【数据结构】二叉树-C语言版（二）-阿里云开发者社区

【数据结构】二叉树-C语言版（二）

2023-02-07 59

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】二叉树-C语言版

二叉树的遍历

二叉树共有4种遍历方式：

深度优先遍历有3种：

(1) 前序遍历(先根遍历) 根->左->右 A B D NULL NULL NULL C E NULL NULL F NULL NULL

(2) 中序遍历(中根遍历) 左->根->右 NULL D NULL B NULL A NULL E NULL C NULL F NULL

(3) 后序遍历(后根遍历) 左->右->根 NULL NULL D NULL B NULL NULL E NULL NULL F C A

广度优先遍历有1种：

(4) 层序遍历一层一层遍历 A B C D NULL E F NULL NULL NULL NULL NULL NULL

使用队列进行广度优先遍历的过程：

另外，普通二叉树增删改查没有意义如果是为了存储数据，应该用线性表更简单，用二叉树反而复杂了，并且插入删除还不好定义在哪个位置进行插入删除。排序二叉树的增删改查才有意义，如如下搜索二叉树，左边比父亲小，右边比父亲大：

查找时，每次都和根节点比较，如果比根节点小，就去左子树查找，否则去右子树查找，最多查找高度次，因此查找的时间复杂度为O(N)。极端情况下，效率会退化成O(N)，和链表差不多，可以用AVL树，红黑树，平衡树来解决。

因此二叉树实现先序、中序、后序、层序遍历，不需要实现增删改

二叉树的遍历代码

040-Queue.h修改为如下：040-Queue.c见【数据结构】队列-C语言版

1. #pragma once
2. #include<stdio.h>
3. #include<stdbool.h>
4. #include<assert.h>
5. #include<stdlib.h>
6. 
7. //加入树节点的前置声明，队列的节点变成树，而非原来的int
8. struct BinaryTreeNode;
9. typedef struct BinaryTreeNode* QDataType;
10. 
11. //typedef int QDataType;
12. typedef struct QueueNode
13. {
14.   struct QueueNode* next;
15.   QDataType data;
16. }QueueNode;
17. 
18. typedef struct Queue
19. {
20.   QueueNode* head;
21.   QueueNode* tail;
22. }Queue;
23. 
24. //初始化
25. void QueueInit(Queue* pq);
26. 
27. //销毁
28. void QueueDestroy(Queue* pq);
29. 
30. //插入数据
31. void QueuePush(Queue* pq, QDataType x);
32. 
33. //删除数据
34. void QueuePop(Queue* pq);
35. 
36. //取队头数据
37. QDataType QueueFront(Queue* pq);
38. 
39. //取队尾数据
40. QDataType QueueRear(Queue* pq);
41. 
42. //判断队是否已满
43. bool QueueEmpty(Queue* pq);
44. 
45. //求队列元素个数
46. int QueueSize(Queue* pq);
47.

046-BinaryTree.h

1. #pragma once
2. #define  _CRT_SECURE_NO_WARNINGS  1
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<math.h>
6. #include "040-Queue.h"
7. 
8. typedef char BTDataType;
9. 
10. typedef struct BinaryTreeNode
11. {
12.   struct BinaryTreeNode* left;
13.   struct BinaryTreeNode* right;
14.   BTDataType data;
15. }BTNode;
16. 
17. //创建结点
18. BTNode* CreateTreeNode(BTDataType x);
19. 
20. //先序遍历
21. void PreOrder(BTNode* root);
22. 
23. //中序遍历
24. void InOrder(BTNode* root);
25. 
26. //后序遍历
27. void PostOrder(BTNode* root);
28. 
29. //求结点个数思路一
30. void TreeSize1(BTNode* root,int* psize);
31. 
32. //求结点个数思路二
33. int TreeSize2(BTNode* root);
34. 
35. //求叶子结点个数
36. int TreeLeafSize(BTNode* root);
37. 
38. //求树的高度
39. int TreeDepth(BTNode* root);
40. 
41. //求第k层结点个数
42. int TreeKLeafSize(BTNode* root,int k);
43. 
44. //查找树中值为x的节点
45. BTNode* TreeFind(BTNode* root, BTDataType x);
46. 
47. //二叉树销毁一级指针
48. void BinaryTreeDestroy1(BTNode* root);
49. 
50. //二叉树销毁二级指针
51. void BinaryTreeDestroy2(BTNode** root);
52. 
53. //广度优先遍历：1.根入队  2.出队头，把队头的孩子入队
54. //A入队，A出队，BC入队，B出队，D入队，C出队，EF入队，E出队，F出队
55. 
56. //广度优先遍历，需在上篇文章【数据结构】队列-C语言版的040-Queue.h开头加入树节点的前置声明：见040-Queue.h
57. void TreeLevelOrder(BTNode* root);
58. 
59. //判断二叉树是否是完全二叉树
60. bool BinaryTreeComplete(BTNode* root);

