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

C语言实现平衡二叉树的插入与删除_高度平衡树的插入和删除c语言

作者：从前慢现在也慢 | 2024-05-03 07:04:29

赞

踩

高度平衡树的插入和删除c语言

目录

前言&看前必读

1.什么是平衡二叉树？

        1.1平衡二叉树的基本概念

         1.2为何要引入平衡二叉树？

2.平衡二叉树如何进行调整？

3.平衡二叉树的插入实现

4.平衡二叉树的删除实现

5.完整代码

前言&看前必读

本文参考b站up@TyrantLucifer，发布的视频教程数据结构-平衡二叉树(AVL)-C语言实现https://www.bilibili.com/video/BV1m64y147Tv/?p=2&vd_source=b64a25bce866a4532d6d87bb174d59e4这个视频讲解通俗易懂，代码可读性也比较高，值得网友去学习。所以本文代码基于此视频教程作为参考，不过这里的代码但略有改动，程序的思路是相同的。另附参考的原文地址：数据结构系列19-平衡二叉树 | tyrantlucifer

本文不讲大量空洞的理论。秉承以实践为主，理论为辅的宗旨讲解平衡二叉树的插入与删除的实现。前面第一节第二节主要是简述一些基本的概念，从第三节开始结合实际讲解程序的思路。如果您对平衡二叉树有了基本的认识可以直接跳到第三节。

个人技术水平有限，如有不妥之处请多多指教，相互交流学习

1.什么是平衡二叉树？

        1.1平衡二叉树的基本概念

                平衡二叉树(balance binary tree)又称作AVL树，AVL树名字来自提出者G.M. Adelson-Velsky和E.M. Landis。平衡二叉树是二叉搜索树的进化体，由此平衡二叉树具有二叉排序树所有的基本特征：

                1.如果左子树不为空，则左子树上任意一个节点值均小于根节点值。

                2.如果右子树不为空，则右子树上任意一个节点值均大于根节点值。

                3.左右子树都是二叉排序树。

                4.树中没有相同的节点。

除此之外，平衡二叉树还具备一个非常重要的特点：任意一个节点左右子树的高度之差的绝对值不超过1，加上前面所提到的四个特征，总共五个特征，缺一不可。我们通常把左右子树的高度差称为平衡因子（BF，Belance Fator），如下面图1所示，这是一颗典型的平衡二叉树。每个节点右上角标记的数是这个节点的平衡因子，显然这颗平衡二叉树具备其应有的所有特征。

        

6a6e5204a6d244209bda9c6dc1afbc81.jpeg

图1 平衡二叉树

         1.2为何要引入平衡二叉树？

        二叉排序树的平均查找长度与树的形状有关，最好的情况是O(log2n),最差的情况是O(n),如下图所示，把1 2 3 4 5 这几个元素，按顺序依次插入节点将得到这样的一颗二叉树，如图2所示，此时二叉查找树被退化成链表。显然这个二叉排序树的平均查找长度为O(n)，所以我们需要引入平衡二叉树来解决这一问题，平衡二叉树在插入/删除完成后，会沿着检查其插入/删除路径的每一个节点的平衡因子，当平衡因子BF等于2时会及时做出相应的调整，从而最大程度的避免这种情况发生。

dd13b27101764f4aaf8162594f4d9042.jpeg

图2 退化成链表的二叉排序树

2.平衡二叉树如何进行调整？

                为了方便讲解平衡二叉树如何调整，我们要引入一个概念，即最小不平衡子树，最小不平衡二叉子树的根节点是离插入点最近且平衡因子的绝对值大于1的节点作为根节点的二叉子树，如图3所示的二叉排序树，在此树插入一个新节点90，如左侧所示，左侧原本98的平衡因子绝对值为1，插入后由1变为2，显然98就是最小不平衡二叉子树的根节点。如右边的红色圈圈所示。当然最小不平衡二叉子树有可能的整个二叉树本身，如图5所示，15是二叉树的根节点，它的平衡因子的绝对值为2。

