由遍历序列构建二叉树（再遍历输出完结）

电玩女神 2022-09-10 04:25 185阅读 0赞

在学校的教材上没找到这个知识点  
**二叉树构造定理**

*  定理7.1：任何n（n>0）个不同结点的二又树，都可由它的中序序列和先序序列唯一地确定。
 *  定理7.2：任何n（n＞0）个不同结点的二又树，都可由它的中序序列和后序序列唯一地确定。

这里会用到递归算法。  
前序遍历：根节点 左子树 右子树  
中序遍历：左子树 根节点 右子树  
后序遍历：左子树 右子树 根节点  
任何一个序列都是按照以上的顺序来进行排列的，所以先找到根节点，在通过中序序列分出左子树和右子树，也就能在前序序列和后序序列中找到左右子树的根节点，再使用递归算法，就能构造二叉树。

以下是某个题目的代码（看懂怎么创造二叉树的就行）：

#include <iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    using namespace std;
    
    typedef struct node{ 
        struct node *l,*r;
        char data;
    } tree;
    //由前序序列和中序序列创建一个二叉树 
    tree *creat(char *tr1,char *tr2,int len)//tr1是前序序列，tr2是中序序列 
    { 
        tree *p; 
        if(len<=0)p=NULL;//空树就返回空指针 
        else
        { 
            p=new tree;
            p->data=*tr1;
            char *a;
            for(a=tr2; a!=NULL; a++)//在中序序列中寻找根节点 
                if(*a==*tr1)break;
            int lm=a-tr2;//属于左子树的序列 
            p->l=creat(tr1+1,tr2,lm);// 递归左子树
            p->r=creat(tr1+1+lm,a+1,len-1-lm);//递归右子树
     
        }
        return p;//返回根节点的指针 
    }
    //后序遍历 
    void after(tree *t)
    { 
        if(t)
        { 
            after(t->l);
            after(t->r);
            cout<<t->data;
        }
    }
    //层次遍历 
    void cen(tree *t)
    { 
        tree *p[1010];
        int flas=0;
        int glas=0;
        if(t)
            p[flas++]=t;
        while(flas>glas)
        { 
            t=p[glas++];
            cout<<t->data;
            if(t->l)
            { 
                p[flas++]=t->l;
     
            }
            if(t->r)
            { 
                p[flas++]=t->r;
            }
        }
    }
    int main()
    { 
        int t;
        cin>>t;//输入多组数据 
        while(t--)
        { 
            tree *T;
            char tr1[51];
            char tr2[51];
            cin>>tr1;
            cin>>tr2;
            int len=strlen(tr1);
            T=creat(tr1,tr2,len);//创建二叉树 
            after(T);
            cout<<endl;
            cen(T);
            cout<<endl;
        }
        return 0;
    }

以下附上一些详细的知识点：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57u05YWL5aSa55qE6YCG6aOO_size_20_color_FFFFFF_t_70_g_se_x_16]

*  前序遍历和中序遍历

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57u05YWL5aSa55qE6YCG6aOO_size_20_color_FFFFFF_t_70_g_se_x_16 1]

*  后序遍历和中序遍历

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57u05YWL5aSa55qE6YCG6aOO_size_20_color_FFFFFF_t_70_g_se_x_16 2]

*  层次遍历和中序遍历

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57u05YWL5aSa55qE6YCG6aOO_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
以后有更深的理解，我会更新的

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57u05YWL5aSa55qE6YCG6aOO_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/86dcc67a571a4723ab30a3c99ac0eca8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57u05YWL5aSa55qE6YCG6aOO_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/d9998a9eb6e944c88e22aacef81d26c0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57u05YWL5aSa55qE6YCG6aOO_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/aeacb0ddec1e42bd94e62e416e244e1b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57u05YWL5aSa55qE6YCG6aOO_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/e7d8bb7f59ba4284a98bd3100abc3c70.png