一、二叉树的存储结构与基本操作

1.二叉树的存储结构

定义方式

struct node {
    typename data;
    node* lchild;
    node* rchild;
};

生成一个新节点

node* newNode(int data) { //data为结点权值
    node* Node = new node;  //申请一个node型变量的地址空间
    Node->data = data;
    Node->lchild = Node->rchild = NULL;
    return Node;
}

2.二叉树结点的查找、修改

void search(node* root, int x, int newdata) {
    if(root == NULL) return; //空树，死胡同（递归边界）
    if(root->data == x) root->data = newdata; //找到修改

    search(root->lchild, x, newdata);
    search(root->rchild, x, newdata);
}

3.二叉树结点的插入

//注意根结点指针root要使用引用
void insert(node* &root, int x) {
    if(root == NULL) { //空树，说明查找失败，也即插入位置（递归边界）
        root = newNode(x);
        return;
    }

    if(左子树的条件) insert(root->lchild, x);
    else insert(root->rchild, x);
}

4.二叉树的创建

node* create(int data[], int n) {
    node* root = NULL; //新建空根结点root
    for(int i = 0; i < n; i++){
        insert(root, data[i]);
    }
    return root;
}

二、二叉树的遍历

1.先序遍历

访问顺序：根结点 -> 左子树 -> 右子树

性质：先序遍历序列的第一个元素一定是根结点

void preorder(node* root){
    if(root==NULL) return; //到达空树，递归边界
    //访问根结点root，输出数据域
    printf("%dn", root->data);
    //访问左子树
    preorder(root->lchild);
    //访问右子树
    preorder(root->rchild);
}

2.中序遍历

访问顺序：左子树 -> 根结点 -> 右子树

性质：只要知道根结点，就可以通过根结点在中序遍历序列中的位置区分出左子树和右子树

void inorder(node* root){
    if(root==NULL) return; //到达空树，递归边界
    //访问左子树
    inorder(root->lchild);
    //访问根结点root，输出数据域
    printf("%dn", root->data);
    //访问右子树
    inorder(root->rchild);
}

3.后序遍历

访问顺序：左子树 -> 右子树 -> 根结点

性质：后序序列的最后一个结点一定是根结点

(color{red}{无论是先序遍历序列还是后序遍历序列都必须知道中序遍历序列才能唯一确定一颗树})

void postorder(node* root){
    if(root==NULL) return; //到达空树，递归边界
    //访问左子树
    postorder(root->lchild);
    //访问右子树
    postorder(root->rchild);
    //访问根结点root，输出数据域
    printf("%dn", root->data);
}

4.层序遍历

访问顺序：从上到下，从左到右 BFS

struct node{
    int data;
    int layer;
    node* lchild;
    node* rchild;
};

void LayerOrder(node* root){
    queue<node*> q; //注意队列里是存地址
    root->layer = 1;
    q.push(root);
    while(!q.empty()){
        node* top=q.front();
        q.pop();
        printf("%d ", top->data);
        if(top->lchild != NULL){ //左子树非空
            top->lchild->layer = top->layer + 1;
            q.push(top->lchild);
        }
        if(top->rchild != NULL){ //右子树非空
            top->rchild->layer = top->layer + 1;
            q.push(top->rchild);
        }
    }
}

5.给定一棵二叉树的先序遍历序列和中序遍历序列，重建起这棵二叉树

由先序序列的性质可知，先序序列的第一个元素(pre1)是当前二叉树的根结点。由中序序列的性质可知，当前二叉树的根结点将中序序列划分为左子树和右子树。因此，要做的就是在中序序列中找到某个结点(ink)，使得(ink == pre1)，这样就在中序序列中找到了根结点。所以左子树的结点个数 (numLeft = k - 1)，这样，左子树的先序区间就是([2, k])，左子树的中序序列区间是([1, k-1])；右子树的先序序列区间是([k+1, n])，右子树的中序序列区间是([k+1, n])，接着只要往左子树和右子树进行递归构建二叉树即可。
如果递归过程中当前先序序列的区间是([preL, preR])，中序序列的区间是([inL, inR])，那么左子树的结点个数为(numLeft = k - inL)，这样左子树的先序序列区间就是([preL+1, preL+numLeft])，左子树的中序序列区间是([inL, k-1])，右子树的先序序列区间是([preL+numLeft+1, preR])，右子树的中序序列区间是([k+1, inR])

