歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

【非遞歸】二叉樹的建立及遍歷

采用先序序列輸入,二叉鏈表存儲結構,非遞歸方式建立二叉樹。

對於非遞歸算法建立二叉樹可以參考迷宮算法給出;

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<conio.h>
  4. typedefstruct tree
  5. {
  6. char ch;
  7. struct tree *lchild;
  8. struct tree *rchild;
  9. int flag;
  10. }TREE;
  11. typedefstruct
  12. {
  13. TREE *elem[30];
  14. int top;
  15. }STACK;
  16. void initStack(STACK *S);
  17. int push(STACK *S, TREE *x);
  18. int pop(STACK *S, TREE **x);
  19. int Pass(TREE *p);
  20. TREE *createTree();
  21. void fristRoot(TREE *root);
  22. void middleRoot(TREE *root);
  23. void lastRoot(TREE *root);
  24. void destroyTree(TREE *root);
  25. int main()
  26. {
  27. TREE *root;
  28. root = createTree();
  29. printf("\n先序:\n");
  30. fristRoot(root);
  31. printf("\n中序:\n");
  32. middleRoot(root);
  33. printf("\n後序:\n");
  34. lastRoot(root);
  35. printf("\n");
  36. destroyTree(root);
  37. return 0;
  38. }
  39. void initStack(STACK *S)
  40. {
  41. S->top = -1;
  42. }
  43. int push(STACK *S, TREE *x)
  44. {
  45. if (S->top >= 29)
  46. return 0;
  47. S->top++;
  48. S->elem[S->top] = x;
  49. return 1;
  50. }
  51. int pop(STACK *S, TREE **x)
  52. {
  53. if (S->top < 0)
  54. return 0;
  55. *x = S->elem[S->top];
  56. S->top--;
  57. return 1;
  58. }
  59. int Pass(TREE *p)
  60. {
  61. if (p->lchild == NULL)
  62. if (p->rchild == NULL)
  63. return 0;
  64. else
  65. if (p->rchild->flag)
  66. return 0;
  67. else
  68. return 2;
  69. else
  70. if (p->lchild->flag)
  71. if (p->rchild == NULL)
  72. return 0;
  73. else
  74. if (p->rchild->flag)
  75. return 0;
  76. else
  77. return 2;
  78. else
  79. if (p->rchild == NULL)
  80. return -1;
  81. else
  82. if (p->rchild->flag)
  83. return -1;
  84. else
  85. return 1;
  86. }
  87. TREE *createTree()
  88. {
  89. char ch;
  90. STACK S;
  91. TREE *root, *p, *q, *temp;
  92. int i, ret;
  93. initStack(&S);
  94. root = (TREE *)malloc(sizeof(TREE));
  95. printf("Please input string:\n");
  96. ch = getche();
  97. root->ch = ch;
  98. p = root;
  99. p->lchild = p->rchild = p;
  100. p->flag = 0;
  101. push(&S, p);
  102. i = 0;
  103. do{
  104. if( (ret = Pass(p) ) > 0 )
  105. {
  106. ch = getche();
  107. if(ch != ' ')
  108. {
  109. q = (TREE *)malloc(sizeof(TREE));
  110. q->ch = ch;
  111. q->lchild = q->rchild = q;
  112. q->flag = 0;
  113. push(&S, q);
  114. }
  115. else
  116. q = NULL;
  117. if (ret == 1)
  118. p->lchild = q;
  119. elseif (ret == 2)
  120. p->rchild = q;
  121. }
  122. else
  123. pop(&S, &temp);
  124. if(S.top > -1)
  125. {
  126. p->flag = 1;
  127. if(p->lchild != p && p->rchild == p)
  128. p->flag = 0;
  129. p = S.elem[S.top];
  130. }
  131. }while(S.top > -1);
  132. return root;
  133. }
  134. void fristRoot(TREE *root)
  135. {
  136. TREE *p;
  137. STACK S;
  138. initStack(&S);
  139. p = root;
  140. while( p || S.top > -1)
  141. {
  142. while(p)
  143. {
  144. printf("%c ",p->ch);
  145. push(&S, p);
  146. p = p->lchild;
  147. }
  148. if(!p)
  149. {
  150. pop(&S, &p);
  151. p = p->rchild;
  152. }
  153. }
  154. }
  155. void middleRoot(TREE *root)
  156. {
  157. TREE *p;
  158. STACK S;
  159. initStack(&S);
  160. p = root;
  161. while(p || S.top > -1)
  162. {
  163. if(p)
  164. {
  165. push(&S, p);
  166. p = p->lchild;
  167. }
  168. else
  169. {
  170. pop(&S, &p);
  171. printf("%c ",p->ch);
  172. p = p->rchild;
  173. }
  174. }
  175. }
  176. void lastRoot(TREE *root)
  177. {
  178. TREE *p, *q;
  179. STACK S;
  180. initStack(&S);
  181. p = root;
  182. while(p || S.top != -1)
  183. {
  184. while(p)
  185. {
  186. push(&S, p);
  187. p = p->lchild;
  188. }
  189. if(S.top > -1)
  190. {
  191. p = S.elem[S.top];
  192. if(p->rchild == NULL || p->rchild == q)
  193. {
  194. printf("%c ",p->ch);
  195. q = p;
  196. S.top--;
  197. p = NULL;
  198. }
  199. else
  200. p = p->rchild;
  201. }
  202. }
  203. }
  204. void destroyTree(TREE *root)
  205. {
  206. if (root != NULL)
  207. {
  208. destroyTree(root->lchild);
  209. destroyTree(root->rchild);
  210. free(root);
  211. }
  212. }
Copyright © Linux教程網 All Rights Reserved