046-BinaryTree.c

1. #include"046-BinaryTree.h"
2. 
3. //创建结点
4. BTNode* CreateTreeNode(BTDataType x)
5. {
6.  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
7.  node->data = x;
8.  node->left = NULL;
9.  node->right = NULL;
10. 
11.   return node;
12. }
13. 
14. //先序遍历
15. void PreOrder(BTNode* root)
16. {
17.   if (root == NULL)
18.   {
19.     printf("NULL ");
20.     return;
21.   }
22.   printf("%c ", root->data);
23.   PreOrder(root->left);
24.   PreOrder(root->right);
25. }
26. 
27. //中序遍历
28. void InOrder(BTNode* root)
29. {
30.   if (root == NULL)
31.   {
32.     printf("NULL ");
33.     return;
34.   }
35. 
36.   InOrder(root->left);
37.   printf("%c ", root->data);
38.   InOrder(root->right);
39. }
40. 
41. //后序遍历
42. void PostOrder(BTNode* root)
43. {
44.   if (root == NULL)
45.   {
46.     printf("NULL ");
47.     return;
48.   }
49. 
50.   PostOrder(root->left);
51.   PostOrder(root->right);
52.   printf("%c ", root->data);
53. }
54. 
55. 
56. //求结点个数，思路一：遍历计数的方式
57. void TreeSize1(BTNode* root,int* psize)
58. {
59.   if (root == NULL)
60.   {
61.     return;
62.   }
63.   (*psize)++;
64.   TreeSize1(root->left, psize);
65.   TreeSize1(root->right, psize);
66. }
67. 
68. //求结点个数思路二，先序遍历（1+左树结点个数+右树结点个数）
69. int TreeSize2(BTNode* root)
70. {
71.   return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right) + 1;
72. }
73. 
74. //求叶子结点个数
75. int TreeLeafSize(BTNode* root)
76. {
77.   if (root == NULL)
78.   {
79.     return 0;
80.   }
81. 
82.   if (root->left == NULL && root->right == NULL)
83.   {
84.     return 1;
85.   }
86. 
87.   return TreeLeafSize(root->left) + TreeLeafSize(root->right);
88. 
89. }
90. 
91. //求树的高度
92. int TreeDepth(BTNode* root)
93. {
94.   if (root == NULL)
95.   {
96.     return 0;
97.   }
98.   return fmax(TreeDepth(root->left), TreeDepth(root->right)) + 1;
99. }
100. 
101. //求第k层结点个数
102. int TreeKLeafSize(BTNode* root,int k)
103. {
104.  if (root == NULL)
105.  {
106.    return 0;
107.  }
108. 
109.  if (k == 1)
110.  {
111.    return 1;
112.  }
113. 
114.  return TreeKLeafSize(root->left, k - 1) + TreeKLeafSize(root->right, k - 1);
115. }
116. 
117. //查找树中值为x的节点
118. BTNode* TreeFind(BTNode* root, BTDataType x)
119. {
120.  if (root == NULL)
121.  {
122.    return NULL;
123.  }
124. 
125.  //自己不是
126.  if (root->data == x)
127.  {
128.    return root;
129.  }
130. 
131.  //到左子树中去找
132.  BTNode* lret = TreeFind(root->left, x);
133.  if (lret)
134.  {
135.    return lret;
136.  }
137. 
138.  //到右子树中去找
139.  BTNode* rret = TreeFind(root->right, x);
140.  if (rret)
141.  {
142.    return rret;
143.  }
144. 
145.  //左右两边都没有找到
146.  return NULL;
147. }
148. 
149. //二叉树销毁一级指针
150. void BinaryTreeDestroy1(BTNode* root)
151. {
152.  if (root == NULL)
153.  {
154.    return;
155.  }
156. 
157.  BinaryTreeDestroy1(root->left);
158.  BinaryTreeDestroy1(root->right);
159.  free(root);
160. }
161. 
162. //二叉树销毁二级指针
163. void BinaryTreeDestroy2(BTNode** pproot)
164. {
165.  if (*pproot == NULL)
166.  {
167.    return;
168.  }
169. 
170.  BinaryTreeDestroy2(&(*pproot)->left);
171.  BinaryTreeDestroy2(&(*pproot)->right);
172.  free(*pproot);
173.  *pproot = NULL;
174. }
175. 
176. //广度优先遍历
177. void TreeLevelOrder(BTNode* root)
178. {
179.  Queue q;
180.  QueueInit(&q);
181. 
182.  //入根结点
183.  if (root)
184.  {
185.    QueuePush(&q, root);
186.  }
187. 
188.  //出根，入左右孩子
189.  while (!QueueEmpty(&q))
190.  {
191.    BTNode* front = QueueFront(&q);
192.    QueuePop(&q);
193. 
194.    printf("%c ", front->data);
195.    if (front->left)
196.    {
197.      QueuePush(&q, front->left);
198.    }
199. 
200.    if (front->right)
201.    {
202.      QueuePush(&q, front->right);
203.    }
204.  }
205. 
206.  QueueDestroy(&q);
207. }
208. 
209. //判断二叉树是否是完全二叉树
210. bool BinaryTreeComplete(BTNode* root)
211. {
212.  Queue q;
213.  QueueInit(&q);
214.  if (root)
215.  {
216.    QueuePush(&q, root);
217.  }
218. 
219.  while (!QueueEmpty(&q))
220.  {
221. 
222.    BTNode* front = QueueFront(&q);
223.    //出根
224.    QueuePop(&q);
225. 
226.    //出的节点为空，跳出循环，准备判断队列后面还有没有非空结点
227.    if (front == NULL)
228.    {
229.      break;
230.    }
231. 
232.    //入左右孩子
233.    QueuePush(&q, front->left);
234.    QueuePush(&q, front->right);
235.  }
236. 
237.  //若队头结点即空结点的下一个结点非空，则不完全
238.  while (!QueueEmpty(&q))
239.  {
240.    BTNode* front = QueueFront(&q);
241.    QueuePop(&q);
242. 
243.    if (front)
244.    {
245.      return false;
246.    }
247.  }
248. 
249.  QueueDestroy(&q);
250.  return true;
251. }