f4558946e64048dd93dae4d51969c2ab.jpeg

图 3 最小不平衡子树

         

af725f4fcb2346dba9652ea9743af814.jpeg

图5 最小不平衡二叉子树也有可能是根节点

温馨提示：下面简单介绍几种不平衡节点的调整方式，这些内容对编写程序的帮助有限，仅用于了解一些基本的概念，实际调整碰到的情况比较复杂一点，很多情况下只会这些概念编写程序显得有些束手无策，当然如果您对这些调整方式有了基本的认识，可以直接跳到二叉树的插入实现这一节，本文将讲详细讲解其插入删除时调整的原理和细节。

图6-图9看懂大概意思就行了，先不要钻牛角尖，对于平衡二叉树的学习由易到难，才是正确的学习方法，平衡二叉树调整的详细过程请见本文的第三节。平衡二叉树旋转必须要掌握稍微复杂的情况怎么处理，才能独立写出程序来。

对于平衡二叉树来说不平衡节点主要右RR型、LL型、RL型、LR型。导致不平衡节点出现的原因都是新节点插入导致的，所以我们需要对其进行旋转操作。

常见不平衡节点产生的原因以及处理方法

类型原因处理方法
RR新插入节点的插入到不平衡节点的右孩子的右边左旋（图6）
LL新插入节点的插入到不平衡节点的左孩子的左边右旋（图7）
RL新插入节点的插入到不平衡节点的右孩子的左边先右旋再左旋（图8）
LR新插入节点的插入到不平衡节点的左孩子的右边先左旋再右旋（图9）

对于RR型我们需要进行左旋操作，如图6所示：

8776ef29c29049f5a06bbf2cd17efbff.jpeg

图6 RR型调整

 对于LL型我们需要进行先右旋操，如图7所示：

0f092155660f4b8aaa6b3e85f28aea7b.jpeg

图7 LL型调整

  对于RL型我们需要进行先右旋操作，再左旋操作，如图8所示：

   

51ff35f583f64b8581a6dca61c6ccd15.jpeg

图8 RL型调整

对于LR型我们需要进行先左旋操作，再右旋操作，如图9所示：

e114feb2a6d94b918b2a2c37d8936619.jpeg

图9 LR型调整

3.平衡二叉树的插入实现

             如图10-图12所示下面分别是稍微复杂情况下调整方法以及各节点平衡因子的情况，通过观察平衡因子的情况有助于我们写程序来判断当前二叉树是否应该要调整。实现平衡二叉树的插入操作首先要实现左旋函数和右旋函数，以确保插入元素后任然具有平衡二叉树的所有特性。

dcba622ab94f4cb69a1d0a59661d2c51.jpeg

