devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

平衡二叉树 C语言代码实现

作者：你好赵伟 | 2024-05-27 13:04:50

赞

踩

平衡二叉排序树代码

    关注、星标公众号，直达精彩内容

8d9b2fe783cc96211a7f8629f1f64a30.png

来源： https://www.cnblogs.com/NoneID

整理：李肖遥

1. 什么是平衡二叉树

平衡二叉树，我们也称【二叉平衡搜索树/AVL】,树中任何节点的两个子树的高度最大差别为1，巴拉巴拉。。。(https://baike.baidu.com/item/AVL树/10986648?fr=aladdin)

但是有个注意的点: 平衡二叉树的前提是 二叉排序树(https://baike.baidu.com/item/二叉搜索树/7077855?fr=aladdin)

这篇博客主要总结平衡二叉树，所以，二叉排序树知识不会提及，但是会用到。

如果想要看 排序二叉树调整为 平衡二叉树 旋转相关内容的，调整至 第5节。

平衡二叉树

b64583b3cce4556aa23f42a4b6ad26e6.png

非平衡二叉树

最小不平衡子树节点为 130

左子树深度为 1，右子树深度为3 ，其差值大于1，所以不平衡

dcc3aa4b828f38918eebfa0cb7515b65.png

2. 如何判断二叉树最小不平衡子树

最小不平衡子树为 130 这颗子树(黄色标注)

da8f14c8fc8a0061f77e7169ffd62050.png

判定最小不平衡子树的关键就在于，判断 这棵树的左子树 和 右字数 深度之差是否大于1，若大于1 ，则证明该树不平衡

检查二叉树是否平衡函数代码实现

  1. typedef struct {
  2.         int data; // 数据节点
  3.         struct TreeNode *left; // 指向左子树
  4.         struct TreeNode *right; // 指向右子树
  5. } TreeNode , *PTreeNode;
  6.  
  7. // 记录平衡二叉树
  8. bool BalanceTrue = false;
  9. // 最小不平衡子树地址
  10. TreeNode *rjt = NULL;
  11.  
  12. // 检查二叉树是否平衡，若不平衡 BalanceTrue 为 true
  13. int checkTreeBalance(TreeNode *root) {
  14.         if (NULL == root) { return 0; }
  15.         int x = checkTreeBalance(root->left);
  16.         int y = checkTreeBalance(root->right);
  17.  
  18.         // 若检测到最小不平衡二叉树后，不进行后面的检查
  19.         if (BalanceTrue) return 0;
  20.     
  21.         int xx = abs(x-y);
  22.  
  23.         if (xx > 1) {
  24.                 // 左子树 和 右子树 相差大于1 ， 二叉树不平衡
  25.                 BalanceTrue = true;
  26.                 rjt = root;
  27.         }
  28.          
  29.         return (x>y?x+1:y+1);
  30. }

程序执行结果

  1. # gcc -w -g -std=c11 BalanceTree.c 
  2. # 
  3. # ./a.out 
  4. 当前二叉树遍历
  5. 前序遍历: 580    130     80      160     150     158     210     1590    900     2100    1900
  6. 中序遍历: 80     130     150     158     160     210     580     900     1590    1900    2100
  7. 二叉树不平衡，不平衡子树根节点为: 130
  8. #

3. 二叉树不平衡情况

在一颗平衡二叉树的前提下，插入和删除一个节点，都有可能会引起二叉树不平衡，不平衡的情况主要有以下四种

左左更高

9b27fb9d13bac586ada905053b889c5a.png

左右更高

177f9a2e9f1241220118cbffe08999ab.png

右左更高

7554f1d6eb4020f74125726f3fa19013.png

右右更高

e2af5a9259b569dc185ab3cb58d0b624.png

4. 判断不平衡二叉树哪边高

3257489a8fdde4398da155f3faf211e6.png

16b074aa021e6882a61c661a89f8f495.png

如上图红色所示，可以先根据最小不平衡二叉树左子树或者右子树高，上图所示，为右子树高，则将最小不平衡二叉树的右子树作为树根节点，继续判断子树的左子树或者右子树高。
比如上图的结果是右左较高，若进行调整的话，为 先让不平衡子树右节点的树先向右旋转，然后再向左旋转。

判断不平衡二叉树哪边高代码实现

  1. typedef struct {
  2.         int data; // 数据节点
  3.         struct TreeNode *left; // 指向左子树
  4.         struct TreeNode *right; // 指向右子树
  5. } TreeNode , *PTreeNode;
  6.  
  7. // 记录平衡二叉树
  8. bool BalanceTrue = false;
  9. // 最小不平衡子树地址
  10. TreeNode *rjt = NULL;
  11.  
  12. // 返回二叉树树高
  13. int treeHeight(TreeNode *root) {
  14.         if (NULL == root) return 0;
  15.         int ll = treeHeight(root->left);
  16.         int rr = treeHeight(root->right);
  17.         return (ll>rr?ll+1:rr+1);
  18. }
  19.  
  20. int main() {
  21.     /*  构建二叉树
  22.     	判断平衡，获取最小不平衡子树， 将数据存入 rjt 中
  23.     	输出二叉树 前序/中序
  24.     */
  25.     if (BalanceTrue) {
  26.         printf("二叉树不平衡，不平衡子树根节点为: %d\n",rjt->data);
  27.     } else {
  28.         return 0;
  29.     };
  30.  
  31.  
  32.     int ll = treeHeight(rjt->left);
  33.     int rr = treeHeight(rjt->right);
  34.     if (1 < ll - rr) {
  35.         printf("左子树高\n");
  36.         TreeNode *rjt_ll = rjt->left;
  37.  
  38.         int child_ll = treeHeight(rjt_ll->left);
  39.         int child_rr = treeHeight(rjt_ll->right);
  40.         if (child_ll > child_rr) {
  41.             printf("左子树更高\n");
  42.         } else if (child_rr > child_ll) {
  43.             printf("右字数更高");
  44.         }
  45.  
  46.     } else if (1 <  rr - ll) {
  47.         printf("右子数高\n");
  48.         TreeNode *rjt_rr = rjt->right;
  49.  
  50.         int child_ll = treeHeight(rjt_rr->left);
  51.         int child_rr = treeHeight(rjt_rr->right);
  52.         if (child_ll > child_rr) {
  53.             printf("左子树更高\n");
  54.         } else if (child_rr > child_ll) {
  55.             printf("右字数更高");
  56.         }
  57.  
  58.     }
  59.  
  60.     return 0;
  61. }

输出

  1. # gcc BalanceTree.c -w -g -std=c11
  2. # 
  3. # ./a.out 
  4. 当前二叉树遍历
  5. 前序遍历:130    80      160     150     158     210
  6. 中序遍历:80     130     150     158     160     210
  7. 二叉树不平衡，不平衡子树根节点为: 130
  8. 右子数高
  9. 左子树更高
  10. #

5. 如何调整平衡二叉树

所谓的旋转，其实是修改指针指向的值，仅此而已。

二叉树不平衡有四种情况

左左更高

原始二叉树，若要调整为平衡二叉树，需要整棵树向右旋转

0492602ec98d6ec79902b3b3b61a3fb7.png

调整1:整棵树向右旋转

39a9121ef08a5d9d9d5d6f2a6c4acb18.png

左右更高

原始二叉树，若要调整为平衡二叉树，需要 先让不平衡子树左节点先向左旋转，然后再向右旋转

4ef34bbc812afe2f2aa1c429040707ff.png

调整1: 先让不平衡子树左节点的树先向左旋转

4c3ce0bdc50d961e33620b288f03bc84.png

调整2: 整棵树向右

0f9a3039625175647870bd735706e8f2.png

右左更高

原始二叉树，若要调整为平衡二叉树，需要 先让不平衡子树右节点的树先向右旋转，然后再向左旋转

174bbbbbf2b44a1bf6e91c6f5a0a46e1.png

调整1: 先让不平衡子树右节点的树先向右旋转

e634c931e1515a6caae92edfd1379129.png

调整2: 整棵树向左

34032edb8d854743ffd993acf1a875fd.png

右右更高

原始二叉树，若要调整为平衡二叉树，需要 整棵树向左旋转

b12228ef9f702850280f3ce64f6bc0e6.png

调整1: 整棵树向左旋转

ed8a260be2583f74dc6041df2c41cf47.png

全部代码

  1. # include <stdio.h>
  2. # include <stdbool.h>
  3. # include <stdlib.h>
  4. # include <math.h>
  5.  
  6. typedef struct {
  7. 	int data; // 数据节点
  8. 	struct TreeNode *left; // 指向左子树
  9. 	struct TreeNode *right; // 指向右子树
  10. } TreeNode , *PTreeNode;
  11.  
  12. // 记录平衡二叉树
  13. bool BalanceTrue = false;
  14. // 最小不平衡子树地址
  15. TreeNode *rjt = NULL;
  16.  
  17. // 检查二叉树是否平衡，若不平衡 BalanceTrue 为 true
  18. int checkTreeBalance(TreeNode *root) {
  19. 	if (NULL == root) { return 0; }
  20. 	int x = checkTreeBalance(root->left);
  21. 	int y = checkTreeBalance(root->right);
  22. 	
  23. 	// 若检测到最小二叉树后，不进行后面的检查
  24. 	if (BalanceTrue) return 0;
  25. 	int xx = abs(x-y);
  26.  
  27. 	if (xx > 1) {
  28. 		// 左子树 和 右子树 相差大于1 ， 二叉树不平衡
  29. 		BalanceTrue = true;
  30. 		rjt = root;
  31. 	}
  32. 	 
  33. 	return (x>y?x+1:y+1);
  34. }
  35.  
  36. // 返回二叉树树高
  37. int treeHeight(TreeNode *root) {
  38. 	if (NULL == root) return 0;
  39. 	int ll = treeHeight(root->left);
  40. 	int rr = treeHeight(root->right);
  41. 	return (ll>rr?ll+1:rr+1);
  42. }
  43.  
  44. // 父节点查询
  45. TreeNode* queryTopData(TreeNode *root,int data) {
  46. 	// 空地址异常抛出
  47. 	if (NULL == root) return NULL;
  48. 	
  49. 	// top: 父节点 ，如果为Null, 该节点为父节点
  50. 	// tmp: 遍历查询节点 
  51. 	TreeNode *top = NULL;
  52. 	TreeNode *tmp = root;
  53.  
  54. 	while (tmp != NULL) {
  55. 		if (data == tmp->data) {
  56. 			// 节点为 返回Null
  57. 			if (NULL == top) return NULL;
  58. 			return top;
  59. 		}
  60.  
  61. 		top = tmp;
  62. 		if (data > tmp->data) {
  63. 			tmp = tmp->right;
  64. 		} else if (data < tmp->data) {
  65. 			tmp = tmp->left;
  66. 		}
  67. 	}
  68. 	return NULL;
  69. }
  70.  
  71. // 左左旋转
  72. //
  73. // 不平衡二叉树
  74. //       70
  75. //      /   \
  76. //    50    80
  77. //   /  \    
  78. //  40  60
  79. //  /
  80. // 30
  81. //
  82. // 旋转后平衡二叉树(向右旋转)
  83. //
  84. //    50
  85. //  /   \
  86. // 40    70
  87. // /     /  \
  88. //30   60    80
  89. //
  90. bool turnLL(TreeNode **root , TreeNode *notBalanceRoot) {
  91. 	
  92. 	if ((*root) != notBalanceRoot) {
  93. 		printf("左左旋转,非根节点\n");
  94. 		// 非根节点
  95. 		TreeNode *lleft = notBalanceRoot->left;
  96. 		TreeNode *lright = lleft->right;
  97. 		
  98. 		// 查找父节点
  99. 		TreeNode *fdata = queryTopData((*root),notBalanceRoot->data);
  100. 		if (NULL == fdata) return false;
  101.  
  102. 		lleft->right = notBalanceRoot;
  103. 		notBalanceRoot->left = lright;
  104. 		
  105. 		if (notBalanceRoot == fdata->left) {
  106. 			fdata->left = lleft;
  107. 		} else if (notBalanceRoot == fdata->right) {
  108. 			fdata->right = lleft;
  109. 		}
  110. 		return true;
  111.  
  112. 	} else {
  113. 		// 根节点
  114. 		printf("左左旋转,是根节点\n");
  115. 		TreeNode *lleft = notBalanceRoot->left;
  116. 		TreeNode *absroot = lleft;
  117. 		TreeNode *lright = lleft->right;
  118. 		
  119.  
  120. 		lleft->right = notBalanceRoot;
  121. 		notBalanceRoot->left = lright;
  122.  
  123. 		(*root) = absroot;
  124. 		return true;
  125. 	}
  126.  
  127. }
  128.  
  129. // 左右旋转
  130. //不平衡二叉树
  131. //      70
  132. //     /   \
  133. //    50    80
  134. //    / \    
  135. //   40 60
  136. //  /   
  137. // 55
  138. //
  139. //左子树向左
  140. //      70
  141. //     /   \
  142. //    60    80
  143. //    /
  144. //   50
  145. //  /  \    
  146. // 40  55
  147. //                                                           
  148. //                                                                   
  149. // 整棵树向右
  150. // 
  151. //     60
  152. //    /   \
  153. //   50    70
  154. //  /  \     \
  155. // 40  55    80
  156. //
  157. bool turnLR(TreeNode **root , TreeNode *notBalanceRoot) {
  158. 	if ((*root) != notBalanceRoot) {
  159. 		printf("左右旋转，非根节点");
  160. 		
  161. 		TreeNode *lleft = notBalanceRoot->left;
  162. 		TreeNode *leftRight = lleft->right;
  163. 		TreeNode *leftRightLeft = leftRight->left;
  164.  
  165. 		// 第一次调整
  166. 		leftRight->left = lleft;
  167. 		lleft->right = leftRightLeft;
  168. 		notBalanceRoot->left = leftRight;
  169.  
  170.  
  171. 		// 查找父节点
  172. 		TreeNode *fdata = queryTopData((*root),notBalanceRoot->data);
  173. 		//if (NULL != fdata) printf("fdata: %d\n",fdata->data);
  174. 		
  175. 		// 第二次调整
  176. 		lleft = notBalanceRoot->left;
  177. 		leftRight = lleft->right;
  178. 		
  179. 		lleft->right = notBalanceRoot;
  180. 		notBalanceRoot->left = leftRight;
  181.  
  182. 		
  183. 		if (notBalanceRoot == fdata->left) {
  184. 			fdata->left = lleft;
  185. 		} else if (notBalanceRoot == fdata->right) {
  186. 			fdata->right = lleft;
  187. 		}
  188. 	} else {
  189. 		printf("左右旋转，是根节点\n");
  190.  
  191. 		TreeNode *lleft = notBalanceRoot->left;
  192. 		TreeNode *leftRight = lleft->right;
  193. 		TreeNode *leftRightLeft = leftRight->left;
  194.  
  195. 		// 第一次调整
  196. 		leftRight->left = lleft;
  197. 		lleft->right = leftRightLeft;
  198. 		notBalanceRoot->left = leftRight;
  199. 		
  200. 		// 第二次调整
  201. 		lleft = notBalanceRoot->left;
  202. 		leftRight = lleft->right;
  203. 		
  204. 		lleft->right = notBalanceRoot;
  205. 		notBalanceRoot->left = leftRight;
  206.  
  207. 		(*root) = lleft;
  208. 	}
  209. }
  210.  
  211. // 右左旋转
  212. //不平衡二叉树
  213. //   70
  214. //  /  \
  215. // 50   80
  216. //     /  \
  217. //    75  88
  218. //     \
  219. //     77
  220. //
  221. //左子树向右
  222. //   70
  223. //  /  \
  224. // 50   75
  225. //     /  \
  226. //    77  80
  227. //         \
  228. //         88
  229. //                                                                                                           
  230. //                                                                                                                  
  231. //                                                                                                                      
  232. //整棵树向左
  233. //     75
  234. //    /  \
  235. //   70  80
  236. //  /  \   \ 
  237. // 50  77  88 
  238. //
  239. bool turnRL(TreeNode **root , TreeNode *notBalanceRoot) {
  240. 	TreeNode *rright = notBalanceRoot->right;
  241. 	TreeNode *rightLeft = rright->left;
  242. 	TreeNode *rightLeftRight = rightLeft->right;
  243.  
  244. 	// 第一次调整
  245. 	rightLeft->right = rright;
  246. 	rright->left = rightLeftRight;
  247. 	notBalanceRoot->right = rightLeft;
  248.  
  249. 	// 查找父节点
  250. 	TreeNode *fdata = queryTopData((*root),notBalanceRoot->data);
  251. 	//if (NULL != fdata) printf("fdata: %d\n",fdata->data);
  252.  
  253. 	// 第二次调整
  254. 	rright = notBalanceRoot->right;
  255. 	rightLeft = rright->left;
  256.  
  257. 	rright->left = notBalanceRoot;
  258. 	notBalanceRoot->right = rightLeft;
  259.  
  260. 	if ((*root) != notBalanceRoot) {
  261. 		printf("右左旋转，非根节点\n");
  262. 		if (notBalanceRoot == fdata->left) {
  263. 			fdata->left = rright;
  264. 		} else if (notBalanceRoot == fdata->right) {
  265. 			fdata->right = rright;
  266. 		}
  267. 	
  268. 	} else {
  269. 		printf("右左旋转，是根节点\n");
  270. 		(*root) = rright;
  271. 	}
  272. }
  273.  
  274. // 右右旋转
  275. // 
  276. // 不平衡二叉树
  277. //  70
  278. // /  \
  279. //50   80
  280. //    /  \
  281. //   75  88
  282. //      /
  283. //     85
  284. //
  285. //
  286. //
  287. //向左旋转
  288. //    80
  289. //   /  \
  290. //  70   88
  291. // /  \   /  
  292. //50  75 85  
  293. bool turnRR(TreeNode **root , TreeNode *notBalanceRoot) {
  294. 	if ((*root) != notBalanceRoot) {
  295. 		printf("右右旋转,非根节点");
  296. 		TreeNode *rright = notBalanceRoot->right;
  297. 		TreeNode *rleft = rright->left;
  298.  
  299. 		// 查找父节点
  300. 		TreeNode *fdata = queryTopData((*root),notBalanceRoot->data);
  301. 		if (NULL != fdata) printf("fdata: %d\n",fdata->data);
  302.  
  303.                 rright->left = notBalanceRoot;
  304.                 notBalanceRoot->right = rleft;
  305.  
  306.                 if (notBalanceRoot == fdata->left) {
  307.                         fdata->left = rright;
  308.                 } else if (notBalanceRoot == fdata->right) {
  309.                         fdata->right = rright;
  310.                 }				
  311.  
  312. 	} else {
  313. 		// 右右旋转，是根节点
  314. 		printf("右右旋转,是根节点\n");
  315. 		TreeNode *rright = notBalanceRoot->right;
  316. 		TreeNode *absroot = rright;
  317. 		TreeNode *rleft = rright->left;
  318.  
  319. 		rright->left = notBalanceRoot;
  320. 		notBalanceRoot->right = rleft;
  321.  
  322. 		(*root) = absroot;
  323.  
  324. 	}
  325. }
  326.  
  327. // 二叉树前序遍历
  328. void Print1(TreeNode *root) {
  329. 	if (NULL == root) return;
  330. 	printf("%d\t",root->data);
  331. 	Print1(root->left);
  332. 	Print1(root->right);
  333. }
  334.  
  335. // 二叉树中序遍历
  336. void Print2(TreeNode *root) {
  337. 	if (NULL == root) return;
  338. 	Print2(root->left);
  339. 	printf("%d\t",root->data);
  340. 	Print2(root->right);
  341. }
  342.  
  343. // 二叉树后续遍历
  344. void Print3(TreeNode *root) {
  345. 	if (NULL == root) return;
  346. 	Print3(root->left);
  347. 	Print3(root->right);
  348. 	printf("%d\t",root->data);
  349. }
  350.  
  351. // 插入二叉树节点
  352. TreeNode* addNode(TreeNode *root,int data) {
  353. 	if (NULL == root) {
  354. 		// 头节点插入
  355. 		TreeNode *Node = (TreeNode *)malloc(sizeof(TreeNode));
  356. 		if (NULL == Node) {
  357. 			printf("新节点申请内存失败\n");
  358. 			return NULL;
  359. 		}
  360. 		Node->data = data;
  361.  
  362. 		return Node;
  363. 	}
  364.  
  365. 	TreeNode *tmp = root;
  366. 	TreeNode *top = NULL;
  367.  
  368. 	// 找到合适的最尾巴节点
  369. 	while (NULL != tmp) {
  370. 		top = tmp;
  371. 		if (tmp->data == data) {
  372. 			printf("已经存在该节点，节点地址: %p\n",tmp);
  373. 			return root;
  374. 		}
  375. 		if (tmp->data < data) {
  376. 			tmp = tmp->right;
  377. 		} else if (tmp->data > data) {
  378. 			tmp = tmp->left;
  379. 		}
  380. 	}
  381.  
  382. 	TreeNode *Node = (TreeNode *)malloc(sizeof(TreeNode));
  383. 	Node->data = data;
  384. 	if (NULL == Node) {
  385. 		printf("申请新节点内存失败\n");
  386. 		return root;
  387. 	}
  388.  
  389. 	// 链接节点
  390. 	if (data > top->data) {
  391. 		top->right = Node;
  392. 	} else if (data < top->data) {
  393. 		top->left = Node;
  394. 	}
  395.  
  396. 	return root;
  397. }
  398.  
  399.  
  400. // 删除二叉排序树节点
  401. bool DeleteTreeNode(TreeNode **TreeRoot,int data) {
  402. 	if (NULL == (*TreeRoot)) return false;
  403.  
  404. 	printf("删除节点: %d\n",data);
  405.  
  406. 	TreeNode *tmp = (*TreeRoot);
  407. 	TreeNode *top = NULL;
  408. 	
  409. 	while (tmp != NULL) {
  410. 		if (tmp->data == data) {
  411. 			// 叶子节点
  412. 			if ((NULL == tmp->left) && (NULL == tmp->right)) {
  413. 				// 叶子节点
  414. 				if (NULL == top) {
  415. 					// 仅有根节点的叶子节点
  416. 					free(tmp);
  417. 					return true;
  418. 				} else {
  419. 					// 其他的叶子节点
  420. 					TreeNode *lastNode = top;
  421. 					if (tmp == lastNode->left) {
  422. 						lastNode->left = NULL;
  423. 					} else if (tmp == lastNode->right) {
  424. 						lastNode->right = NULL;
  425. 					}
  426. 					free(tmp);
  427. 					return true;
  428. 				}
  429. 			} else {
  430. 				// 非叶子节点
  431. 				// 算法为: 
  432. 				// 默认算法为: 1.  当删除该节点时，获取该树右子树最左子节点
  433. 				//             2.  当右子树为空时，此时应该获取左子树最右端子节点
  434.  
  435. 				if (NULL != tmp->right) {
  436. 					// 方案 1
  437. 					TreeNode *tmp2 = tmp->right;
  438. 					TreeNode *top2 = NULL;
  439.  
  440. 					// 找到最后一个节点
  441. 					while (tmp2->left != NULL) {
  442. 						top2 = tmp2;
  443. 						tmp2 = tmp2->left;
  444. 					}
  445.  
  446. 					// 删除老的节点
  447. 					tmp->data = tmp2->data;
  448. 					// 只有右子树节点 没有左子树节点
  449. 					if (NULL == top2) {
  450. 						tmp->right = NULL;
  451.  
  452. 					} else {
  453. 						top2->left = NULL;
  454. 					}
  455. 					free(tmp2);
  456. 				} else {
  457. 					// 方案 2
  458. 					TreeNode *tmp2 = tmp->left;
  459. 					TreeNode *top2 = NULL;
  460.  
  461. 					// 找到最后一个节点
  462. 					while (tmp2->right != NULL) {
  463. 						tmp2 = tmp2->right;
  464. 					}
  465.  
  466. 					// 删除老的节点
  467. 					tmp->data = tmp2->data;
  468. 					if (NULL == top2) {
  469. 						tmp->left = NULL;
  470. 					} else {
  471. 						top2->right = NULL;
  472. 					}
  473. 					free(tmp2);
  474. 				}
  475. 				
  476. 			}
  477. 		} else {
  478. 			top = tmp;
  479. 			if (data > tmp->data) {
  480. 				tmp = tmp->right;
  481. 			} else {
  482. 				tmp = tmp->left;
  483. 			}
  484. 		}
  485. 	}
  486. 	return false;
  487. }
  488.  
  489. // 二叉树平衡调整
  490. bool treeBalance(TreeNode **root) {
  491. 	checkTreeBalance((*root));
  492. 	while (BalanceTrue) {
  493. 		printf("二叉树不平衡,最小不平衡子树数据结点: %d\n",rjt->data);
  494. 		TreeNode *tmp;
  495.  
  496. 		if (1 < treeHeight(rjt->left) - treeHeight(rjt->right)) {
  497. 			// 对于不平衡二叉树而言，左子树比右子树高
  498. 			//
  499. 			//printf("左\n");
  500. 			if (rjt->left != NULL) {
  501. 				tmp = rjt->left;
  502. 				int ll = treeHeight(tmp->left);
  503. 				int rr = treeHeight(tmp->right);
  504. 				
  505. 				if (ll > rr) {
  506. 					// 对于不平衡子树 左子树 而言， 左子树比右子树高
  507. 					// 左左旋转
  508.  
  509. 					turnLL(root,rjt);
  510.  
  511. 				} else {
  512. 					// 对于不平衡子树 左子树 而言， 右子树比左子树高
  513. 					// 左右旋转
  514. 					//
  515. 					turnLR(root ,rjt);
  516. 				}
  517. 			} 
  518. 		} else if (1 < treeHeight(rjt->right) - treeHeight(rjt->left)) {
  519. 			// 对于不平衡二叉树而言，右子树比左子树高
  520. 			//
  521. 			//printf("右\n");
  522. 			if (rjt->right != NULL) {
  523. 				tmp = rjt->right;
  524. 				int ll = treeHeight(tmp->left);
  525. 				int rr = treeHeight(tmp->right);
  526.  
  527. 				if (ll > rr) {
  528. 					//右左旋转
  529. 					turnRL(root,rjt);
  530. 				} else {
  531. 					//右右旋转
  532. 					turnRR(root,rjt);
  533. 				}
  534. 			}		
  535. 		}
  536. 		
  537. 		BalanceTrue = false;
  538. 		checkTreeBalance((*root));
  539. 		printf("二叉树调整平衡后数据结点:\n");
  540. 		printf("前序遍历:");
  541. 		Print1(*root);
  542. 		printf("\n");
  543. 		printf("中序遍历:");
  544. 		Print2(*root);
  545. 		printf("\n");
  546. 		printf("\n");
  547. 	}
  548.  
  549. }
  550.  
  551. int main() {
  552. 	TreeNode *root = NULL;
  553.  
  554. 	printf("平衡二叉树插入测试\n");
  555. 	int nums[] = {65,60,70,55,40,63,69,66,68,77};
  556. 	int i;
  557. 	for (i=0;i<sizeof(nums)/sizeof(int);i++) {
  558. 		printf("插入数据: %d\n",nums[i]);
  559.  
  560. 		root = addNode(root,nums[i]);
  561. 		if (NULL == root) {
  562. 			printf("首节点申请失败"); 
  563. 			return -1;
  564. 		}
  565.  
  566. 		treeBalance(&root);
  567. 		sleep(1);
  568.  
  569. 	}
  570. 	printf("\n当前二叉树遍历\n");
  571. 	printf("前序遍历:");
  572. 	Print1(root);
  573. 	printf("\n");
  574. 	printf("中序遍历:");
  575. 	Print2(root);
  576. 	printf("\n");
  577. 	//return 0;
  578.  
  579. 	printf("\n\n平衡二叉树删除测试\n");
  580.  
  581. 	for (i=2;i<5;i++) {
  582. 		DeleteTreeNode(&root,nums[i]);
  583.  
  584. 		treeBalance(&root);
  585. 		sleep(1);
  586. 	}
  587.  
  588. 	printf("\n当前二叉树遍历\n");
  589. 	printf("前序遍历:");
  590. 	Print1(root);
  591. 	printf("\n");
  592. 	printf("中序遍历:");
  593. 	Print2(root);
  594. 	printf("\n");
  595. 		
  596. 	return 0;
  597. }

程序执行结果

  1. # gcc BalanceTree.c -w -g -std=c11
  2. # 
  3. # ./a.out 
  4. 平衡二叉树插入测试
  5. 插入数据: 65
  6. 插入数据: 60
  7. 插入数据: 70
  8. 插入数据: 55
  9. 插入数据: 40
  10. 二叉树不平衡,最小不平衡子树数据结点: 60
  11. 左左旋转,非根节点
  12. 二叉树调整平衡后数据结点:
  13. 前序遍历:65     55      40      60      70
  14. 中序遍历:40     55      60      65      70
  15.  
  16. 插入数据: 63
  17. 二叉树不平衡,最小不平衡子树数据结点: 65
  18. 左右旋转，是根节点
  19. 二叉树调整平衡后数据结点:
  20. 前序遍历:60     55      40      65      63      70
  21. 中序遍历:40     55      60      63      65      70
  22.  
  23. 插入数据: 69
  24. 插入数据: 66
  25. 二叉树不平衡,最小不平衡子树数据结点: 70
  26. 左左旋转,非根节点
  27. 二叉树调整平衡后数据结点:
  28. 前序遍历:60     55      40      65      63      69      66      70
  29. 中序遍历:40     55      60      63      65      66      69      70
  30.  
  31. 插入数据: 68
  32. 二叉树不平衡,最小不平衡子树数据结点: 65
  33. 右左旋转，非根节点
  34. 二叉树调整平衡后数据结点:
  35. 前序遍历:60     55      40      66      65      63      69      68      70
  36. 中序遍历:40     55      60      63      65      66      68      69      70
  37.  
  38. 插入数据: 77
  39. 二叉树不平衡,最小不平衡子树数据结点: 60
  40. 右右旋转,是根节点
  41. 二叉树调整平衡后数据结点:
  42. 前序遍历:66     60      55      40      65      63      69      68      70      77
  43. 中序遍历:40     55      60      63      65      66      68      69      70      77
  44.  
  45.  
  46. 当前二叉树遍历
  47. 前序遍历:66     60      55      40      65      63      69      68      70      77
  48. 中序遍历:40     55      60      63      65      66      68      69      70      77
  49.  
  50.  
  51. 平衡二叉树删除测试
  52. 删除节点: 70
  53. 删除节点: 55
  54. 删除节点: 40
  55. 二叉树不平衡,最小不平衡子树数据结点: 60
  56. 右左旋转，非根节点
  57. 二叉树调整平衡后数据结点:
  58. 前序遍历:66     63      60      65      69      68      77
  59. 中序遍历:60     63      65      66      68      69      77
  60.  
  61.  
  62. 当前二叉树遍历
  63. 前序遍历:66     63      60      65      69      68      77
  64. 中序遍历:60     63      65      66      68      69      77
  65. #

‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧  END  ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧

关注我的微信公众号，回复“加群”按规则加入技术交流群。
点击“阅读原文”查看更多分享，欢迎点分享、收藏、点赞、在看。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/632120
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号