构造二叉树并遍历

Birty

发布日期: 2018-12-21 14:02:32 浏览量: 1084
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

介绍

已知二叉树的后序遍历和中序遍历序列,构造对应的二叉树,并非递归前序遍历该二叉树。

1 解题思路

先建立一个结构体,结构体中包含数据域以及左孩子和右孩子的指针域。然后首先输入中序遍历和后序遍历的数组,再定义四个变量:il,ir,pl,pr即中序遍历的左右端点和后序遍历的左右端点。然后调用子函数,

分配空间,将后序遍历的右端点数据放入数据域。之后处理左右孩子,若左孩子存在则递归调用子函数,右孩子同理。最后将二叉树用非递归先序遍历输出。

2 函数调用图

3 各函数功能

  1. // 根据中序和后序构造二叉树
  2. void buildTree(int inOrder[], int postOrder[], int il, int ir, int pl, int pr, BitTree T);
  3. // 主函数,流程控制,输入中序遍历和后序遍历的数组
  4. int main();

4 测试

5 源代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4. typedef struct BitTree {
  5. int data; /*定义数据*/
  6. struct BitTree *lChild, *rChild; /*定义左右孩子指针*/
  7. }BitNode, *BitTree;
  8. void buildTree(int inOrder[], int postOrder[], int il, int ir, int pl, int pr, BitTree T) { /*根据中序和后序构造二叉树*/
  9. T = (BitTree)malloc(sizeof(BitNode));
  10. T -> data = postOrder[pr]; /*后序序列中最后一个元素为二叉树的根节点*/
  11. int m = il;
  12. while(inOrder[m] != postOrder[pr]) { /*查找根节点在中序序列的位置*/
  13. m++;
  14. }
  15. if (m == il) { /*左子树的中序序列为空*/
  16. T -> lChild = NULL;
  17. } else {
  18. buildTree(inOrder, postOrder, il, m - 1, pl, pl + m -1 - il, T -> lChild); /*确定左子树*/
  19. }
  20. if (m == ir) { /*右子树的中序序列为空*/
  21. T -> rChild = NULL;
  22. } else {
  23. buildTree(inOrder, postOrder, m + 1, ir, pr - ir + m, pr - 1, T -> rChild); /*确定右子树*/
  24. }
  25. }
  26. int preOrder(BitTree T) { /*非递归先序遍历*/
  27. BitTree stack[100]; /*基于栈进行遍历*/
  28. int front = 0, rear = 0;
  29. BitNode *p;
  30. if(T != NULL) {
  31. stack[rear] = T; /*将根节点入栈*/
  32. rear = (rear + 1) % 100;
  33. }
  34. while (front != rear) {
  35. p = stack[front];
  36. front = (front + 1) % 100;
  37. printf("%5d", p -> data); /*输出节点*/
  38. if(p -> lChild != NULL) { /*左子树不为空就输出左子树*/
  39. stack[rear] = p -> lChild; /*左子树入栈*/
  40. rear = (rear + 1) % 100;
  41. }
  42. if(p -> rChild != NULL) { /*最后是右子树*/
  43. stack[rear] = p -> rChild; /*右子树入栈*/
  44. rear = (rear + 1) % 100;
  45. }
  46. }
  47. return;
  48. }
  49. int main() {
  50. int i, il, ir, pl, pr; /*il和ir为中序序列的左右端点, pl和pr为后序序列的左右端点*/
  51. int len;
  52. BitNode *T; /*树的根节点*/
  53. printf("请输入数组的长度:\n");
  54. scanf("%d", &len);
  55. int inOrder[len]; /*中序的数组*/
  56. printf("请依次输入中序数组:\n");
  57. for(i = 0; i < len; i++) {
  58. scanf("%d", &(inOrder[i]));
  59. }
  60. int postOrder[len]; /*后序的数组*/
  61. printf("请依次输入后序数组:\n");
  62. for(i = 0; i < len; i++) {
  63. scanf("%d", &(postOrder[i]));
  64. }
  65. il = 0;
  66. ir = len - 1;
  67. pl = 0;
  68. pr = len - 1;
  69. buildTree(inOrder, postOrder, il, ir, pl, pr, &T);
  70. preOrder(&T);
  71. return 1;
  72. }
上传的附件 cloud_download 构造二叉树并遍历.7z ( 181.17kb, 25次下载 )
error_outline 下载需要8点积分

发送私信

只愿岁月静好,别无所求

20
文章数
15
评论数
最近文章
eject