图10 稍复杂情况下的RR型的调整

        如图10所示130是最新插入的节点，50是不平衡节点，它的平衡因子(以下将简称BF)为-2，属于RR型，RR型是新节点插入最小不平衡右子树的右子树导致的，因此我们对它进行左旋操作，先做准备工作，创建一个临时变量保存首先把最小不平衡子树的根节点右孩子保存起来，最小不平衡子树的根节点的右孩子指针指向最小不平衡右孩子的左孩子，然后再把最小不平衡子树的根节点的右孩子的左孩子指针指向最小不平衡子树的根节点，最后把最小不平衡子树的根节点的右孩子换做成该子树的根节点。

        或许看着听着有点绕？没关系，看下面的代码并且结合图片更非常的直观的。

  首先定义一个结构体

  1. typedef struct TreeNode
  2. {
  3. 	int data;//数据
  4. 	int height;//当前节点的高度
  5. 	struct TreeNode* lchild;//左孩子
  6. 	struct TreeNode* rchild;//右孩子
  7. }TreeNode;
  8.  
  9. //获取当前节点高度
  10. int getHeight(TreeNode* node)
  11. {
  12. 	return node ? node->height : 0;
  13. }
  14. //返回最大值
  15. int max(int a, int b)
  16. {
  17. 	return a>b ? a : b;
  18. }

 实现RR型处理的左旋函数

  1. //RR处理，左旋node是根节点指针，root是根节点二级指针
  2. //当然作为读者可以适当优化一些，比如只用一个二级指针就能实现这个功能
  3. void rrRotation(TreeNode *node, TreeNode** root)
  4. {
  5. 	TreeNode* temp = node -> rchild;//保存最小不平衡子树根节点的右孩子
  6. 	node -> rchild = temp ->  lchild;//根节点右孩子指向，自己右孩子的左孩子
  7. 	temp -> lchild = node;//自己右孩子的左孩子指针指向根原来的最小不平衡二叉树的根节点
  8.     //重新节点计算高度
  9. 	node -> height = max(getHeight(node -> lchild),getHeight(node -> rchild)) + 1;
  10. 	temp -> height = max(getHeight(temp -> lchild),getHeight(temp -> rchild)) + 1;
  11. 	//原来的最小不平衡二叉树的根节点的右孩子作为新的根节点
  12.     *root = temp;
  13. }
f38a1eba64d8462d82b8920eb346e16c.jpeg

图11 稍复杂情况下的LL型的调整

          如图11所示8是最新插入的节点，15是不平衡节点，它的平衡因子BF为2，属于LL型，LL型是新节点插入最小不平衡左子树的左子树导致的，因此我们对它进行右旋操作，先做准备工作，创建一个临时变量保存首先把最小不平衡子树的根节点左孩子保存起来，最小不平衡子树的根节点的左孩子指针指向最小不平衡左孩子的右孩子，然后再把最小不平衡子树的根节点的左孩子的右孩子指针指向最小不平衡子树的根节点，最后把最小不平衡子树的根节点的左孩子换做成该子树的根节点。

   看下面的代码并且结合图片更非常的直观的。

   实现LL型处理的右旋函数

  1. //LL处理，右旋，node是根节点指针，root是根节点二级指针
  2. //当然作为读者可以适当优化一些，比如只用一个二级指针就能实现这个功能
  3. void llRotation(TreeNode *node, TreeNode** root)
  4. {
  5. 	TreeNode *temp =  node ->lchild;//保存最小不平衡子树根节点的左孩子
  6. 	node -> lchild = temp->rchild;//根节点左孩子指向自己左孩子的右孩子
  7. 	temp -> rchild = node;//自己左孩子的右孩子指针指向根原来的最小不平衡二叉树的根节点
  8. 	//更新高度
  9.     node -> height = max(getHeight(node->lchild),getHeight(node->rchild)) + 1;
  10. 	temp -> height = max(getHeight(temp -> lchild),getHeight(temp -> rchild)) + 1;
  11. 	*root = temp;//左孩子作为根节点
  12. }
dd0107f5ac49434cac32bc9970db8b5b.jpeg

图12  稍复杂情况下的RL型的调整

d21af1e2c57b427fa7d367a5dd1eb2f2.jpeg

图13 稍复杂情况下LR调整

 如图13-14所示，RL型很直观的可以看出，先对其最小不平衡子树的右孩子右旋，然后对最小不平衡子树的根左旋。LR型很直观的可以看出，先对其最小不平衡子树的左孩子左旋，然后对最小不平衡子树的根右旋。

       平衡二叉树插入思路

              平衡二叉树的插入基本原理与二叉搜索树相类似，只不过多了一个二叉树调整的步骤，每次插入完后向原路径返回，检查其节点的平衡因子的绝对值是否大于2，如果大于2，则去调整。

        二叉树插入/删除的实现主要是难点是如何判断最小不平衡子树属于哪种类型，一般情况人眼看二叉树不平衡属于哪种类型该如何调整，一眼就能看出来，但是计算机不像人类一样，所以需要梳理好一套清晰的逻辑，才能编写程序来判断并作出相应调整。

        观察图6-图13可知，LL型的新插入的节点总是在当前节点的左孩子的左边，再结合本文第一节所提到的特征，新插入的节点一定比当前不平衡节点的左孩子要小。如果是LR型，新插入的节点总是在当前节点的左孩子的右边，所以比当前节点的左孩子大。RR型新插入的节点一定比当前不平衡节点的右孩子要大，RL型则是相反的，只要利用这个特性就能判断出当前节点不平衡属于什么类型了。

