求二叉树的先序遍历

╰+攻爆jí腚メ 2022-05-14 03:40 212阅读 0赞

Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
已知一棵二叉树的中序遍历和后序遍历,求二叉树的先序遍历
Input
输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的中序遍历序列,第二个字符串表示二叉树的后序遍历序列。
Output
输出二叉树的先序遍历序列
Sample Input
2
dbgeafc
dgebfca
lnixu
linux
Sample Output
abdegcf
xnliu
Hint

Source
GYX

  1. #include <iostream>
  2. //#include <string>
  3. //#include <typeinfo>
  4. //#include <algorithm>
  5. #include <cstring>
  6. using namespace std;
  7. typedef struct nd
  8. {
  9. char data;
  10. nd *left, *right;
  11. } node, *pnode;
  12. pnode zhonghou(char hou[],int len,char zhong[])
  13. {
  14. if(len<=0)
  15. return NULL;
  16. pnode root = nullptr;
  17. root=new node();
  18. root->data=hou[len-1];
  19. int p;//根的下标
  20. for(p=0; p<len; p++)
  21. if(zhong[p]==hou[len-1])
  22. break;
  23. root->left=zhonghou(hou,p,zhong);
  24. root->right=zhonghou(hou+p,len-p-1,zhong+p+1);
  25. return root;
  26. };
  27. void xian(pnode root)
  28. {
  29. if(root)
  30. {
  31. cout << root->data;
  32. xian(root->left);
  33. xian(root->right);
  34. }
  35. }
  36. int main()
  37. {
  38. int t;
  39. char zhong[1000],hou[1000];
  40. pnode root = nullptr;
  41. cin >>t;
  42. while(t--)
  43. {
  44. cin >> zhong >> hou;
  45. int len =strlen(zhong);
  46. root=zhonghou(hou,len,zhong);
  47. xian(root);
  48. cout << endl;
  49. }
  50. return 0;
  51. }

发表评论

表情:
评论列表 (有 0 条评论,212人围观)

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

相关阅读

    相关

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