wustoj (二叉树)

╰半夏微凉° 2022-06-06 04:51 123阅读 0赞

问题描述:

根据一棵二叉树的先序和中序遍历序列，可以将该二叉树构造出来。

包含多组测试数据。每组测试数据一行，给出两个由大写字母组成的字符串，分别表示某二叉树的先序和中序遍历结果。

输出该二叉树的后序遍历序列。

## Sample Input  ##

DBACEGF ABCDEFG  
BCAD CBAD

## Sample Output ##

ACBFGED

CDAB

题目来源:[点击打开链接][Link 1]

题目分析:为了确定这棵二叉树我们就得确定每个节点的左儿子和右儿子，我们知道中序遍历的特点就是先遍历左子树然后根节点，接着就是右子树，也就是说我们知道到了根节点那么左边就是左子树的节点，右边是右子树的节点，很巧合的是先序遍历第一个节点就是根节点！那么树找到了根节点，而且左子树的节点和右子树的节点也区分了。然后就是把左子树看成一棵二叉树，右子树看成一棵二叉树，继续以上操作！

它其实是一个递归过程 一直是找节点 然后左儿子 右儿子的过程

代码如下:

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<functional>
    using namespace std;
    
    string pre,mid;
    struct tree
    {
        struct tree* lchild;
        struct tree* rchild;
        char val;
    }*Tree;
    tree* built(int lp,int rp,int lm,int rm)
    {
        struct tree*  T=new tree;
        if (lp==rp) {//如果相等了，那么就表明到了叶子节点
            T->val=pre[lp];
            T->lchild=NULL;//左右儿子指针空
            T->rchild=NULL;
            return T;
        }
        if (lp>rp||lm>rm) return NULL;
        int k=mid.find(pre[lp]);//找到那个根节点
        T->val=pre[lp];
        T->lchild=built(lp+1,lp+k-lm,lm,k-1);//左边是左儿子。递归下去继续找
        T->rchild=built(lp+k-lm+1,rp,k+1,rm);//右边是右儿子
        return T;
    }
    void postorder(tree *T)//后序遍历
    {
        if(T)
        {
            postorder(T->lchild);
            postorder(T->rchild);
            cout<<T->val;
        }
    }
    int main()
    {
        while (cin>>pre>>mid) {
            int len=pre.size();
            Tree=built(0,len-1,0,len-1);
            postorder(Tree);
            cout<<endl;
        }
        return 0;
    }

[Link 1]: http://acm.wust.edu.cn/problem.php?cid=1219&pid=1