平衡二叉树插入代码如下所示：

  1.  
  2.  
  3. //插入
  4. void avlInsert(TreeNode** T, int data)
  5. {
  6. 	if(*T == NULL)
  7. 	{
  8. 		*T = (TreeNode*)malloc(sizeof(TreeNode));
  9. 		(*T) -> data = data;
  10. 		(*T) -> height = 0;
  11. 		(*T) -> lchild = NULL;
  12. 		(*T) -> rchild = NULL;
  13. 	}else if(data < (*T)->data){
  14.  
  15. 		avlInsert(&(*T)->lchild,data);
  16.  
  17. 		int lHeight = getHeight((*T) -> lchild);
  18. 		int rHeight = getHeight((*T) -> rchild);
  19. 		//计算平衡因子
  20. 		if(lHeight - rHeight == 2)//LL or LR
  21. 		{
  22. 			if(data < (*T)->lchild->data)
  23. 			{
  24. 				//LL
  25. 				llRotation(*T,T);
  26. 			}else{
  27. 				//LR
  28. 				rrRotation((*T)->lchild,&(*T)->lchild);
  29. 				llRotation(*T,T);
  30. 			}
  31. 		}
  32. 	}else if(data > (*T) -> data){// RR or RL
  33. 		avlInsert(&(*T) -> rchild, data);
  34. 		int lHeight = getHeight((*T)->lchild);
  35. 		int rHeight = getHeight((*T)->rchild);
  36. 		//计算bf
  37. 		if(rHeight - lHeight == 2)
  38. 		{
  39. 			if(data > (*T) -> rchild -> data)
  40. 			{
  41. 				//RR
  42. 				rrRotation(*T,T);
  43. 			}else{
  44. 				//RL
  45. 				llRotation((*T)->rchild,&(*T)->rchild);
  46. 				rrRotation(*T,T);
  47. 				
  48. 			}
  49. 		}
  50. 	}
  51. 	(*T)->height = max(
  52. 						getHeight((*T)->lchild),
  53. 						getHeight((*T)->rchild)
  54. 					) +1;
  55. }

4.平衡二叉树的删除实现

         平衡二叉树删除的基本原理也是类似的，删除的基本原理和二叉搜索树相同，如果不了解基本原理请参考下面这篇文章：

c语言递归实现二叉排序树的插入与删除https://blog.csdn.net/qq_21708039/article/details/130516473        平衡二叉树的插入和删除也是同样的，删除后需要沿着删除路径检查是否有节点不平衡，也就是计算BF，对此本文采用第二种方法来判断不平衡节点的类型。

        通过观察图6-图13可知，当最小不平衡二叉树的BF是+2说明当前类型可能是LL型或者LR型，这时候我们需要进一步判断他的左子树BF值是多少，当左子树的BF=1或者0是说明是LL型，LR型BF = -1。当最小不平衡二叉树的BF是-2明当前类型可能是RR型或者RL型，这时候我们需要进一步判断他的右子树BF值是多少，当右子树的BF=-1或者0是说明是RR型，RL型BF = 1。

