数据结构 二叉树的非递归遍历

举报
悦来客栈的老板 发表于 2020/12/29 00:16:25 2020/12/29
【摘要】 #include <stdio.h>#include <stdlib.h> #define STACT_INIT_SIZE 100#define STACTINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -2 typedef char TElemType; typedef struc...

  
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define STACT_INIT_SIZE 100
  4. #define STACTINCREMENT 10
  5. #define OK 1
  6. #define ERROR 0
  7. #define OVERFLOW -2
  8. typedef char TElemType;
  9. typedef struct BiNode
  10. {
  11. TElemType data;
  12. struct BiNode *lchild,*rchild;
  13. }BiNode, *BiTree;
  14. typedef BiTree SElemType;
  15. typedef struct
  16. {
  17. SElemType *base;
  18. SElemType *top;
  19. int stacksize;
  20. }SqStack;
  21. int InitStack(SqStack &S)
  22. {
  23. S.base = (SElemType *)malloc(STACT_INIT_SIZE * sizeof(SElemType));
  24. if (!S.base)
  25. {
  26. exit(OVERFLOW);
  27. }
  28. S.top = S.base ;
  29. S.stacksize = STACT_INIT_SIZE;
  30. return OK;
  31. }
  32. int Push(SqStack &S, SElemType e)
  33. {
  34. if (S.top - S.base >= S.stacksize)
  35. {
  36. S.base = (SElemType*)realloc(S.base , (S.stacksize + STACTINCREMENT) * sizeof(SElemType));
  37. if (!S.base)
  38. {
  39. exit(OVERFLOW);
  40. }
  41. S.top = S.base + S.stacksize ;
  42. S.stacksize += STACTINCREMENT;
  43. }
  44. *S.top++ = e;
  45. return OK;
  46. }
  47. int Pop(SqStack &S, SElemType &e)
  48. {
  49. if (S.base == S.top)
  50. {
  51. return ERROR;
  52. }
  53. e = *--S.top;
  54. return OK;
  55. }
  56. int GetTop(SqStack S,SElemType &e)
  57. {
  58. if (S.base == S.top)
  59. {
  60. return ERROR;
  61. }
  62. e = *(S.top-1);
  63. return OK;
  64. }
  65. int StackEmpty(SqStack S)
  66. {
  67. if (S.top == S.base )
  68. {
  69. return 1;
  70. }
  71. return 0;
  72. }
  73. void Create_BiTree(BiTree &T)
  74. {
  75. TElemType ch;
  76. scanf("%c",&ch);
  77. if (ch == '#')
  78. {
  79. T = NULL;
  80. }
  81. else
  82. {
  83. T = (BiTree)malloc(sizeof(BiNode));
  84. if (!T)
  85. {
  86. exit(OVERFLOW);
  87. }
  88. T->data = ch;
  89. Create_BiTree(T->lchild);
  90. Create_BiTree(T->rchild);
  91. }
  92. }
  93. void PreOrderTraverse1(BiTree T)
  94. {//先序遍历的递归调用1
  95. SqStack S;
  96. BiTree p = T;
  97. InitStack(S);
  98. Push(S,p);
  99. while (!StackEmpty(S))
  100. {
  101. while (GetTop(S,p) && p)
  102. {
  103. printf("%c",p->data);
  104. Push(S,p->lchild);
  105. }
  106. Pop(S,p);
  107. if (!StackEmpty(S))
  108. {
  109. Pop(S,p);
  110. Push(S,p->rchild);
  111. }
  112. }
  113. }
  114. void PreOrderTraverse2(BiTree T)
  115. {//先序遍历的递归调用2
  116. SqStack S;
  117. BiTree p = T;
  118. InitStack(S);
  119. while (p || !StackEmpty(S))
  120. {
  121. if (p)
  122. {
  123. printf("%c",p->data);
  124. Push(S,p);
  125. p = p->lchild;
  126. }
  127. else
  128. {
  129. Pop(S,p);
  130. p = p->rchild;
  131. }
  132. }
  133. }
  134. void InOrderTraverse1(BiTree T)
  135. {//中序遍历的非递归调用1
  136. SqStack S;
  137. BiTree p = T;
  138. InitStack(S);
  139. Push(S,p);
  140. while (!StackEmpty(S))
  141. {
  142. while (GetTop(S,p) && p)
  143. {
  144. Push(S,p->lchild);
  145. }
  146. Pop(S,p);
  147. if (!StackEmpty(S))
  148. {
  149. Pop(S,p);
  150. printf("%c",p->data);
  151. Push(S,p->rchild);
  152. }
  153. }
  154. }
  155. void InOrderTraverse2(BiTree T)
  156. {//中序遍历的非递归调用2
  157. SqStack S;
  158. BiTree p = T;
  159. InitStack(S);
  160. while (p || !StackEmpty(S))
  161. {
  162. if (p)
  163. {
  164. Push(S,p);
  165. p = p->lchild;
  166. }
  167. else
  168. {
  169. Pop(S,p);
  170. printf("%c",p->data);
  171. p = p->rchild;
  172. }
  173. }
  174. }
  175. void PostOrderTraverse1(BiTree T)
  176. {
  177. BiTree p,p1;
  178. SqStack S;
  179. p = T;
  180. p1 = NULL;
  181. InitStack(S);
  182. while (p || !StackEmpty(S))
  183. {
  184. if (p)
  185. {
  186. Push(S,p);
  187. //visit,先序
  188. p = p->lchild;
  189. }
  190. else
  191. {
  192. GetTop(S,p);
  193. //visit,中序
  194. if (p->rchild == p1)
  195. {//右子树为空,或者为上一次弹出的子树,则弹出根节点
  196. Pop(S,p1);
  197. p = NULL;
  198. //visit,后序
  199. printf("%c",p1->data);
  200. }
  201. else
  202. {
  203. p = p->rchild;
  204. p1 = NULL;
  205. }
  206. }
  207. }
  208. }
  209. int main()
  210. {
  211. BiTree T;
  212. Create_BiTree(T);
  213. PreOrderTraverse1(T);
  214. printf("\n");
  215. PreOrderTraverse2(T);
  216. printf("\n");
  217. InOrderTraverse1(T);
  218. printf("\n");
  219. InOrderTraverse2(T);
  220. printf("\n");
  221. PostOrderTraverse1(T);
  222. printf("\n");
  223. return 0;
  224. }

文章来源: blog.csdn.net,作者:悦来客栈的老板,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/qq523176585/article/details/17249245

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。