SDUT 1489 求二叉树的先序遍历 (中序后序还原二叉树)

时间：2022-11-30 16:44:17

求二叉树的先序遍历

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

 已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历

Input

 输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的中序遍历序列，第二个字符串表示二叉树的后序遍历序列。 

Output

 输出二叉树的先序遍历序列

Example Input

2

dbgeafc

dgebfca

lnixu

linux

Example Output

abdegcf

xnliu

DQE:

本题考查的主要内容是已知中序和后序遍历序列还原二叉树，需要注意后序的结构为（左子树，右子树，根），递归时倒取字符，先创建右子树。
附先序中序还原二叉树链接：http://www.cnblogs.com/Mimick/p/6031657.html
 
 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 struct Tree

 {

     char c;

     Tree *lt,*rt;

 };

 Tree *creat(char *&hx,char *zx)

 {

     if(*zx=='\0')

         return NULL;

     char *x,*y;

     Tree *r=new Tree;

     int i=;

     while(zx[i]!='\0')

     {

         if(zx[i]==*hx)

         {

             r->c=zx[i];

             zx[i]='\0';

             hx--;

             x=zx;

             y=zx+i+;

             r->rt=creat(hx,y);

             r->lt=creat(hx,x);

             break;

         }

         i++;

     }

     return r;

 }

 void xout(Tree *r)

 {

     if(r==NULL)

         return ;

     printf("%c",r->c);

     xout(r->lt);

     xout(r->rt);

 }

 int main()

 {

     Tree *root;

     int n;

     scanf("%d",&n);

     while(n--)

     {

         char hx[],zx[],*p;

         scanf("%s %s",zx,hx);

         p=hx+strlen(hx)-;

         root=creat(p,zx);

         xout(root);

         printf("\n");

     }

     return ;

 }

 /***************************************************

 User name: ***

 Result: Accepted

 Take time: 0ms

 Take Memory: 156KB

 Submit time: 2016-11-08 18:22:21

 ****************************************************/

相关文章