C/C++实现重建二叉树

重建二叉树

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
描述
题目很简单,给你一棵二叉树的后序和中序序列,求出它的前序序列(So easy!)。

输入
输入有多组数据(少于100组),以文件结尾结束。
每组数据仅一行,包括两个字符串,中间用空格隔开,分别表示二叉树的后序和中序序列(字符串长度小于26,输入数据保证合法)。
输出
每组输出数据单独占一行,输出对应得先序序列。
样例输入
ACBFGED ABCDEFG
CDAB CBAD
样例输出
DBACEGF
BCAD
这道题主要考查对二叉树的遍历的熟悉程度,对先序遍历,中序遍历,后序遍历的掌握程度;

由后序遍历可以得到,最后一个字母应该就是树的根节点,中序遍历是先访问左子树,后访问根节点,在访问右子树,然后通过中序遍历的序列,可以把这颗树分成左右子树,得出这颗树的结构,然后再递归得出先序遍历的序列;

下面是代码:

[cpp]

  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <cstdlib>  
  4. struct node  
  5. {  
  6.     char value;  
  7.     node *lchild,*rchild;//左孩子,右孩子  
  8. };  
  9. node *newnode(char c)  
  10. {  
  11.   node *p=(node *)malloc(sizeof(node));  
  12.   p->value=c;  
  13.   p->lchild=p->rchild=NULL;  
  14.   return p;  
  15. }  
  16. node *rebulid(char *post,char *in,int n)  
  17. {  
  18.     if(n==0) return NULL;  
  19.     char ch=post[n-1];//得到的是根节点的值  
  20.     node *p=newnode(ch);  
  21.     int i;  
  22.     for(i=0;i<n&&in[i]!=ch;i++);  
  23.     int l_len=i;  
  24.     int r_len=n-i-1;  
  25.     if(l_len>0) p->lchild=rebulid(post,in,l_len);//由中序遍历得出左右子树的值  
  26.     if(r_len>0) p->rchild=rebulid(post + l_len, in+l_len+1, r_len);  
  27.     return p;  
  28. }  
  29. void preorder(node *p)//先序遍历  
  30. {  
  31.     if(p==NULL) return;  
  32.     printf(“%c”,p->value);  
  33.     preorder(p->lchild);  
  34.     preorder(p->rchild);  
  35. }  
  36. int main()  
  37. {  
  38.     char postorder[30],inorder[30];  
  39.     while(scanf(“%s%s”,postorder,inorder)!=EOF)  
  40.     {  
  41.         node *root=rebulid(postorder,inorder,strlen(postorder));  
  42.         preorder(root);  
  43.         printf(“\n”);  
  44.     }  
  45.     return 0;  
  46. }  

标签