求二叉树的先序遍历

柔光的暖阳◎ 2022-08-18 02:25 221阅读 0赞

求二叉树的先序遍历

#

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

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

输入

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

输出

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

示例输入

  1. 2
  2. dbgeafc
  3. dgebfca
  4. lnixu
  5. linux

示例输出

  1. abdegcf
  2. xnliu

提示

来源

GYX

示例程序

  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #include<string.h>  
  4. struct node  
  5. {  
  6. int data;  
  7. struct node *lchild,*rchild;  
  8. };  
  9. struct node *creat(int n,char *a,char *b)  
  10. {  
  11. struct node *root;  
  12. char *p;  
  13. if(n==0)  
  14. return NULL;  
  15. root=(struct node *)malloc(sizeof(struct node));  
  16. root->data=a[n-1];  
  17. for(p=b;p!='\0';p++)  
  18. if(*p==a[n-1])  
  19. break;  
  20. int t;  
  21. t=p-b;  
  22. root->lchild=creat(t,a,b);  
  23. root->rchild=creat(n-t-1,a+t,p+1);  
  24. return root;  
  25. }  
  26. void qianxu(struct node *root)  
  27. {  
  28. if(root)  
  29. {  
  30. printf("%c",root->data);  
  31. qianxu(root->lchild);  
  32. qianxu(root->rchild);  
  33. }  
  34. }  
  35. int main()  
  36. {  
  37. int i,j,n,m,k,t;  
  38. struct node *root;  
  39. root=(struct node *)malloc(sizeof(struct node));  
  40. char a[100],b[100];  
  41. while(scanf("%d",&n)!=EOF)  
  42. {  
  43. while(n--)  
  44. {  
  45. scanf("%s %s",b,a);  
  46. m=strlen(a);  
  47. root=creat(m,a,b);  
  48. qianxu(root);  
  49. printf("\n");  
  50. }  
  51. }  
  52. }

发表评论

表情：
评论列表 （有 0 条评论，221人围观）

还没有评论，来说两句吧...

相关阅读

    相关 二叉树先序遍历

    前两天面试，看见了个笔试题，关于二叉树的，今天算是把自己的一点理解写下来吧。 今天看网文，才想起来，二叉树的先序遍历、中序遍历、后序遍历， 遍历顺序都是

    向右看齐向右看齐/ 0 赞/ 304 阅读