046-test.c

1. #include"046-BinaryTree.h"
2. int main()
3. {
4.  BTNode* A = CreateTreeNode('A');
5.  BTNode* B = CreateTreeNode('B');
6.  BTNode* C = CreateTreeNode('C');
7.  BTNode* D = CreateTreeNode('D');
8.  BTNode* E = CreateTreeNode('E');
9.  BTNode* F = CreateTreeNode('F');
10. 
11.   A->left = B;
12.   A->right = C;
13.   B->left = D;
14.   C->left = E;
15.   C->right = F;
16. 
17.   //先序遍历
18.   PreOrder(A);//递归：1.子问题（根  左子树  右子树）  2.结束条件 
19.   printf("\n");
20. 
21.   //中序遍历
22.   InOrder(A);
23.   printf("\n");
24. 
25.   //后序遍历
26.   PostOrder(A);
27.   printf("\n");
28. 
29.   //求结点个数思路一调用
30.   int size = 0;
31.   TreeSize1(A, &size);
32.   printf("TreeSize = %d\n", size);
33. 
34.   //求结点个数思路二调用
35.   printf("TreeSize = %d\n", TreeSize2(A));
36. 
37.     //求叶子结点个数
38.   printf("TreeLeafSize = %d\n", TreeLeafSize(A));
39. 
40.   //求树的高度
41.   printf("TreeDepth = %d\n", TreeDepth(A));
42. 
43.   //第K层结点个数
44.   printf("TreeKLeafSize = %d\n", TreeKLeafSize(A, 3));
45. 
46.   //查找结点
47.   BTNode* ret = TreeFind(A, 'F');
48.   printf("TreeFind = %c\n", ret->data);
49. 
50.   //层序遍历
51.   TreeLevelOrder(A);
52. 
53.     printf("\n");
54. 
55.   //判断二叉树是不是完全二叉树
56.   printf("%d", BinaryTreeComplete(A));
57. 
58.   //二叉树销毁一级指针
59.   //BinaryTreeDestroy1(A);
60.   //A = NULL;
61. 
62.   //二叉树销毁二级指针
63.   BinaryTreeDestroy2(&A);
64. 
65. 
66. 
67.   return 0;
68. }
69.