二叉樹順序表示的實現(C語言)

二叉樹順序表示的實現(C語言)

1. #include <stdio.h>
2. #include <string.h>
3. #include <math.h>
5. #define OK 1
6. #define ERROR 0
7. #define TRUE 1
8. #define FALSE 0
9. #define MAX_TREE_SIZE 100
11. typedef char seq_bitree[MAX_TREE_SIZE]; //可以把seq_bitree當做一個數據類型用了
13. char nil = ' '; //字符型節點設' '為空節點
14. int (*visit_fun)(char);
16. struct position
17. {
18. int level;
19. int order;
20. };
22. /*
23. 初始化二叉樹，結點值賦為nil
24. */
25. void init_seq_bitree(seq_bitree tree)
26. {
27. int i = 0;
28. for(i = 0; i < MAX_TREE_SIZE; i++)
29. {
30. tree[i] = nil;
31. }
33. return ;
34. }
36. /*
37. 根據輸入的層序str_tree，創建二叉樹
38. */
39. void create_seq_bitree(seq_bitree tree, char *str_tree)
40. {
41. int i = 0;
42. int len = 0;
43. len = strlen(str_tree);
45. for(i = 0; i < len; i++)
46. {
47. if(str_tree[i] == 0)
48. {
49. tree[i] = nil;
50. }
51. else
52. {
53. tree[i] = str_tree[i];
54. }
56. if((i != 0) && (tree[(i + 1) / 2 - 1] == nil) && (tree[i] != nil))
57. {
58. printf("出現了無父節點的非根節點!\n");
59. exit(ERROR);
60. }
61. }
63. for(i = len; i < MAX_TREE_SIZE; i++) //將剩余的部分置為空節點
64. {
65. tree[i] = nil;
66. }
68. return ;
69. }
71. /*
72. 功能： 判斷二叉樹是否為空
73. 返回： TRUE 為空；FLASE 非空
74. */
75. int is_bitree_empty(seq_bitree tree)
76. {
77. if(tree[0] == nil)
78. {
79. return TRUE;
80. }
81. else
82. {
83. return ERROR;
84. }
86. }
88. /*
89. 獲取二叉樹的深度
90. */
91. int get_bitree_depth(seq_bitree tree)
92. {
93. int i = 0;
94. int depth = 0;
96. for(i = (MAX_TREE_SIZE - 1); i >= 0; i--)
97. {
98. if(tree[i] != nil)
99. {
100. break;
101. }
102. }
104. do
105. {
106. depth++;
107. }while(i >= (int)pow(2, depth));
110. return depth;
111. }
113. /*供preorder_traverse調用*/
114. void pre_traverse(seq_bitree tree, int index)
115. {
116. visit_fun(tree[index]);
117. if(tree[2 * index + 1] != nil)
118. {
119. pre_traverse(tree, (2 * index + 1));
120. }
121. if(tree[2 * index + 2] != nil)
122. {
123. pre_traverse(tree, (2 * index + 2));
124. }
125. }
127. /*
128. 先序遍歷二叉樹
129. */
130. int preorder_traverse(seq_bitree tree, int (*visit)(char))
131. {
132. visit_fun = visit;
134. if(is_bitree_empty(tree))
135. {
136. printf("the tree is empty.\n");
137. }
138. pre_traverse(tree, 0);
140. return OK;
141. }
143. /*供inorder_traverse調用*/
144. void in_traverse(seq_bitree tree, int index)
145. {
146. if(tree[2 * index + 1] != nil)
147. {
148. in_traverse(tree, (2 * index + 1));
149. }
151. visit_fun(tree[index]);
153. if(tree[2 * index + 2] != nil)
154. {
155. in_traverse(tree, (2 * index + 2));
156. }
157. }
159. /*
160. 中序遍歷二叉樹
161. */
162. int inorder_traverse(seq_bitree tree, int (*visit)(char))
163. {
164. visit_fun = visit;
166. if(is_bitree_empty(tree))
167. {
168. printf("the tree is empty.\n");
169. }
170. in_traverse(tree, 0);
172. return OK;
173. }
175. /*供postorder_traverse調用*/
176. void post_traverse(seq_bitree tree, int index)
177. {
178. if(tree[2 * index + 1] != nil)
179. {
180. post_traverse(tree, (2 * index + 1));
181. }
183. if(tree[2 * index + 2] != nil)
184. {
185. post_traverse(tree, (2 * index + 2));
186. }
188. visit_fun(tree[index]);
189. }
191. /*
192. 後序遍歷二叉樹
193. */
194. int postorder_traverse(seq_bitree tree, int (*visit)(char))
195. {
196. visit_fun = visit;
198. if(is_bitree_empty(tree))
199. {
200. printf("the tree is empty.\n");
201. }
202. post_traverse(tree, 0);
204. return OK;
205. }
207. /*
208. 按層遍歷二叉樹
209. */
210. int level_order_traverse(seq_bitree tree, int (*visit)(char))
211. {
212. int i = MAX_TREE_SIZE - 1;
213. int j = 0;
214. visit_fun = visit;
216. if(is_bitree_empty(tree))
217. {
218. printf("the tree is empty.\n");
219. return OK;
220. }
221. while(tree[i] != nil)
222. {
223. i--;
224. }
226. for(j = 0; j <+ i; j++)
227. {
228. if(tree[j] == nil) //不存在的結點不打印
229. {
230. continue;
231. }
232. visit_fun(tree[j]);
233. }
234. printf("\n");
236. return OK;
237. }
239. int visit(char e)
240. {
241. printf("%c ", e);
242. return OK;
243. }
245. int main(int argc, char *argv[])
246. {
247. seq_bitree tree;
249. char str_tree[MAX_TREE_SIZE] = "abcde fg";
250. //測試數據，假設二叉樹層序遍歷如上（' '表示該處無節點）
252. init_seq_bitree(tree);
253. create_seq_bitree(tree, str_tree);
254. if(is_bitree_empty(tree))
255. {
256. printf("the bitree is empty.\n");
257. return 0;
258. }
259. printf("the depth of the bitree is %d\n", get_bitree_depth(tree));
260. printf("先序遍歷二叉樹:\n");
261. preorder_traverse(tree, visit);
262. printf("\n中序遍歷二叉樹:\n");
263. inorder_traverse(tree, visit);
264. printf("\n後序遍歷二叉樹:\n");
265. postorder_traverse(tree, visit);
266. printf("\n按層遍歷二叉樹:\n");
267. level_order_traverse(tree, visit);
269. return 0;
270. }