【非递归】二叉树的建立及遍历

采用先序序列输入，二叉链表存储结构，非递归方式建立二叉树。

对于非递归算法建立二叉树可以参考迷宫算法给出；

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