树

基本术语：

节点的度：
- 叶子节点=0
- 分支节点：含有的子树个数
节点关系：
- 父，子，兄
节点层次：
- 根节点：1 floor
- 路径：两节点间经过的节点序列
- 路径长度：路径上的边数

树的分类：

节点子树是否可以互换位置：
- 有序树：从左到右各子树依次有序（不能互换
- 无序树

二叉树

基本理论

定义1：

各节点度 ≤2
有序树

定义2（递归方式）：

空树
非空树：一根两子，且子树也为二叉树

特殊二叉树：

满二叉树FullBinaryTree：
- 深度为k，则最后一个节点编号为2^k-1
- 特殊的完全二叉树
完全二叉树CompleteBinaryTree：
- 仅末排右侧有空节点
二叉搜索树BinarySearchTree：
- 左子树值<根节点值<右子树值
- 子数可default（缺省
平衡二叉搜索树BalancedBinaryTree：
- 叶节点间，高度差不超过1（只允许相邻两层存在叶节点

存储结构：

顺序存储：
- 适用于完全二叉树
- 二叉堆结构（堆排，优先队列）
- 一维数组
- 采用完全二叉树的节点层次编号
- 空节点：^
- 节点关系：
  - 某非叶节点下标=i：
    - 左孩子下标=2*i+1
    - 右孩子下标=2*i+2
  - 某非根节点下标=i：
    - 根节点下标=（i-1）/2（整除
链式存储：二叉链
- 适用于一般二叉树
- left--val--right：左右指针域和数据与域

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

和链表类似，但比链表多了一个指针（两指针，左右孩子

建树--扩展二叉树

二叉链表：lchild--data(val)--rchild
非空节点的空指针引出”虚“节点：#
e.g. AB#D##C##
- A
- BC
- D##
- ..##

#include<iostream>
#include<string>
using namespace std;

typedef struct Bnode{
    char data;
    Bnode *lch,*rch; 
}Bnode,*BTree;
//等价于
typedef Bnode,*BTree;//BTree equals to BNode
struct Bnode{
    char data;
    Bnode *lch,*rch; 
};

void CreatBTree(BTree &BT){
    char ch;
    cin>>ch;
    if(ch=='#')
        BT=nullptr;
    else{
        BT=(BTree)malloc(sizeof(Bnode));
        if(!BT)
            exit(EOF);
        BT->data=ch;
        CreatBTree(BT->lch);
        CreatBTree(BT->rch);
    }
}

int main(){
    cout<<"二叉树的扩展前序序列"<<endl;
    BTree root;
    CreatBTree(root);
    return 0;
}

typedef：给结构体Bnode起别名BTree

二叉树的遍历

深度优先搜索DFS（DepthFirstSearch)

3种遍历顺序：

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
指的是遍历到中间节点的顺序

递归遍历

< 递归三要素 >

递归函数的参数和返回值
终止条件
单层逻辑

144.前序遍历

参数and返回值：
- 根节点: TreeNode* cur
- 遍历节点打印数组：vector< int >& nums
终止条件：
- cur==nullptr
单层逻辑：
- 根值--左孩子值--右孩子值

void preordertraversal(TreeNode* cur,vector<int>& nums){
    if(cur==nullptr)
        return;
    nums.push_back(cur->val);
    preordertraversal(cur->left,nums);
    preordertraversal(cur->right,nums);
}

94.中序遍历

void intraversal(TreeNode* cur,vector<int>& nums){
    if(cur==nullptr)
        return;
    intraversal(cur->left,nums);
    nums.push_back(cur->val);
    intraversal(cur->right,nums);
}

145.后序遍历

void posttraversal(TreeNode* cur,vector<int>& nums){
    if(cur==nullptr)
        return;
    posttraversal(cur->left,nums);
    posttraversal(cur->right,nums);
    nums.push_back(cur->val);
}

迭代遍历（显式栈）

< stack >

前序遍历：

根节点为空：return
stack存放树节点
根节点进栈
根节点取值入vector，出栈
右孩子进，左孩子进
栈空：跳出循环

vector<int> pre(TreeNode* root){
    stack<TreeNode*> st;
    vector<int> res;
    if(root==nullptr)
        return res;
    st.push(root);
    while(!st.empty()){
        TreeNode* node=st.top();
        st.pop();//先出根，再进右左子树
        res.push_back(node->val);
        if(node->right) st.push(node->right);
        if(node->left) st.push(node->left);
    }
    return res;
}

中序遍历：

栈：左孩子一口气进完：判断空节点
取值：判断栈空
循环体：
- 进左
- else遇到空节点
- 弹出栈顶元素==中
- 右节点进栈为cur

vector<int> in(TreeNode* root){
    stack<TreeNode*> st;
    vector<int> res;
    TreeNode* cur=root;
    while(cur!=nullptr || !st.empty()){
        if(cur!=nullptr){
            st.push(cur);
            cur=cur->left;
            //一直进左孩子
        }
        else{
            cur=st.top();
            st.pop();
            res.push_back(cur->val);//中
            cur=cur->right;//右
        }
    }
    return res;
}

后序遍历：

翻转前序遍历

reverse(preres.begin(),preres.end());
return preres;//postres

广度优先搜索BFS（BreadthFirstSearch)

102.层序遍历

< queue >

进：root
出：root
进：左右孩子
出：左孩子；进：左--左右子孙
出：右孩子；进：右--左右子孙

vector<vector<int>> level(TreeNode* root){
    queue<TreeNode*> que;
    if(root!=nullptr)
        que.push(root);
    vector<vector<int>> res;
    while(!que.empty()){
        int size=que.size();
        vector<int> vec;
        for(int i=0;i<size;i++){
            TreeNode* node=que.front();
            que.pop();
            vec.push_back(node->val);
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }
        res.push_back(vec);
    }
    return res;
}

104.二叉树的最大深度

#include<iostream>
#include<queue>
#include"TreeNode.h"
using namespace std;

//迭代
int maxDepth(TreeNode* root) {
    int depth=0;
    queue<TreeNode*> que;
    if(root==nullptr)
        return 0;
    que.push(root);
    while (!que.empty()){
        int size=que.size();
        depth++;
        for(int i=0;i<size;i++){
            TreeNode* node=que.front();
            que.pop();
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }
    }
    return depth;
}

void Build(){

}


int main(){
    
    return 0;
}

自定义头文件

嫌cv树节点定义太麻烦，顺便下学了下怎么自定义头文件，引用起来方便且高级一点

结构：

防止头文件名重复定义，于是有了一大堆#
也可以把int main( )单独定义在main.cpp（一个独立的源文件）中

文件名：TreeNode.h

#ifndef TreeNode_H
#define TreeNode_H
//完全大写
//.换为_
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
    TreeNode(int x,TreeNode* l):val(x),left(l),right(nullptr){}
    TreeNode(int x,TreeNode* l,TreeNode* r):val(x),left(l),right(r){}
};

#endif

头文件引用区分<> & " ":