数据结构实验之求二叉树后序遍历和层次遍历（根据前序中序还原二叉树）

傷城~ 2022-05-17 00:26 182阅读 0赞

先介绍一下树的层次遍历，顾名思义一层一层的遍历输出，eg：

![Center][]

：  
这一个二叉树的层次遍历为ABECFDGHK;

其次就是根据一个二叉树的前序中序序列还原一个二叉树：首先要知道前序遍历以及中序遍历的规则，前序遍历也叫先序遍历。前序遍历有一个特点，第一个节点为二叉树的根节点，根据这个根节点可以在中序序列中找到根节点的左右子树。例如：一个二叉树前序序列是：a b d e g c f,中序序列是：d b g e a f c，则根据前序序列第一个数据为a，在中序序列中可以看出此二叉树的左子树为：d b g e ，右子树为：f c ，此时就可以用递归解决了，前序序列指针往后移动一个位置即为左子树的根节点，前序序列指针往后移动左子树节点个数加一个位置即为右子树的根节点的位置。下面为具体的代码实现：

[https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2562/pid/2137][https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2562_pid_2137]（代码为此例题解）

#include<bits/stdc++.h>
    using namespace std;
    struct tree
    {
        char data;
        tree *lc,*rc;
    }*T;
    char pre[55],in[55];
    tree *creat(char *pre,char *in,int n)///根据前序中序遍历结果还原二叉树；
    {
        tree *t;
        char *p;
        int k;
        if(n<=0)
            return NULL;
            t=new tree;
            t->data=*pre;
            for(p=in;p<in+n;p++)
            {
                if(*p==*pre)
                    break;
            }
          k=p-in;
          t->lc=creat(pre+1,in,k);///通过递归的方式还原；先还原根节点，然后是左子树最后是右子树；
          t->rc=creat(pre+k+1,p+1,n-k-1);
          return t;
    }
    void postorder(tree *T)///后序遍历的输出二叉树；
    {
        if(T)
        {
            postorder(T->lc);
            postorder(T->rc);
            cout<<T->data;
        }
    }
    int cctree(tree *T,int i)///通过层次遍历输出；
    {
        if(!T||i<0)
            return 0;
        if(i==0)
        {
            cout<<T->data;
            return 1;
        }
            return cctree(T->lc,i-1)+cctree(T->rc,i-1);
    }
    void level(tree *T)///层序遍历的控制函数；
    {
        int i=0;
        for(i=0;;i++)
        {
            if(!cctree(T,i))
                break;
        }
    }
    
    int main()
    {
        int i,n;
        cin>>n;
        while(n--)
        {
            scanf("%s%s",pre,in);
            i=strlen(pre);
            T=creat(pre,in,i);
            postorder(T);
            cout<<endl;
            level(T);
            cout<<endl;
        }
    
    }

[Center]: /images/20220517/66bb074fdabc4671b33f5837b0e50ebe.png
[https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2562_pid_2137]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2562/pid/2137