(color{red}{递归边界：先序序列的长度小于等于0时，当前二叉树就不存在了})

node* create(int preL,int preR, int inL, int inR){
    if(preL > preR){
        return NULL;    // 先序序列长度小于等于0时，直接返回
    }
    node* root = new node;
    root->data = pre[preL];
    int k;
    for(k = inL; k <= inR; k++){
        if(in[k] == pre[preL]){
            break;
        }
    }
    int numLeft = k - inL;

    root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);
    root->rchild = create(preL + numLeft + 1, preR, k + 1， inR);
    return root;
}

同理：用后序遍历序列和中序遍历序列来重建二叉树

node* create(int postL, int postR, int inL, int inR){
    if(postL > postR){
        return NULL;
    }
    node* root = new node;
    root->data = post[postR];
    int k;
    for(k = inL; k <= inR; k++){
        if(in[k] == post[postR]){
            break;
        }
    }
    int numLeft = k - 1 - inL + 1;
    root->lchild = create(postL, postL + numLeft - 1, inL, k - 1);
    root->rchild = create(postL + numLeft, postR - 1, k + 1, inR);
    return root;
}

6.用中序遍历序列和层序遍历序列来重建二叉树

用层序遍历确定根结点，在中序遍历中，利用根结点划分出左右子树。
对各个子树分别执行三步操作：1.在层序序列中，找出子树结点集合中，最靠前的结点，这个结点即为子树的根结点；2.在中序序列中找 1 中得到的根结点，并划分开根节点的左右子树；跟（中序+前序）和（中序+后序）不同之处在于没有迭代的第 3 步，层序是无法直接划分得到左右子树的结点集合的。但这并不妨碍正常的处理。层序是用来找到子树的顶结点的，而根结点即是所有子树的结点中，在层序遍历中最靠前的结点。

代码链接：https://blog.csdn.net/hza419763578/article/details/89042656#变式%3A层序中序序列还原二叉树

#include<iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef char Type;

const int MAXN=100;

struct node{
    Type data;
    node* lchild;
    node* rchild;   
};

//后序[postL,postR]  中序:[inL,inR]
node* Create(Type layer[],Type in[],int len){//长度都一样 一个len即可
    if(len==0) return NULL;
    node* root=new node;
    root->data=layer[0];
    int k;
    //中序中找根
    for(k=0;k<len;k++){
        if(in[k]==layer[0]) break;
    }
    //new节省空间  申请左右子树的层序即可 中序可由指针加法移位获得
    Type *Llay=new Type[len],*Rlay=new Type[len];

    //左子树的先序序列  
    /*中序都很简单根两边就是  难找的就是这个先序 
    好在只是中序顺序换了下 根据中序在整个先序里找
    重复的即可，此处也可看出序列data不能有相同*/
    int cnt=0;
    for(int i=1;i<len;i++){//第0个根结点,i从1开始即可
        for(int j=0;j<k;j++){
            if(layer[i]==in[j]){//in[j]不是in[k] 别犯傻
                Llay[cnt++]=layer[i];
                break;//不可能有重复
            }
        }
    }
    root->lchild=Create(Llay,in,cnt);

    cnt=0;
    for(int i=1;i<len;i++){
        for(int j=k+1;j<len;j++){
            if(layer[i]==in[j]){//in[j]不是in[k] 别犯傻
                Rlay[cnt++]=layer[i];
                break;//不可能有重复
            }
        }
    }
    root->rchild=Create(Rlay,in+k+1,cnt);

    return root;//返回根结点地址
}

//先序遍历
void preOrder(node* root){
    if(root==NULL) return;
    cout<<root->data;
    preOrder(root->lchild);
    preOrder(root->rchild);
}

//中序遍历
void inOrder(node* root){
    if(root==NULL) return;
    inOrder(root->lchild);
    cout<<root->data;
    inOrder(root->rchild);
}

//后序遍历
void postOrder(node* root){
    if(root==NULL) return;
    postOrder(root->lchild);
    postOrder(root->rchild);
    cout<<root->data;
}

