• C语言二叉树详解

     

     

    文章目录

     

    概念

    一棵二叉树是结点的一个有限集合，该集合:
    1. 或者为空
    2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
    注意：
    1. 二叉树不存在度大于2的结点
    2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
    任意的二叉树都由下面几种情况组合而成：
    45d4a0f3f9db4a32b8447163aa03bcca.png

    二叉树中有两个非常特别的存在：

    1.满二叉树：

    一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
    说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

    2.完全二叉树：

    完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
    的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
    如图所示：
    a7ac267975934f77a698d6f345332f83.png

     

     

    一、二叉树的性质

    1. 若规定根节点的层数为1，则一棵非空二叉树的 第 i 层上最多有2^(i-1) 个结点.
    2. 若规定根节点的层数为1，则 深度为 h 的二叉树的最大结点数是2^h-1.
    3. 对任何一棵二叉树, 如果度为 0 其叶结点个数为 n0 , 度为 2 的分支结点个数为n2  , 则有
    n0 = n2+1
    4. 若规定根节点的层数为1，具有 n 个结点的满二叉树的深度， h= log(n+1). 
    5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：
    1. 若 i>0 ， i 位置节点的双亲序号： (i-1)/2；i=0，i为根节点编号，无双亲节点
    2. 若 2i+1 ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子
    3. 若 2i+2 ，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子

    二、实现二叉树

    二叉树我们是用链表实现的，下面是结构：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. typedef char BTDataType;
    7. typedef struct BTNode
    8. {
    9. 	BTDataType data;
    10. 	struct BTNode* left;
    11. 	struct BTNode* right;
    12. }BTNode;

    我们可以看到一个节点中有三个变量，一个存放数据，一个指向左子树，一个指向右子树。将char类型重命名是为了后面更方便的更改类型，将结构体重命名为BTNode是为了更简单的写出指针类型。 

    下面是实现的完整代码，然后我们依次进行讲解，在下面我们可以看到队列，这是因为二叉树的层序遍历和完全二叉树的判断用队列非常方便。

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. typedef char BTDataType;
    7. typedef struct BTNode
    8. {
    9. 	BTDataType data;
    10. 	struct BTNode* left;
    11. 	struct BTNode* right;
    12. }BTNode;
    13.  
    14. typedef BTNode* QueueDate;
    15. typedef struct QueueNode
    16. {
    17. 	struct QueueNode* next;
    18. 	QueueDate data;
    19. }QueueNode;
    20.  
    21. typedef struct Queue
    22. {
    23. 	QueueNode* head;
    24. 	QueueNode* tail;
    25. 	int size;
    26. }Queue;
    27.  
    28. QueueDate QueueFront(Queue* ps)
    29. {
    30. 	assert(ps);
    31. 	assert(ps->head);
    32. 	return ps->head->data;
    33. }
    34.  
    35. bool QueueEmpty(Queue* ps)
    36. {
    37. 	assert(ps);
    38. 	return ps->size == 0;
    39. }
    40.  
    41.  
    42. void QueuePop(Queue* ps)
    43. {
    44. 	assert(ps);
    45. 	assert(ps->head);
    46. 	if (ps->head->next == NULL)
    47. 	{
    48. 		free(ps->head);
    49. 		ps->head = ps->tail = NULL;
    50. 	}
    51. 	else
    52. 	{
    53. 		QueueNode* tmp = ps->head->next;
    54. 		free(ps->head);
    55. 		ps->head = tmp;
    56. 	}
    57. 	ps->size--;
    58. }
    59.  
    60. void QueuePush(Queue* ps, QueueDate x)
    61. {
    62. 	assert(ps);
    63. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    64. 	if (newnode == NULL)
    65. 	{
    66. 		perror("malloc:");
    67. 		exit(-1);
    68. 	}
    69. 	newnode->data = x;
    70. 	newnode->next = NULL;
    71. 	if (ps->head == NULL)
    72. 	{
    73. 		ps->head = ps->tail = newnode;
    74. 	}
    75. 	else
    76. 	{
    77. 		ps->tail->next = newnode;
    78. 		ps->tail = newnode;
    79. 	}
    80. 	ps->size++;
    81. }
    82.  
    83. void QueueDestroy(Queue* ps)
    84. {
    85. 	assert(ps);
    86. 	while (ps->head)
    87. 	{
    88. 		QueueNode* cur = ps->head->next;
    89. 		free(ps->head);
    90. 		ps->head = cur;
    91. 	}
    92. 	ps->head = ps->tail = NULL;
    93. 	ps->size = 0;
    94. }
    95.  
    96. void QueueInit(Queue* ps)
    97. {
    98. 	assert(ps);
    99. 	ps->head = NULL;
    100. 	ps->tail = NULL;
    101. 	ps->size = 0;
    102. }
    103. //二叉树的销毁
    104. void BinaryTreeDestroy(BTNode* root)
    105. {
    106. 	if (root == NULL)
    107. 	{
    108. 		return;
    109. 	}
    110. 	BinaryTreeDestroy(root->left);
    111. 	BinaryTreeDestroy(root->right);
    112. 	free(root);
    113. }
    114.  
    115. //二叉树的前序遍历
    116. void PrevOrder(BTNode* root)
    117. {
    118. 	if (root == NULL)
    119. 	{
    120. 		printf("NULL ");
    121. 		return;
    122. 	}
    123. 	printf("%c ", root->data);
    124. 	PrevOrder(root->left);
    125. 	PrevOrder(root->right);
    126. }
    127. //二叉树的中序遍历
    128. void middleOrder(BTNode* root)
    129. {
    130. 	if (root == NULL)
    131. 	{
    132. 		printf("NULL ");
    133. 		return;
    134. 	}
    135. 	middleOrder(root->left);
    136. 	printf("%c ", root->data);
    137. 	middleOrder(root->right);
    138. }
    139. //二叉树的后序遍历
    140. void AfterOrder(BTNode* root)
    141. {
    142. 	if (root == NULL)
    143. 	{
    144. 		printf("NULL ");
    145. 		return;
    146. 	}
    147. 	AfterOrder(root->left);
    148. 	AfterOrder(root->right);
    149. 	printf("%d ", root->data);
    150. }
    151. //二叉树的节点数
    152. int BinaryTreeSize(BTNode* root)
    153. {
    154. 	if (root == NULL)
    155. 	{
    156. 		return 0;
    157. 	}
    158. 	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
    159. }
    160. //二叉树的叶子节点数
    161. int BinaryTreeLeafSize(BTNode* root)
    162. {
    163. 	if (root == NULL)
    164. 	{
    165. 		return 0;
    166. 	}
    167. 	if (root->left == NULL && root->right == NULL)
    168. 	{
    169. 		return 1;
    170. 	}
    171. 	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
    172. }
    173.  
    174. //二叉树的高度
    175. int BinaryTreeHeight(BTNode* root)
    176. {
    177. 	if (root == NULL)
    178. 	{
    179. 		return 0;
    180. 	}
    181. 	int Left = BinaryTreeHeight(root->left);
    182. 	int right = BinaryTreeHeight(root->right);
    183. 	return Left > right ? Left + 1 : right + 1;
    184. }
    185. //二叉树第K层节点数
    186. int BinaryTreeKnode(BTNode* root,int k)
    187. {
    188. 	if (root == NULL)
    189. 	{
    190. 		return 0;
    191. 	}
    192. 	if (k == 1)
    193. 	{
    194. 		return 1;
    195. 	}
    196. 	return BinaryTreeKnode(root->left, k - 1) + BinaryTreeKnode(root->right, k - 1);
    197. }
    198. //二叉树查找值为x的节点
    199. BTNode* BinaryTree(BTNode* root,BTDataType x)
    200. {
    201. 	if (root == NULL)
    202. 	{
    203. 		return NULL;
    204. 	}
    205. 	if (root->data == x)
    206. 	{
    207. 		return root;
    208. 	}
    209. 	BTNode* left = BinaryTree(root->left, x);
    210. 	if (left)
    211. 	{
    212. 		return left;
    213. 	}
    214. 	BTNode* right = BinaryTree(root->right, x);
    215. 	if (right)
    216. 	{
    217. 		return right;
    218. 	}
    219. 	return NULL;
    220. }
    221. // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    222. BTNode* BinaryTreeCreate(BTDataType* str, int n, int* i)
    223. {
    224. 	if (str[*i] == '#')
    225. 	{
    226. 		(*i)++;
    227. 		return NULL;
    228. 	}
    229. 	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    230. 	newnode->data = str[(*i)++];
    231. 	newnode->left = BinaryTreeCreate(str, n, i);
    232. 	newnode->right = BinaryTreeCreate(str, n, i);
    233. 	return newnode;
    234. }
    235. //层序遍历
    236. void BinaryTreeLevelOrder(BTNode* root)
    237. {
    238. 	Queue sl;
    239. 	QueueInit(&sl);
    240. 	if (root)
    241. 	{
    242. 		QueuePush(&sl, root);
    243. 	}
    244. 	while (!QueueEmpty(&sl))
    245. 	{
    246. 		BTNode* tmp = QueueFront(&sl);
    247. 		QueuePop(&sl);
    248. 		printf("%d ", tmp->data);
    249. 		if (tmp->left)
    250. 		{
    251. 			QueuePush(&sl, tmp->left);
    252. 		}
    253. 		if (tmp->right)
    254. 		{
    255. 			QueuePush(&sl, tmp->right);
    256. 		}
    257. 	}
    258. 	printf("\n");
    259. 	QueueDestroy(&sl);
    260. }
    261. //判断是否为完全二叉树
    262. int BinaryTreeComplete(BTNode* root)
    263. {
    264. 	Queue sl;
    265. 	QueueInit(&sl);
    266. 	if (root)
    267. 	{
    268. 		QueuePush(&sl, root);
    269. 	}
    270. 	while (!QueueEmpty(&sl))
    271. 	{
    272. 		BTNode* tmp = QueueFront(&sl);
    273. 		QueuePop(&sl);
    274. 		if (tmp==NULL)
    275. 		{
    276. 			break;
    277. 		}
    278. 		else
    279. 		{
    280. 			QueuePush(&sl, tmp->left);
    281. 			QueuePush(&sl, tmp->right);
    282. 		}
    283. 	}
    284. 	while (!QueueEmpty(&sl))
    285. 	{
    286. 		BTNode* tmp = QueueFront(&sl);
    287. 		QueuePop(&sl);
    288. 		if (tmp)
    289. 		{
    290. 			QueueDestroy(&sl);
    291. 			return 0;
    292. 		}
    293. 	}
    294. 	QueueDestroy(&sl);
    295. 	return 1;
    296. }
    297.  
    298. int main()
    299. {
    300. 	/*BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
    301. 	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
    302. 	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
    303. 	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
    304. 	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
    305. 	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
    306. 	n1->data = 1;
    307. 	n2->data = 2;
    308. 	n3->data = 3;
    309. 	n4->data = 4;
    310. 	n5->data = 5;
    311. 	n6->data = 6;
    312. 	n1->left = n2;
    313. 	n1->right = n4;
    314. 	n2->left = n3;
    315. 	n2->right = n5;
    316. 	n3->left = NULL;
    317. 	n3->right = NULL;
    318. 	n4->left = n6;
    319. 	n4->right = NULL;
    320. 	n5->right = NULL;
    321. 	n5->left = NULL;
    322. 	n6->left = NULL;
    323. 	n6->right = NULL;*/
    324. 	/*PrevOrder(n1);
    325. 	printf("\n");
    326. 	middleOrder(n1);
    327. 	printf("\n");
    328. 	AfterOrder(n1);
    329. 	printf("\n");
    330. 	printf("%d\n", BinaryTreeSize(n1));
    331. 	printf("%d\n", BinaryTreeLeafSize(n1));
    332. 	printf("%d\n", BinaryTreeHeight(n1));
    333. 	printf("%d\n", BinaryTreeKnode(n1,1));
    334. 	BTNode* tmp = BinaryTree(n1, 10);
    335. 	if (tmp == NULL)
    336. 	{
    337. 		printf("tmp=NULL\n");
    338. 	}
    339. 	else
    340. 	{
    341. 		printf("tmp=%d\n", tmp->data);
    342. 	}*/
    343. 	/*BinaryTreeLevelOrder(n1);
    344. 	printf("%d\n", BinaryTreeComplete(n1));*/
    345. 	/*BinaryTreeDestroy(n1);*/
    346. 	char str[100];
    347. 	scanf("%s", str);
    348. 	int i = 0;
    349. 	BTNode* tmp = BinaryTreeCreate(str, 100, &i);
    350. 	middleOrder(tmp);
    351. 	printf("\n");
    352. 	PrevOrder(tmp);
    353. 	BinaryTreeDestroy(tmp);
    354. 	return 0;
    355. }

     先看第一个：二叉树遍历

    1.前序遍历：先遍历根 然后是左子树 然后是右子树

    1. void PrevOrder(BTNode* root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		printf("NULL ");
    6. 		return;
    7. 	}
    8. 	printf("%c ", root->data);
    9. 	PrevOrder(root->left);
    10. 	PrevOrder(root->right);
    11. }

     6713c36ddd2e40f28a6518038966c990.png

    如图所示，在递归的过程中，第一个节点为1，1不为空打印1然后递归1的左子树，1的左子树为2，不为空打印2，然后递归2的左子树，2的左子树为空打印NULL然后返回刚刚2的那个函数，2的左子树已经递归了所以该2的右子树，2的右子树为空打印NULL然后返回2的函数，2的函数执行完了返回1的函数，这时候1的左子树递归完成了，现在递归1的右子树，这里与1的左子树递归出来是一样的，然后成功用前序遍历出这棵树。后面的中序遍历就是先去遍历左子树不打印，然后左子树遍历完了在打印节点然后再去遍历右子树。

    2.中序遍历：先遍历左子树，然后遍历根，再遍历右子树

    1. void middleOrder(BTNode* root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		printf("NULL ");
    6. 		return;
    7. 	}
    8. 	middleOrder(root->left);
    9. 	printf("%c ", root->data);
    10. 	middleOrder(root->right);
    11. }

     d7b288fced8e485d9fb245c416f49c96.png

     与前序相同就不再讲述。

    3.后序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。

    1. void AfterOrder(BTNode* root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		printf("NULL ");
    6. 		return;
    7. 	}
    8. 	AfterOrder(root->left);
    9. 	AfterOrder(root->right);
    10. 	printf("%d ", root->data);
    11. }

     第二个：求二叉树的节点数

    1. int BinaryTreeSize(BTNode* root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return 0;
    6. 	}
    7. 	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
    8. }

     求二叉树的节点很简单，当这个节点为空时就返回0否则就返回这个节点的左子树的节点加右子树的节点再加自己。单靠代码可能不好看出来，那么我们画个图看看。

    e7188b80d53a4fd58565b393b96fd2ee.png

    相信大家也看懂这个图了，本质就是计算一个节点的左子树的节点+右子树的节点再加自己。

    第三个：求二叉树的叶子节点数

    叶子节点我们在上篇已经讲过，就是度为0的节点。我们从这个角度出发，度为0就是左子树为空并且右子树为空，所以只需要将上面的代码稍微修改即可。

    1. int BinaryTreeLeafSize(BTNode* root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return 0;
    6. 	}
    7. 	if (root->left == NULL && root->right == NULL)
    8. 	{
    9. 		return 1;
    10. 	}
    11. 	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
    12. }

     在这里一定要注意，当树为空要返回0否则就是死递归。下面是递归图：

    5bb98628e8f34e1980227cd3556f40e7.png

     我们可以看到求叶子节点的递归非常简单，只需要记得当树为空返回0，如果没有这个条件当一棵树或者一个节点只有左边没有右边时就会死递归。

    第四个：求树的高度

    1. int BinaryTreeHeight(BTNode* root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return 0;
    6. 	}
    7. 	int Left = BinaryTreeHeight(root->left);
    8. 	int right = BinaryTreeHeight(root->right);
    9. 	return Left > right ? Left + 1 : right + 1;
    10. }

     求树的高度只需要看一棵树中它的左子树高还是右子树高，我们返回高的那个然后再加上根的一层就是总高度，当一样高时随便返回一颗子树的高度即可。在这里需要注意的是一定要用两个值去分别记录左右子树的高度，否则效率非常差每一层递归都要重新计算高度。

    b0e4390328fc4e93915d530baaea9f44.png

    如递归图所示当有变量记录其左右高度时会比直接递归快很多。

    第五个：求第K层节点数

    1. int BinaryTreeKnode(BTNode* root,int k)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return 0;
    6. 	}
    7. 	if (k == 1)
    8. 	{
    9. 		return 1;
    10. 	}
    11. 	return BinaryTreeKnode(root->left, k - 1) + BinaryTreeKnode(root->right, k - 1);
    12. }

    怎么求第K层节点数呢？我们发现当我们要求一棵树的第三层时，从根节点的角度看是第三层，从第二层的角度看是第二层，从第三层的角度看是第一层，也就是说每次都可以转化为这个节点的左子树的K-1层的节点+这个节点的右子树的K-1层节点，当K=1也就是自己就是第一层时那么只有自己一个节点，所以返回1即可。

    c4192d8a1aff4636a910181e29737d70.png

    第六个：二叉树查找值为x的节点

    1. BTNode* BinaryTree(BTNode* root,BTDataType x)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return NULL;
    6. 	}
    7. 	if (root->data == x)
    8. 	{
    9. 		return root;
    10. 	}
    11. 	BTNode* left = BinaryTree(root->left, x);
    12. 	if (left)
    13. 	{
    14. 		return left;
    15. 	}
    16. 	BTNode* right = BinaryTree(root->right, x);
    17. 	if (right)
    18. 	{
    19. 		return right;
    20. 	}
    21. 	return NULL;
    22. }

     查找值为x的节点我们要考虑几个问题，第一个是如果找到了这个节点能否直接返回，第二个是当找不到的时候要返回空指针，当这个节点为空时也要返回空指针，我们在递归的过程中一定要保证每一个都有返回值。在这里当我们找到这个节点时为什么要用变量保存呢？因为当我们找到这个节点后我们应该要函数直接返回而不是继续去递归它的左右子树。

    5e5c4498e732443f80841290c42465ce.png

    通过递归图我们可以看到每次找到节点后返回这个节点必须要有变量去保存这个节点，否则就白找了，并且通过判断变量是否为空的情况就可以知道有没有找到，当任意一个变量不为空时直接返回了找到的这个节点就不会去递归其他的节点。 

    第七个：通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

    这个其实是牛客网的一道题，就是通过前序遍历来让一个字符串被二叉树存储。

    1. BTNode* BinaryTreeCreate(BTDataType* str, int n, int* i)
    2. {
    3. 	if (str[*i] == '#')
    4. 	{
    5. 		(*i)++;
    6. 		return NULL;
    7. 	}
    8. 	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    9. 	newnode->data = str[(*i)++];
    10. 	newnode->left = BinaryTreeCreate(str, n, i);
    11. 	newnode->right = BinaryTreeCreate(str, n, i);
    12. 	return newnode;
    13. }

     如图当遇到字符#时，就是空指针，str是传来的字符串，i是记录字符串位置的下标，在这里一定要注意此函数要传下标的地址，因为我们在递归的过程中i会++如果不是传地址的话每次递归后的i++后对上一次函数栈帧不起作用，我们通过递归图来演示。

    1. int main()
    2. {
    3.     char str[100];
    4. 	scanf("%s", str);
    5. 	int i = 0;
    6. 	BTNode* tmp = BinaryTreeCreate(str, 100, &i);
    7.     return 0;
    8. }

     a36ae4fab0d54aea9d28f33a238500a8.png

    如图所示当走完全部字符串后返回二叉树的根节点，这样就创建好了一颗二叉树。在这里要注意的是不管遇到空指针还是正常字符都需要让下标I++。在这里我们开辟的空间到最后结束程序都要记得销毁。

    第八个：销毁二叉树

    1. void BinaryTreeDestroy(BTNode* root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return;
    6. 	}
    7. 	BinaryTreeDestroy(root->left);
    8. 	BinaryTreeDestroy(root->right);
    9. 	free(root);
    10. }

     销毁二叉树同样需要递归来实现，我们只需要先找到左子树最后一个节点然后依次销毁即可。在这里需要注意的是当这个节点为空时，一定要返回。

    527b72974930474697fc6684372764d4.png

    第九个：二叉树的层序遍历

    1. void BinaryTreeLevelOrder(BTNode* root)
    2. {
    3. 	Queue sl;
    4. 	QueueInit(&sl);
    5. 	if (root)
    6. 	{
    7. 		QueuePush(&sl, root);
    8. 	}
    9. 	while (!QueueEmpty(&sl))
    10. 	{
    11. 		BTNode* tmp = QueueFront(&sl);
    12. 		QueuePop(&sl);
    13. 		printf("%d ", tmp->data);
    14. 		if (tmp->left)
    15. 		{
    16. 			QueuePush(&sl, tmp->left);
    17. 		}
    18. 		if (tmp->right)
    19. 		{
    20. 			QueuePush(&sl, tmp->right);
    21. 		}
    22. 	}
    23. 	printf("\n");
    24. 	QueueDestroy(&sl);
    25. }

    层序遍历我们是用队列实现的，先将根节点入队列，每次出队头元素前都需要将这个节点的左右子树入队列。当队列为空说明所有节点都遍历完了，直接销毁队列即可。

    d4a463efcaeb43f9b14ccf5b3c9f93a9.png 

     当然每次入队列我们是不会入空树的因为层序遍历就是每层从左到右根的遍历。每次用一个变量去保存队列头元素，这样方便出队列和入队列。入节点的子树的时候每次左右子树不为空再入队列。在这里要说明一下，队列里保存的是二叉树结构体的指针而不是节点，如果保存的是节点就会出错。如下面代码要保存树的节点的地址。

    1. typedef BTNode* QueueDate;
    2. typedef struct QueueNode
    3. {
    4. 	struct QueueNode* next;
    5. 	QueueDate data;
    6. }QueueNode;

    第十个：判断是不是完全二叉树

    完全二叉树可以在最后一个节点只有左子树，但一定不会在已经有空树的后面还有节点如下图所示：

    58d02ff98f57436d92b70669582400a5.png

    如图所示，非完全二叉树有空节点后后面还会有节点，而完全二叉树在某一个节点为空时它的右边全是空节点，依据这个特性我们就很容易的判断一棵树是否为完全二叉树。

    1. int BinaryTreeComplete(BTNode* root)
    2. {
    3. 	Queue sl;
    4. 	QueueInit(&sl);
    5. 	if (root)
    6. 	{
    7. 		QueuePush(&sl, root);
    8. 	}
    9. 	while (!QueueEmpty(&sl))
    10. 	{
    11. 		BTNode* tmp = QueueFront(&sl);
    12. 		QueuePop(&sl);
    13. 		if (tmp==NULL)
    14. 		{
    15. 			break;
    16. 		}
    17. 		else
    18. 		{
    19. 			QueuePush(&sl, tmp->left);
    20. 			QueuePush(&sl, tmp->right);
    21. 		}
    22. 	}
    23. 	while (!QueueEmpty(&sl))
    24. 	{
    25. 		BTNode* tmp = QueueFront(&sl);
    26. 		QueuePop(&sl);
    27. 		if (tmp)
    28. 		{
    29. 			QueueDestroy(&sl);
    30. 			return 0;
    31. 		}
    32. 	}
    33. 	QueueDestroy(&sl);
    34. 	return 1;
    35. }

    我们继续用队列实现，这次空节点也要入队列，当队列的头变成空节点时我们出队列并且退出循环，当队列不为空时我们继续拿队头元素，一旦这个元素不是空节点就说明不是完全二叉树，当队列全部出完也没有遇到非空的节点时，那么就说明这棵树为完全二叉树。

    总结

    二叉树最重要的就是递归，要深刻的理解递归过程就必须要多画图，只要理解了递归那么再去写二叉树就手到擒来了。

     

     

  • 相关阅读:
    数组的赋值
    Centos 7部署sysbench测试Opengauss/MogDB性能
    想要精通算法和SQL的成长之路 - 简化路径
    C语言- 基础数据结构和算法 - 09 栈的应用_中缀表达式转后缀表达式20220611
    2年半经验，2 本学历，竟给 30K，我的美团 Offer 终于来了
    模拟登陆系统
    Spring整合RabbitMQ
    shell 位置参数变量
    C++之打印编译全过程(二百一十四)
    基于边缘物联网关的智慧零售应用方案
  • 原文地址：https://blog.csdn.net/Sxy_wspsby/article/details/128161174