分类: 数据结构及算法2012-04-28 14:30 8572人阅读 评论(6) 收藏 举报

利用栈实现二叉树的先序,中序,后序遍历的非递归操作

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <stdlib.h>
  4. #include <queue>
  5. #include <stack>
  6. #include <iostream>
  7. using namespace std;
  8. typedef struct BiTNode{
  9. char data;
  10. BiTNode *lchild, *rchild;
  11. }BiTNode,*BiTree;
  12. void CreateBiTree(BiTree &T)//建树,按先序顺序输入节点
  13. {
  14. char ch;
  15. scanf("%c",&ch);
  16. if(ch==' ')
  17. {
  18. T=NULL;
  19. return;
  20. }
  21. else
  22. {
  23. T=(BiTree)malloc(sizeof(BiTNode));
  24. if(!T)
  25. exit(1);
  26. T->data=ch;
  27. CreateBiTree(T->lchild);
  28. CreateBiTree(T->rchild);
  29. }
  30. }
  31. void InOrderTraverse(BiTree T)//非递归中序遍历
  32. {
  33. stack<BiTree> Stack;
  34. if(!T)
  35. {
  36. printf("空树!\n");
  37. return;
  38. }
  39. while(T || !Stack.empty())
  40. {
  41. while(T)
  42. {
  43. Stack.push(T);
  44. T=T->lchild;
  45. }
  46. T=Stack.top();
  47. Stack.pop();
  48. printf("%c",T->data);
  49. T=T->rchild;
  50. }
  51. }
  52. void PreOrderTraverse(BiTree T)//非递归先序遍历
  53. {
  54. stack<BiTree> Stack;
  55. if(!T)
  56. {
  57. printf("空树!\n");
  58. return;
  59. }
  60. while(T || !Stack.empty())
  61. {
  62. while(T)
  63. {
  64. Stack.push(T);
  65. printf("%c",T->data);
  66. T=T->lchild;
  67. }
  68. T=Stack.top();
  69. Stack.pop();
  70. T=T->rchild;
  71. }
  72. }
  73. void PostOrderTraverse(BiTree T)//非递归后序遍历,用一个标记标记右子树是否访问过
  74. {
  75. int flag[20];
  76. stack<BiTree> Stack;
  77. if(!T)
  78. {
  79. printf("空树!\n");
  80. return;
  81. }
  82. while(T)
  83. {
  84. Stack.push(T);
  85. flag[Stack.size()]=0;
  86. T=T->lchild;
  87. }
  88. while(!Stack.empty())
  89. {
  90. T=Stack.top();
  91. while(T->rchild && flag[Stack.size()]==0)
  92. {
  93. flag[Stack.size()]=1;
  94. T=T->rchild;
  95. while(T)
  96. {
  97. Stack.push(T);
  98. flag[Stack.size()]=0;
  99. T=T->lchild;
  100. }
  101. }
  102. T=Stack.top();
  103. printf("%c",T->data);
  104. Stack.pop();
  105. }
  106. }
  107. void main()
  108. {
  109. BiTree T;
  110. CreateBiTree(T);
  111. PreOrderTraverse(T);
  112. printf("\n");
  113. InOrderTraverse(T);
  114. printf("\n");
  115. PostOrderTraverse(T);
  116. printf("\n");
  117. }
 ZT 二叉树先序,中序,后序遍历非递归实现-LMLPHP
05-06 05:42