1 #include <stdio.h>
2 #include <stdlib.h>
3 #define INIT_STACK_SIZE 100
4 #define STACKINCREMENT 10
5
6 //*****二叉樹的二叉鏈表存儲結構*****//
7 typedef struct BiNode
8 {
9 char data;
10 struct BiNode *lchild, *rchild;
11 int visitcount; //訪問次數(後序遍歷會用到)
12 }BiNode, *BiTree;
13
14 typedef struct
15 {
16 BiNode **base;
17 BiNode **top;
18 int stacksize;
19 }SqStack;
20
21 //*****初始化棧*****//
22 void InitStack(SqStack &S)
23 {
24 if (!(S.base = (BiNode **)malloc(sizeof(BiTree) * INIT_STACK_SIZE)))
25 {
26 return;
27 }
28 S.top = S.base;
29 S.stacksize = INIT_STACK_SIZE;
30
31 return;
32 }
33
34 //*****元素進棧*****//
35 void Push(SqStack &S, BiNode *e)
36 {
37 if (S.top - S.base >= S.stacksize)
38 {
39 if (!(S.base = (BiNode **)realloc(S.base, sizeof(BiTree) * (STACKINCREMENT + S.stacksize))))
40 {
41 return;
42 }
43 S.stacksize += STACKINCREMENT;
44 }
45 *S.top++ = e;
46
47 return;
48 }
49
50 //*****元素出棧*****//
51 void Pop(SqStack &S, BiNode **e)
52 {
53 if (S.base == S.top)
54 {
55 return;
56 }
57 *e = *--S.top;
58
59 return;
60 }
61
62 //*****取棧頂元素*****//
63 int GetTop(SqStack S, BiNode **e)
64 {
65 if (S.base == S.top)
66 {
67 return 0;
68 }
69 *e = *(S.top - 1);
70
71 return 1;
72 }
73
74 //*****判斷棧是否為空*****//
75 int StackEmpty(SqStack S)
76 {
77 if (S.top == S.base)
78 return 1;
79 else
80 return 0;
81 }
82
83 //*****按先序次序輸入二叉樹中結點的值(一個字符)，空格字符表示空樹構造二叉鏈表表示的二叉樹T*****//
84 void CreateBiTree(BiTree &T)
85 {
86 char ch;
87 scanf("%c", &ch);
88 if(ch == ' ')
89 {
90 T = NULL;
91 }
92 else
93 {
94 if(!(T = (BiNode *)malloc(sizeof(BiNode))))
95 {
96 return;
97 }
98 T->data = ch; //生成根結點
99 CreateBiTree(T->lchild); //構造左子樹
100 CreateBiTree(T->rchild); //構造右子樹
101 }
102
103 return;
104 }
105
106 //*****先序遍歷二叉樹方法1*****//
107 void PreorderTraverse_1(BiTree T)
108 {
109 BiTree p;
110 SqStack S;
111 InitStack(S);
112 Push(S, T); //根指針進棧
113 while(!StackEmpty(S))
114 {
115 while(GetTop(S, &p) && p)
116 {
117 printf("%c ", p->data);
118 Push(S, p->lchild);
119 }
120 Pop(S, &p); //空指針退棧
121 if(!StackEmpty(S))
122 {
123 Pop(S, &p); //根結點出棧
124 Push(S,p->rchild); //右孩子進棧
125 }
126 }
127
128 return;
129 }
130
131 //*****先序遍歷二叉樹方法2*****//
132 void PreorderTraverse_2(BiTree T)
133 {
134 BiTree p = T;
135 SqStack S;
136 InitStack(S);
137
138 while (p || !StackEmpty(S))
139 {
140 if (p)
141 {
142 printf("%c ", p->data);
143 Push(S,p);
144 p = p->lchild;
145 }
146 else
147 {
148 Pop(S, &p);
149 p = p->rchild;
150 }
151 }
152 }
153
154 //*****中序遍歷二叉樹方法1*****//
155 void InOrderTraverse_1(BiTree T)
156 {
157 SqStack S;
158 BiTree p;
159 InitStack(S);
160 Push(S,T);
161 while (!StackEmpty(S))
162 {
163 while (GetTop(S,&p) && p)
164 {
165 Push(S,p->lchild); //向左走到盡頭
166 }
167 Pop(S,&p); //空指針退棧
168 if (!StackEmpty(S))
169 {
170 Pop(S,&p);
171 printf("%c ", p->data);
172 Push(S,p->rchild);
173 }
174 }
175
176 return;
177 }
178
179 //*****中序遍歷二叉樹方法2*****//
180 void InOrderTraverse_2(BiTree T)
181 {
182 BiTree p = T;
183 SqStack S;
184 InitStack(S);
185
186 while (p || !StackEmpty(S))
187 {
188 if (p)
189 {
190 Push(S,p);
191 p = p->lchild;
192 }
193 else
194 {
195 Pop(S, &p);
196 printf("%c ", p->data);
197 p = p->rchild;
198 }
199 }
200
201 return;
202 }
203
204 //*****後序遍歷二叉樹*****//
205 void PostOrderTraverse(BiTree T)
206 {
207 SqStack S;
208 BiTree p = T;
209 InitStack(S);
210
211 while (p || !StackEmpty(S))
212 {
213 if(p)
214 {
215 if (p->visitcount != 2)
216 {
217 p->visitcount = 1;
218 Push(S, p);
219 }
220 p = p->lchild;
221 }
222 else
223 {
224 Pop(S, &p);
225 if(p->visitcount == 2)
226 {
227 printf("%c ", p->data);
228 }
229 else
230 {
231 p->visitcount++;
232 Push(S, p);
233 }
234 p = p->rchild;
235 }
236 }
237
238 return;
239 }
240
241 int main(void)
242 {
243 BiTree T;
244 printf("請按先序次序輸入二叉樹中結點的值(字符)，空格字符表示空樹:\n");
245 CreateBiTree(T);
246
247 printf("先序遍歷方法1結果為:");
248 PreorderTraverse_1(T);
249 printf("\n\n");
250
251 printf("先序遍歷方法2結果為:");
252 PreorderTraverse_2(T);
253 printf("\n\n");
254
255 printf("中序遍歷方法1結果為:");
256 InOrderTraverse_1(T);
257 printf("\n\n");
258
259 printf("中序遍歷方法2結果為:");
260 InOrderTraverse_2(T);
261 printf("\n\n");
262
263 printf("後序遍歷結果為:");
264 PostOrderTraverse(T);
265 printf("\n\n");
266
267 return 0;
268 }
以如下二叉樹為例，給出按先序次序輸入二叉樹中結點的值（字符），從而按照本文給出的算法構造二叉樹。
輸入字符的順序是：-+a空格空格*b空格空格-c空格空格d空格空格/e空格空格f空格空格，即可驗證本文給出的遍歷算法。
