二叉树的操作实现
这里的二叉树全部都是用二叉链实现，算法都是一些简单的递归
- 根据二叉树括号表示法字符串str生成对应的二叉树链式存储结构
- 输出二叉树
- 先序遍历、中序遍历、后序遍历
- 销毁二叉树
- 查找值为x的结点
- 求二叉树的高度
- 求二叉树元素的最大值
- 求二叉树结点个数
- 输出所有的叶子结点
- 求二叉树中结点值x的层数
- 求二叉树第k层的结点个数
- 求第k层上叶子结点的个数
- 求二叉树中所有单分支结点个数
- 判断两棵树是否相似
- 输出值为x的结点的所有祖先
- 输出值为x的结点的所有子孙结点
- 判断值为x的结点和值为y的结点是否为兄弟
- 将二叉树b1复制到二叉树b2
- 将二叉树的所有左右子树进行交换
- 判断一颗二叉树是否是完全二叉树
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 typedef char ElemType;
5 typedef struct node
6 {
7 ElemType data;
8 struct node *lchild;
9 struct node *rchild;
10 }BTNode;
11
12 const int MaxSize = 100 + 10;
13
14 //根据二叉树括号表示法字符串str生成对应的二叉树链式存储结构
15 void CreateBTree(BTNode * &b, char *str)
16 {
17 BTNode *St[MaxSize], *p; //St作为顺序栈
18 int top = -1, k,j = 0; //top作为栈顶指针
19 char ch;
20 b = NULL;
21 ch = str[j];
22 while (ch != '\0')
23 {
24 switch (ch)
25 {
26 case '(':top++; St[top] = p; k = 1; break; //开始处理左孩子结点
27 case ')':top--; break; //栈顶结点的子树处理完毕
28 case ',':k = 2; break; //开始处理右孩子结点
29 default:
30 p = (BTNode *)malloc(sizeof(BTNode)); //创建一个结点，由p指向它
31 p->data = ch;
32 p->lchild = p->rchild = NULL;
33 if (b == NULL) b = p; //若尚未创建根节点
34 else
35 {
36 switch (k)
37 {
38 case 1:St[top]->lchild = p; break;
39 case 2:St[top]->rchild = p; break;
40 }
41 }
42 }
43 j++; //继续扫描str
44 ch = str[j];
45 }
46 }
47
48 //输出二叉树DispBTree(b)
49 void DispBTree(BTNode *b)
50 {
51 if (b != NULL)
52 {
53 printf("%c", b->data);
54 if (b->lchild != NULL || b->rchild != NULL)
55 {
56 printf("("); //有孩子结点时才输出“（”
57 DispBTree(b->lchild); //递归处理左子树
58 if (b->rchild != NULL) printf(","); //有右孩子结点时才输出“,”
59 DispBTree(b->rchild); //递归处理右子树
60 printf(")"); //有孩子结点时才输出
61 }
62 }
63 }
64
65 //先序遍历
66 void PreOrder(BTNode * b)
67 {
68 if (b != NULL)
69 {
70 printf("%c", b->data);
71 PreOrder(b->lchild);
72 PreOrder(b->rchild);
73 }
74 }
75 //中序遍历
76 void InOrder(BTNode * b)
77 {
78 if (b != NULL)
79 {
80 InOrder(b->lchild);
81 printf("%c", b->data);
82 InOrder(b->rchild);
83 }
84 }
85 //后序遍历
86 void PostOrder(BTNode * b)
87 {
88 if (b != NULL)
89 {
90 InOrder(b->lchild);
91 InOrder(b->rchild);
92 printf("%c", b->data);
93 }
94 }
95
96 //销毁二叉树
97 void DestroyBTree(BTNode *& b)
98 {
99 if (b != NULL)
100 {
101 DestroyBTree(b->lchild);
102 DestroyBTree(b->rchild);
103 free(b);
104 }
105 }
106
107
108 //查找值为x的结点
109 BTNode *FindNode(BTNode *b, ElemType x)
110 {
111 BTNode *p;
112 if (b == NULL) return NULL;
113 else if (b->data == x) return b;
114 else
115 {
116 p = FindNode(b->lchild, x);
117 if (p != NULL) return p;
118 else return FindNode(b->rchild, x);
119 }
120 }
121
122 //求二叉树的高度
123 int BTHeight(BTNode *b)
124 {
125 int lchildh, rchildh;
126 if (b == NULL) return 0;
127 else
128 {
129 lchildh = BTHeight(b->lchild);
130 rchildh = BTHeight(b->rchild);
131 return lchildh > rchildh ? (lchildh + 1) : (rchildh + 1);
132 }
133 }
134
135 //求二叉树元素的最大值
136 int BTMax(BTNode *b)
137 {
138 if (b == NULL) return 0;
139 else
140 {
141 int m1 = BTMax(b->lchild);
142 int m2 = BTMax(b->rchild);
143 int m3 = b->data;
144 if (m1 > m2) return m1 > m3 ? m1 : m3;
145 else return m2 > m3 ? m2 : m3;
146 }
147 }
148
149 //求二叉树结点个数
150 int BTNum(BTNode * b)
151 {
152 if (b == NULL) return 0;
153 else return BTNum(b->lchild) + BTNum(b->rchild) + 1;
154 }
155
156 //输出所有的叶子结点
157 void DispLeaf(BTNode *b)
158 {
159 if (b != NULL)
160 {
161 if (b->lchild == NULL && b->rchild == NULL)
162 printf("%c", b->data);
163 DispLeaf(b->lchild);
164 DispLeaf(b->rchild);
165 }
166 }
167
168 //求二叉树中结点值x的层数
169 //返回0表示未找到,h初始置为0
170 int BTLevel(BTNode *b, ElemType x, int h)
171 {
172 int level;
173 if (b == NULL) return 0;
174 else if (b->data == x) return h;
175 else
176 {
177 level = BTLevel(b->lchild, x, h + 1);
178 if (level != 0) return level;
179 else return BTLevel(b->rchild, x, h + 1);
180 }
181 }
182
183 //求二叉树第k层的结点个数
184 //当前层数h初始置为0
185 int BTKlevel(BTNode *b,int h, int k)
186 {
187 if (b == NULL) return 0;
188 else
189 {
190 if (h == k) return 1;
191 if (h < k) return (BTKlevel(b->lchild, h + 1, k) + BTKlevel(b->rchild,h + 1,k));
192 }
193 }
194
195 //求第k层上叶子结点的个数
196 int BTKlevelLeaf(BTNode *b, int h, int k)
197 {
198 if (b == NULL) return 0;
199 else
200 {
201 if (h == k && b->lchild == NULL && b->rchild == NULL) return 1;
202 if (h < k) return (BTKlevelLeaf(b->lchild, h + 1, k) + BTKlevelLeaf(b->rchild, h + 1, k));
203 }
204 return 0; //其它情况返回0
205 }
206
207 //求二叉树中所有单分支结点个数
208 int BTSingleSonNode(BTNode * b)
209 {
210 if (b == NULL) return 0;
211 else if ((b->lchild == NULL && b->rchild != NULL) || (b->lchild != NULL && b->rchild == NULL)) return BTSingleSonNode(b->lchild) + BTSingleSonNode(b->rchild) + 1;
212 else return BTSingleSonNode(b->lchild) + BTSingleSonNode(b->rchild);
213 }
214
215 //判断两棵树是否相似
216 //形态一样，结点值可以不同
217 bool BTLike(BTNode *b1, BTNode *b2)
218 {
219 bool flag1, flag2;
220 if (b1 == NULL && b2 == NULL) return true;
221 else if (b1 == NULL || b2 == NULL) return false;
222 else
223 {
224 flag1 = BTLike(b1->lchild, b2->lchild);
225 flag2 = BTLike(b1->rchild, b2->rchild);
226 return flag1 && flag2;
227 }
228 }
229
230 //输出值为x的结点的所有祖先
231 //f(b,x)=true表示以结点b为根节点的二叉树包含x
232 bool BTAncestor(BTNode *b, ElemType x)
233 {
234 if (b == NULL) return false;
235 else if ((b->lchild != NULL && b->lchild->data == x) || (b->rchild != NULL && b->rchild->data == x))
236 {
237 printf("%c", b->data);
238 return true;
239 }
240 else
241 {
242 int flag1 = BTAncestor(b->lchild, x);
243 int flag2 = BTAncestor(b->rchild, x); //考虑到可能存在多个x，分开写
244 if(flag1 || flag2) printf("%c", b->data);
245 return true;
246 }
247 return false;
248 }
249
250 //输出值为x的结点的所有子孙结点
251 void BTChild(BTNode *b, ElemType x)
252 {
253 if (b != NULL)
254 {
255 if (b->data == x)
256 {
257 PreOrder(b->lchild);
258 PreOrder(b->rchild);
259 }
260 else
261 {
262 BTChild(b->lchild,x);
263 BTChild(b->rchild,x);
264 }
265 }
266 }
267
268 //判断值为x的结点和值为y的结点是否为兄弟
269 bool BTBrother(BTNode *b, ElemType x, ElemType y)
270 {
271 if (b == NULL) return false;
272 else
273 {
274 if (b->lchild != NULL && b->rchild != NULL)
275 if ((b->lchild->data == x && b->rchild->data == y) || (b->lchild->data == y && b->rchild->data == x))
276 return true;
277 return BTBrother(b->lchild, x, y) || BTBrother(b->rchild, x, y);
278 }
279 }
280
281 //将二叉树b1复制到二叉树b2
282 void BTCopy(BTNode *b1, BTNode * &b2)
283 {
284 if (b1 == NULL) b2 = NULL;
285 else
286 {
287 b2 = (BTNode *)malloc(sizeof(BTNode));
288 b2->data = b1->data;
289 BTCopy(b1->lchild, b2->lchild);
290 BTCopy(b1->rchild, b2->rchild);
291 }
292 }
293
294 //将二叉树的所有左右子树进行交换
295 void BTSwap(BTNode *b1, BTNode * &b2)
296 {
297 if (b1 == NULL) b2 = NULL;
298 else
299 {
300 b2 = (BTNode *)malloc(sizeof(BTNode));
301 b2->data = b1->data;
302 BTSwap(b1->rchild, b2->lchild);
303 BTSwap(b1->lchild, b2->rchild);
304 }
305 }
306
307
308 //判断一颗二叉树是否是完全二叉树
309 //两条规则，违反任意一条均不是完全二叉树
310 //1、某结点无左孩子，则一定没有右孩子
311 //2、若某结点缺少左孩子或右孩子，则其所有后继（层次遍历的后继）一定无孩子
312 bool BTComp(BTNode *b)
313 {
314 BTNode *Qu[MaxSize], *p; //定义一个队列用于层次遍历
315 int front = 0, rear = 0; //环形队列的队头和队尾指针
316 bool cm = true; //cm为真表示二叉树为完全二叉树
317 bool flag = true; //flag为真表示所有结点到目前为止都有左右孩子
318 if (b == NULL) return true;
319 rear++;
320 Qu[rear] = b; //根结点入队
321 while (front != rear) //队列不为空
322 {
323 front = (front + 1) % MaxSize;
324 p = Qu[front]; //队首出队
325 if (p->lchild == NULL)
326 {
327 flag = false;
328 if (p->rchild != NULL) //没有左孩子，则一定没有右孩子
329 {
330 cm = false;
331 break;
332 }
333 }
334 else
335 {
336 if ((!flag)) //出现空缺少左孩子或右孩子之后，所有的结点均无孩子
337 {
338 cm = false;
339 break;
340 }
341 rear = (rear + 1) % MaxSize;
342 Qu[rear] = p->lchild; //左孩子入队
343 if (p->rchild == NULL) flag = false;
344 else
345 {
346 rear = (rear + 1) % MaxSize;
347 Qu[rear] = p->rchild; //右孩子入队
348 }
349 }
350 }
351 return cm;
352 }
353
354 int main()
355 {
356 BTNode *b1, *b2;
357 char str1[] = "A(B(D(,G)),C(E(,G),F))";
358 char str2[] = "A(B(D,D),C(E))";
359 CreateBTree(b2,str2);
360 printf("%d\n", BTComp(b2));
361 return 0;
362 }
参考资料：《数据结构教程》李春葆等