平衡二叉树删除代码如下所示：

  1. //删除
  2. void avlDelete(TreeNode** T, int data)
  3. {
  4. 	if(T == NULL)	return;
  5. 	if(*T == NULL)	return;
  6. 	if(data > (*T)->data)
  7. 	{
  8.  
  9. 		avlDelete(&(*T)->rchild,data);
  10. 	
  11. 	}else if(data < (*T)->data){
  12. 	
  13. 		avlDelete(&(*T)->lchild,data);
  14.  
  15. 	}else{
  16.  
  17. 		if((*T)->lchild == NULL  && (*T)->rchild == NULL)
  18. 		{
  19.  
  20. 			free(*T);
  21. 			*T = NULL;
  22. 		
  23. 		}else if( (*T) -> lchild == NULL ){
  24.  
  25. 			struct TreeNode* temp = (*T)->rchild;
  26. 			free(*T);
  27. 			*T = temp;
  28. 		}else if( (*T) -> rchild == NULL ){
  29.  
  30. 			struct TreeNode* temp = (*T)->lchild;
  31. 			free(*T);
  32. 			*T = temp;
  33. 				
  34. 		}else{
  35. 			struct TreeNode* temp = (*T)->lchild;
  36. 			while(temp -> rchild != NULL)
  37. 			{
  38. 				temp = temp ->rchild;
  39. 			}
  40. 			(*T)->data = temp->data;
  41. 			avlDelete(&(*T)->lchild,temp->data);
  42. 		}
  43.  
  44. 	}
  45.  
  46. 		if(*T == NULL) return;//如果删除后是空指针就什么都不做
  47. 		(*T)->height = max(
  48. 					
  49. 					getHeight((*T)->lchild),
  50. 					getHeight((*T)->rchild)
  51. 				
  52. 				)+1;
  53. 		int lheight = getHeight((*T)->lchild);
  54. 		int rheight = getHeight((*T)->rchild);
  55.         //计算BF
  56. 		if(lheight-rheight == 2)
  57. 		{
  58. 			//LL LR
  59.             //进一步判断，详见上文
  60. 			if( getHeight((*T)->lchild->lchild) - getHeight((*T)->lchild->rchild) == 0 ||  getHeight((*T)->lchild->lchild) - getHeight((*T)->lchild->rchild) == 1 )
  61. 			{
  62. 				//LL
  63. 				
  64. 				llRotation(*T,T);
  65. 			}else{
  66. 				//LR
  67. 			
  68. 				rrRotation((*T)->lchild, &(*T)->lchild);
  69. 				llRotation(*T,T);
  70. 			}
  71.  
  72. 		}else if(lheight -rheight == -2)
  73. 		{
  74. 			//RR RL	
  75. 			if( getHeight((*T)->rchild->lchild) - getHeight((*T)->rchild->rchild) == 0 ||  getHeight((*T)->rchild->lchild) - getHeight((*T)->rchild->rchild) == -1 )
  76. 			{
  77. 				//RL
  78. 				rrRotation(*T,T);
  79. 			}else{
  80.  
  81. 				//RL
  82. 				llRotation((*T)->rchild,&(*T)->rchild);
  83. 				rrRotation(*T,T);
  84. 			}
  85.  
  86. 		}
  87. }

        

