C语言 数据结构之二叉树 数据结构上机测试4.1:二叉树的遍历与应用1

爱被打了一巴掌 2022-06-01 14:29 56阅读 0赞

数据结构上机测试4.1:二叉树的遍历与应用1
Time Limit: 1000MS Memory Limit: 65536KB
Submit Statistic
Problem Description

输入二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列。
Input

第一行输入二叉树的先序遍历序列;
第二行输入二叉树的中序遍历序列。
Output

输出该二叉树的后序遍历序列。
Example Input

ABDCEF
BDAECF
Example Output

DBEFCA

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. struct node
  5. {
  6. char data;
  7. struct node *l, *r;
  8. };
  9. char s1[2000], s2[2000];
  10. struct node *creat(int n, char *s1, char *s2)
  11. {
  12. int i;
  13. if(n == 0)
  14. return NULL;
  15. struct node *root;
  16. root = (struct node*) malloc (sizeof(struct node));
  17. root -> data = s1[0];
  18. for(i = 0; i < n; i++)
  19. {
  20. if(s2[i] == s1[0])
  21. break;
  22. }
  23. root -> l = creat(i, s1 + 1, s2);
  24. root -> r = creat(n - 1 - i, s1 + i + 1, s2 + i + 1);
  25. return root;
  26. }
  27. void houxv(struct node *root)
  28. {
  29. if(root)
  30. {
  31. houxv(root -> l);
  32. houxv(root -> r);
  33. printf("%c", root -> data);
  34. }
  35. }
  36. int main()
  37. {
  38. scanf("%s", s1);
  39. scanf("%s", s2);
  40. int n = strlen(s1);
  41. struct node *root;
  42. root = creat(n, s1, s2);
  43. houxv(root);
  44. return 0;
  45. }

发表评论

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

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

相关阅读