二叉树的遍历

二叉树的遍历

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83498#problem/D

    题意：

     输入一颗二叉树的先序遍历和中序遍历序列，输出后序遍历序。

样例：

Sample Input 

DBACEGF ABCDEFG
BCAD CBAD

Sample Output 

ACBFGED
CDAB


题解：
  
 因为先序序列的第一个字符是根，所以可以在中序序列中找到根的位置，找出左子树和右子树；
并将根记入后序数组中（采用倒序的方法）。
如此用递归进行遍历即可；
注意由于此出是倒序记入所以遍历时应该先遍历右子树后遍历左子树。
知识：

1．先序遍历：

若二叉树非空，则依次执行如下操作：访问根结点—>遍历左子树->遍历右子树。

2．中序遍历：

若二叉树非空，则依次执行如下操作：遍历左子树->访问根结点->遍历右子树。

3．后序遍历：

若二叉树非空，则依次执行如下操作：遍历左子树->遍历右子树->访问根结点。

#include<iostream>
 #include<cstring>
 #include<cstdio>
 using namespace std;
 char a[30],b[30],c[30];
 int n,m;
 void input(int x,int y,int z,int e)     
 {
     m--;
   c[m]=a[x];//将根倒序的放入数组中
     int p=z;
     while(b[p]!=c[m])
          p++;  //找出根节点在中序中的位置   
    if(p!=e) 
        input(x+p-z+1,y,p+1,e);     //右子树（到最右端时结束）
    if(p!=z)  
         input(x+1,y,z,p-1);    //左子树
}
 int main()
 {
    while(scanf("%s%s",a,b)!=EOF)
    {
        n=strlen(a);
         m=n;
     memset(c,0,30);
         input(0,n-1,0,n-1);  //参数分别为先序序列首字符的下标，先序列长度，中序序列首字符的下标，中序列的长度
     cout<<c;
         cout<<endl;
     }
     return 0;
 }