5.完整代码

  1. #include<stdlib.h>
  2. #include<stdio.h>
  3.  
  4. typedef struct TreeNode
  5. {
  6. 	int data;
  7. 	int height;
  8. 	struct TreeNode* lchild;
  9. 	struct TreeNode* rchild;
  10. }TreeNode;
  11.  
  12. int getHeight(TreeNode* node)
  13. {
  14. 	return node ? node->height : 0;
  15. }
  16.  
  17. int max(int a, int b)
  18. {
  19. 	return a>b ? a : b;
  20. }
  21.  
  22. void rrRotation(TreeNode *node, TreeNode** root)
  23. {
  24. 	TreeNode* temp = node -> rchild;
  25. 	node -> rchild = temp ->  lchild;
  26. 	temp -> lchild = node;
  27. 	node -> height = max(getHeight(node -> lchild),getHeight(node -> rchild)) + 1;
  28. 	temp -> height = max(getHeight(temp -> lchild),getHeight(temp -> rchild)) + 1;
  29. 	*root = temp;
  30. }
  31.  
  32. void llRotation(TreeNode *node, TreeNode** root)
  33. {
  34. 	TreeNode *temp =  node ->lchild;
  35. 	node -> lchild = temp->rchild;
  36. 	temp -> rchild = node;
  37. 	node -> height = max(getHeight(node->lchild),getHeight(node->rchild)) + 1;
  38. 	temp -> height = max(getHeight(temp -> lchild),getHeight(temp -> rchild)) + 1;
  39. 	*root = temp;
  40. }
  41.  
  42. void avlInsert(TreeNode** T, int data)
  43. {
  44. 	if(*T == NULL)
  45. 	{
  46. 		*T = (TreeNode*)malloc(sizeof(TreeNode));
  47. 		(*T) -> data = data;
  48. 		(*T) -> height = 0;
  49. 		(*T) -> lchild = NULL;
  50. 		(*T) -> rchild = NULL;
  51. 	}else if(data < (*T)->data){
  52.  
  53. 		avlInsert(&(*T)->lchild,data);
  54.  
  55. 		int lHeight = getHeight((*T) -> lchild);
  56. 		int rHeight = getHeight((*T) -> rchild);
  57. 		//计算平衡因子
  58. 		if(lHeight - rHeight == 2)
  59. 		{
  60. 			if(data < (*T)->lchild->data)
  61. 			{
  62. 				//LL
  63. 				llRotation(*T,T);
  64. 			}else{
  65. 				//LR
  66. 				rrRotation((*T)->lchild,&(*T)->lchild);
  67. 				llRotation(*T,T);
  68. 			}
  69. 		}
  70. 	}else if(data > (*T) -> data){
  71. 		avlInsert(&(*T) -> rchild, data);
  72. 		int lHeight = getHeight((*T)->lchild);
  73. 		int rHeight = getHeight((*T)->rchild);
  74. 		//计算bf
  75. 		if(rHeight - lHeight == 2)
  76. 		{
  77. 			if(data > (*T) -> rchild -> data)
  78. 			{
  79. 				//RR
  80. 				rrRotation(*T,T);
  81. 			}else{
  82. 				//RL
  83. 				llRotation((*T)->rchild,&(*T)->rchild);
  84. 				rrRotation(*T,T);
  85. 				
  86. 			}
  87. 		}
  88. 	}
  89. 	(*T)->height = max(
  90. 						getHeight((*T)->lchild),
  91. 						getHeight((*T)->rchild)
  92. 					) +1;
  93. }
  94.  
  95.  
  96. void avlDelete(TreeNode** T, int data)
  97. {
  98. 	if(T == NULL)	return;
  99. 	if(*T == NULL)	return;
  100. 	if(data > (*T)->data)
  101. 	{
  102.  
  103. 		avlDelete(&(*T)->rchild,data);
  104. 	
  105. 	}else if(data < (*T)->data){
  106. 	
  107. 		avlDelete(&(*T)->lchild,data);
  108.  
  109. 	}else{
  110.  
  111. 		if((*T)->lchild == NULL  && (*T)->rchild == NULL)
  112. 		{
  113.  
  114. 			free(*T);
  115. 			*T = NULL;
  116. 		
  117. 		}else if( (*T) -> lchild == NULL ){
  118.  
  119. 			struct TreeNode* temp = (*T)->rchild;
  120. 			free(*T);
  121. 			*T = temp;
  122. 		}else if( (*T) -> rchild == NULL ){
  123.  
  124. 			struct TreeNode* temp = (*T)->lchild;
  125. 			free(*T);
  126. 			*T = temp;
  127. 				
  128. 		}else{
  129. 			struct TreeNode* temp = (*T)->lchild;
  130. 			while(temp -> rchild != NULL)
  131. 			{
  132. 				temp = temp ->rchild;
  133. 			}
  134. 			(*T)->data = temp->data;
  135. 			avlDelete(&(*T)->lchild,temp->data);
  136. 		}
  137.  
  138. 	}
  139. 		if(*T == NULL) return;
  140. 		(*T)->height = max(
  141. 					
  142. 					getHeight((*T)->lchild),
  143. 					getHeight((*T)->rchild)
  144. 				
  145. 				)+1;
  146. 		int lheight = getHeight((*T)->lchild);
  147. 		int rheight = getHeight((*T)->rchild);
  148. 		if(lheight-rheight == 2)
  149. 		{
  150. 			//LL LR
  151. 			if( getHeight((*T)->lchild->lchild) - getHeight((*T)->lchild->rchild) == 0 ||  getHeight((*T)->lchild->lchild) - getHeight((*T)->lchild->rchild) == 1 )
  152. 			{
  153. 				//LL
  154. 				
  155. 				llRotation(*T,T);
  156. 			}else{
  157. 				//LR
  158. 			
  159. 				rrRotation((*T)->lchild, &(*T)->lchild);
  160. 				llRotation(*T,T);
  161. 			}
  162.  
  163. 		}else if(lheight -rheight == -2)
  164. 		{
  165. 			//RR RL	
  166. 			if( getHeight((*T)->rchild->lchild) - getHeight((*T)->rchild->rchild) == 0 ||  getHeight((*T)->rchild->lchild) - getHeight((*T)->rchild->rchild) == -1 )
  167. 			{
  168. 				//RL
  169. 				rrRotation(*T,T);
  170. 			}else{
  171.  
  172. 				//RL
  173. 				llRotation((*T)->rchild,&(*T)->rchild);
  174. 				rrRotation(*T,T);
  175. 			}
  176.  
  177. 		}
  178. }
  179.  
  180. void preOrder(TreeNode *T)
  181. {
  182. 	if(!T) return;
  183. 	printf("%d ", T->data);
  184. 	preOrder(T -> lchild);
  185. 	preOrder(T -> rchild);
  186. }
  187.  
  188.  
  189. void inOrder(TreeNode *T)
  190. {
  191. 	if(!T) return;
  192. 	inOrder(T -> lchild);
  193. 	printf("%d ", T->data);
  194. 	inOrder(T -> rchild);
  195. }
  196.  
  197. void bstFree(TreeNode** T)
  198. {
  199. 	if(*T == NULL) return;
  200. 	 bstFree(&(*T)->lchild);
  201. 	 bstFree(&(*T)->rchild);
  202. 	 free(*T);
  203. 	 *T=NULL;
  204. }
  205.  
  206.  
  207. int main()
  208. {
  209. 	TreeNode *T = NULL;
  210. 	int nums[5] = {1,8,6,7,10};
  211. 	for(int i = 0; i<5; i++)
  212. 	{
  213. 		avlInsert(&T,nums[i]);
  214. 	}
  215.  
  216. 	preOrder(T);
  217. 	printf("\t先\n");
  218. 	inOrder(T);
  219. 	printf("\t中\n");
  220.  
  221. 	avlDelete(&T,6);
  222. 	preOrder(T);
  223. 	printf("\t先\n");
  224. 	inOrder(T);
  225. 	printf("\t中\n");
  226. 	
  227. 	bstFree(&T);
  228. 	
  229. 	return 0;
  230. }

 运行结果：

  1. 6 1 8 7 10 	先
  2. 1 6 7 8 10 	中
  3. 8 1 7 10 	先
  4. 1 7 8 10 	中

3df171b79e5946bdbb7f1c3303ff44c3.jpeg

图14 上面程序的平衡二叉树的调整过程

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/528400
推荐阅读
相关标签

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

  

闽ICP备14008679号