二叉树的建立和遍历

【问题描述】

　　已知二叉树的先序和中序遍历序列,推出它的后序遍历序列。

　　输入: 共两行,第1行一一个字符串，表示树的先序遍历，第2行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。

　　输出: 仅一行，表示树的后序遍历序列。

　　【样例输入】

　　　　abdec

　　　　dbeac

　　【样例输出】

　　　　debca

#include<iostream>
#include<cstring>
using namespace std;
char pre[101], mid[101]; 
int root=0, cnt=0,n; // 分别表示根节点的下标、编号和个数。 

struct node{
    char value; // 节点名称。
    int lchild, rchild; 
} data[101]; // 声明node类型的数组data。 

int create(int preL, int preR, int midL, int midR, int rt){
    if(preL>preR) return 0; // 递归的边界条件。
    rt=++cnt;
    // 找到每个根节点的位置index。 
    int index;
    for(int i=midL; i<=midR; i++){
        if(mid[i]==pre[preL]) {
            index=i;
            break;
        }
    } 
    data[rt].value=mid[index];
    int numLeft = index-midL;
    data[rt].lchild=create(preL+1, preL+numLeft, midL, index-1, rt);
    data[rt].rchild=create(preL+numLeft+1, preR, index+1, midR, rt);
    return rt;
} 

void rootPos(int rt){
    if(rt){
        rootPos(data[rt].lchild);
        rootPos(data[rt].rchild);
        cout<<data[rt].value;
    }
    return;
} 

int main(){
    cin>>pre>>mid;
    n=strlen(pre); 
    int root = create(0, n-1, 0, n-1, 0); // 分别传入先序和中序的左端元素和右端元素的下标与根节点的下标。
    rootPos(root);// 后序遍历输出：寻找节点的位置。 
    return 0;
}