二叉树顺序表示的实现(C语言)

二叉树顺序表示的实现(C语言)

二叉树顺序表示的实现(C语言)

1. #include <stdio.h>  
2. #include <string.h>  
3. #include <math.h>  
4.  
5. #define OK 1  
6. #define ERROR 0  
7. #define TRUE 1  
8. #define FALSE 0  
9. #define MAX_TREE_SIZE 100  
10.  
11. typedef char seq_bitree[MAX_TREE_SIZE]; //可以把seq_bitree当做一个数据类型用了  
12.  
13. char nil = ' '; //字符型节点设' '为空节点  
14. int (*visit_fun)(char); 
15.  
16. struct position 
17. { 
18.     int level; 
19.     int order; 
20. }; 
21.  
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.     } 
32.  
33.     return ; 
34. } 
35.  
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); 
44.  
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.         } 
55.  
56.         if((i != 0) && (tree[(i + 1) / 2 - 1] == nil) && (tree[i] != nil)) 
57.         { 
58.             printf("出现了无父节点的非根节点!\n"); 
59.             exit(ERROR); 
60.         } 
61.     } 
62.  
63.     for(i = len; i < MAX_TREE_SIZE; i++) //将剩余的部分置为空节点  
64.     { 
65.         tree[i] = nil; 
66.     } 
67.  
68.     return ; 
69. } 
70.  
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.     } 
85.  
86. } 
87.  
88. /* 
89. 获取二叉树的深度 
90. */ 
91. int get_bitree_depth(seq_bitree tree) 
92. { 
93.     int i = 0; 
94.     int depth = 0; 
95.  
96.     for(i = (MAX_TREE_SIZE - 1); i >= 0; i--) 
97.     { 
98.         if(tree[i] != nil) 
99.         { 
100.             break; 
101.         } 
102.     } 
103.      
104.     do 
105.     { 
106.         depth++; 
107.     }while(i >= (int)pow(2, depth)); 
108.  
109.  
110.     return depth; 
111. } 
112.  
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. } 
126.  
127. /* 
128. 先序遍历二叉树 
129. */ 
130. int preorder_traverse(seq_bitree tree, int (*visit)(char)) 
131. { 
132.     visit_fun = visit; 
133.  
134.     if(is_bitree_empty(tree)) 
135.     { 
136.         printf("the tree is empty.\n"); 
137.     } 
138.     pre_traverse(tree, 0); 
139.  
140.     return OK; 
141. } 
142.  
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.     } 
150.  
151.     visit_fun(tree[index]); 
152.  
153.     if(tree[2 * index + 2] != nil) 
154.     { 
155.         in_traverse(tree, (2 * index + 2)); 
156.     } 
157. } 
158.  
159. /* 
160. 中序遍历二叉树 
161. */ 
162. int inorder_traverse(seq_bitree tree, int (*visit)(char)) 
163. { 
164.     visit_fun = visit; 
165.  
166.     if(is_bitree_empty(tree)) 
167.     { 
168.         printf("the tree is empty.\n"); 
169.     } 
170.     in_traverse(tree, 0); 
171.  
172.     return OK; 
173. } 
174.  
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.     } 
182.  
183.     if(tree[2 * index + 2] != nil) 
184.     { 
185.         post_traverse(tree, (2 * index + 2)); 
186.     } 
187.  
188.     visit_fun(tree[index]); 
189. } 
190.  
191. /* 
192. 后序遍历二叉树 
193. */ 
194. int postorder_traverse(seq_bitree tree, int (*visit)(char)) 
195. { 
196.     visit_fun = visit; 
197.  
198.     if(is_bitree_empty(tree)) 
199.     { 
200.         printf("the tree is empty.\n"); 
201.     } 
202.     post_traverse(tree, 0); 
203.  
204.     return OK; 
205. } 
206.  
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; 
215.  
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.     } 
225.  
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"); 
235.  
236.     return OK; 
237. } 
238.  
239. int visit(char e) 
240. { 
241.     printf("%c ", e); 
242.     return OK; 
243. } 
244.  
245. int main(int argc, char *argv[]) 
246. { 
247.     seq_bitree tree; 
248.  
249.     char str_tree[MAX_TREE_SIZE] = "abcde    fg"; 
250.     //测试数据，假设二叉树层序遍历如上（' '表示该处无节��）  
251.      
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); 
268.  
269.     return 0; 
270. }