//层序遍历
void layerOrder(node* root){
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* top=q.front();
        q.pop();
        cout<<top->data;
        if(top->lchild!=NULL) q.push(top->lchild);
        if(top->rchild!=NULL) q.push(top->rchild);
    }
}

int main(){
    freopen("input5_2.txt","r",stdin);
    Type layer[MAXN],in[MAXN];
    cin>>layer>>in;
    int len=strlen(layer);
    cout<<len<<endl;
    node* root=Create(layer,in,len);
    cout<<"先序遍历:";preOrder(root);cout<<endl;
    cout<<"中序遍历:";inOrder(root);cout<<endl;
    cout<<"后序遍历:";postOrder(root);cout<<endl;
    cout<<"层序遍历:";layerOrder(root);cout<<endl;
    return 0;
}

(color{red}{总结：中序序列可以和先序、后序、层序中的任意一个来构建唯一的二叉树，而后三者两两搭配或者三个在一起都无法构建唯一二叉树})

二、二叉树的静态实现

  方法：静态的二叉链表
     静态二叉链表是指：结点的左右指针域使用int型代替，用来表示左右子树的根结点在数组中的下标。为此需要建立一个大小为结点上限个数的node型数组，所有动态生成的结点都直接使用数组中的结点，所有对指针的操作都改为对数组下标的访问。

定义方式

struct node{
    typename data;   //数据域
    int lchild;   //指向左子树的指针域
    int rchild;  //指向右子树的指针域 
} Node[maxn];    //结点数组，maxn为结点上限个数 

生成一个新节点

int index = 0;
int newNode(int v){     //分配一个Node数组中的结点给新的结点，index为其下标 
    Node[index].data = v;   //数据域为v 
    Node[index].lchild = -1;    //以-1表示空 
    Node[index].rchild = -1;
    return index++;
} 

二叉树的查找

//root为根结点在数组中的下标
void search(int root, int x, int newdata){
    if(root == -1){
        return;
    }
    if(Node[root].data == x){
        Node[root].data = newdata;
    }
    search(Node[root].lchild, x, newdata);
    search(Node[root].rchild, x, newdata);
} 

二叉树的插入

//root为根结点在数组中的下标
void insert(int &root, int x){
    if(root == -1){
        root = newNode(x);
        return;
    }
    if(由二叉树的性质x应该插在左子树){
        insert(Node[root].lchild, x);
    } 
    else{
        insert(Node[root].rchild, x);
    }
} 

二叉树的建立

//函数返回根结点root的下标
int create(int data[], int n){
    int root = -1;
    for(int i = 0; i < n; i++){
        insert(root, data[i]);
    }
    return root;
}

二叉树的遍历

//先序遍历
void preOrder(int root){
    if(root == -1){     //递归边界 
        return;
    }
    printf("%dn", Node[root].data);    //访问根结点，例如将其数据域输出 
    preOrder(Node[root].lchild);        //访问左子树 
    preOrder(Node[root].rchild);        //访问右子树 
}

//中序遍历
void inOrder(int root){
    if(root == -1){     //递归边界 
        return;
    }
    inOrder(Node[root].lchild);         //访问左子树 
    printf("%dn", Node[root].data);       //访问根结点，例如将其数据域输出 
    inOrder(Node[root].rchild);        //访问右子树 
} 

//后序遍历
void postOrder(int root){
    if(root == -1){     //递归边界 
        return;
    }
    postOrder(Node[root].lchild);       //访问左子树 
    postOrder(Node[root].rchild);       //访问右子树 
    printf("%dn", Node[root].data);    //访问根结点，例如将其数据域输出
}

//层序遍历
void layerOrder(int root){
    queue<int> q;       //队列存放数组下标 
    q.push(root);      //将根结点地址入队 
    while(!q.empty()){
        int now = q.front();     //取队首元素 
        q.pop();      
        printf("%d ", Node[now].data);  //访问队首元素 
        if(Node[now].lchild != -1){     //左子树非空 
            q.push(Node[now].lchild);
        } 
        if(Node[now].rchild != -1){     //右子树非空 
            q.push(Node[now].rchild);
        }
    }
}