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

平衡二叉树算法实现C++_平衡二叉树c++

作者：从前慢现在也慢 | 2024-07-21 22:55:09

赞

踩

平衡二叉树c++

数据结构课程设计之平衡二叉树算法实现。

什么是平衡二叉树？

是一种结构平衡的二叉搜索树，是一种每个节点的左右子树高度差都不超过1的二叉树。

由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质：

  1. 可以是空树。
  2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

举个例子，下图不是平衡二叉树，因为结点 60 的左子树高度为2，右子树高度为0，高度超过1。

什么是二叉搜索树？

它或者是一棵空树，或者是具有下列性质的 二叉树 ： 若它的左子树不空，则左子树上所有结点的值均小于它的 根结点 的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为 二叉排序树 。. 二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

为什么要拥有平衡二叉树呢？

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列 A = {1，2，3，4，5，6}，构造二叉搜索树如下图。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。

二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列 A，将其改为下图的方式存储，查找元素 6 时只需比较 3 次，查找效率提升一倍。

可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。

这种左右子树的高度相差不超过 1 的树为平衡二叉树。

平衡因子：

某结点的左子树和右子树的高度差即为该结点的平衡因子，平衡二叉树中不存在平衡因子大于 1 的节点。

如何构造平衡二叉树？

首先我们知道，平衡二叉树是一颗二叉树，我们二叉树结构具有左子树、右子树、值，而在平衡二叉树，由于我们需要检查它的平衡性，以及失衡调整操作，我们需要定义一个深度。下面代码块是平衡二叉树的定义。

  1. //平衡二叉树的结构 
  2. typedef struct AVLNode{
  3. 	int depth;//深度
  4. 	struct AVLNode *left;//左孩子 
  5. 	struct AVLNode *right;//右孩子 
  6. 	struct AVLNode *parent;//父结点 
  7. 	ElenmentType value; //值 
  8. }AVLtree,Tree;

平衡二叉树的初始化：
 

  1. //初始化 
  2. Tree* Init(ElenmentType value){
  3. 	Tree* root=new Tree();
  4. 	root->parent = NULL;
  5.     root->depth = 0;
  6.     root->left = root->right = NULL;
  7.     root->value=value; 
  8.     return root;
  9. }

平衡二叉树插入时的失衡和调整：

二叉树的基本操作有：插入、删除、遍历等。

对于平衡二叉树而言，插入和删除会导致二叉树的失衡。

下图是一棵平衡二叉树

在此平衡二叉树插入节点 99 ，树结构变为：

节点 66 的左子树高度为 1，右子树高度为 3，此时平衡因子为 -2，树失去平衡。

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。 

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。

根据旋转的方向有两种处理方式，左旋 与 右旋 。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

左旋：

在下图中，加入新节点 99 后， 节点 66 的左子树高度为 1，右子树高度为 3，此时平衡因子为 -2。为保证树的平衡，此时需要对节点 66 做出旋转，因为右子树高度高于左子树，对节点进行左旋操作，流程如下：

（1）节点的右孩子替代此节点位置 （2）右孩子的左子树变为该节点的右子树 （3）节点本身变为右孩子的左子树

  • 节点的右孩子替代此节点位置 —— 节点 66 的右孩子是节点 77 ，将节点 77 代替节点 66 的位置
  • 右孩子的左子树变为该节点的右子树 —— 节点 77 的左子树为节点 75，将节点 75 挪到节点 66 的右子树位置
  • 节点本身变为右孩子的左子树 —— 节点 66 变为了节点 77 的左子树
  1. //RR型调整函数,执行左旋 
  2. Tree* RR_rotate(Tree * root){
  3.     Tree* temp;
  4.     temp = root->right;
  5.     root->right = temp->left;
  6.     temp->left = root;
  7.     return temp;
  8. }

右旋：

（1）节点的左孩子代表此节点 （2）节点的左孩子的右子树变为节点的左子树 （3）将此节点作为左孩子节点的右子树。

  1. //LL型调整函数,执行右旋
  2. Tree* LL_rotate(Tree *root){
  3.     Tree *temp;
  4. 	temp = root->left;
  5. 	root->left = temp->right;
  6. 	temp->right = root;
  7. 	return temp; 
  8.    
  9. }

四种可能的插入方式：

 LL和RR的插入方式中，我们对最小失衡子树实现右旋和左旋即可。

若 A 的左孩子节点 B 的右子树 E 插入节点 F ，导致节点 A 失衡，如图

这种称为LR的插入方式，在LR的插入方式中，我们先对最小失衡子树A的左孩子B进行左旋，再对最小失衡子树A进行右旋.

  1. //LR型调整函数，先左旋转，再右旋转
  2. Tree* LR_rotate(Tree* root){
  3. 	Tree* temp;
  4. 	temp = root->left;
  5.     root->left =RR_rotate(temp);
  6.     return LL_rotate(root);
  7. }

若 A 的右孩子节点 C 的左子树 D 插入节点 F ，导致节点 A 失衡，如图 

这种称为RL的插入方式,在RL的插入方式中，我们先对最小失衡子树 A 的右孩子 C 进行右旋操作，再对最小失衡子树 A 做左旋操作。

  1. //RL型调整函数，先右旋转，再左旋转
  2. Tree* RL_rotate(Tree* root){
  3. 	 Tree* temp;
  4. 	 temp = root->right;
  5.     root->right=LL_rotate(temp);
  6.     return RR_rotate(root);
  7. } 
  1. //插入结点
  2. Tree* Insert(Tree* root,ElenmentType k )
  3. {
  4.     if (NULL == root)
  5.     {
  6.         root = Init(k);//如果根结点为null，则直接将值为根结点 
  7.         if(root==NULL)
  8.         	cout<<"创建失败"<<endl; 
  9.         return root;
  10.     }
  11.     else if (k < root->value)
  12.     {
  13.         root->left = Insert(root->left, k);//递归左子树
  14.         root = Balance(root);//平衡操作
  15.     }
  16.     else if (k>root->value)
  17.     {
  18.         root->right = Insert(root->right, k);//递归右子树
  19.         root = Balance(root);//平衡操作
  20.     }
  21.     return root;
  22. }

平衡二叉树删除时的失衡和调整：

删除操作分为四种情况：
（1）删除叶子节点

（2）删除的节点只有左子树

（3）删除的节点只有右子树

（4）删除的节点既有左子树又有右子树 

AVL 树在删除节点后需要重新检查平衡性并修正，同时，删除操作与插入操作后的平衡修正区别在于，插入操作只需要调整最小的不平衡子树，而删除操作需要调整所有的不平衡子树。

删除操作的大致步骤如下：

1.查找删除元素是否存在

2.删除元素的值与根节点的值的比较，删除元素的值若小于根节点的值，则往左边删，大于则往右边删，直到找到删除节点。

3.判断删除的节点的情况，是既有左子树又有右子树，还是只有左子树，还是只有右子树，还是为叶子节点。

4.根据不同的情况进行删除

若删除的节点既有左子树又有右子树

     1）左子树更高，在左边删除，以左子树的最大值替换当前值，删除左子树中已经替换上去的节点。（删除替换节点进行了递归）

     2）右子树更高，在右边删除，以右子树的最小值替换当前值，删除右子树中已经替换上去的节点。（删除替换节点进行了递归）

若删除的节点只有一个孩子或者为叶子节点，那么我们可以直接进行删除。

5.删除之后，进行平衡性检查，若失衡，则进行失衡调整。

注：对于删除操作造成的非平衡状态的修正，可以这样理解：对左或者右子树的删除操作相当于对右或者左子树的插入操作，然后再对应上插入的四种情况选择相应的旋转就好了。

  1. //删除结点
  2. Tree* Delete(Tree *root, const ElenmentType k)
  3. {
  4.     if (NULL == root)
  5.         return root;
  6.     if (!binaryTreeSearch(root,k))//查找删除元素是否存在
  7.     {
  8.         cout<<"删除失败，未找到"<<endl;
  9.         return root;
  10.     }
  11.  
  12.     if (k == root->value)//根节点
  13.     {
  14.         if (root->left!=NULL&&root->right!=NULL)//左右子树都非空
  15.         {
  16.             if (diff(root) > 0)//左子树更高，在左边删除
  17.             {
  18.                 root->value = tree_max(root->left);//以左子树的最大值替换当前值
  19.                 root->left = Delete(root->left, root->value);//删除左子树中已经替换上去的节点
  20.             }
  21.             else//右子树更高，在右边删除
  22.             {
  23.                 root->value = tree_min(root->right);//以右子树的最小值替换当前值
  24.                 root->right = Delete(root->right, root->value);//删除右子树中已经替换上去的节点
  25.             }
  26.         }
  27.         else//有一个孩子、叶子节点的情况合并
  28.         {
  29.                 Tree * tmp = root;
  30.                 root = (root->left) ? (root->left) :( root->right);
  31.                 delete tmp;
  32.                 tmp = NULL;
  33.         }
  34.     }
  35.     //往左边删 
  36.     else if (k < root->value)
  37.     {
  38.         root->left = Delete(root->left, k);
  39.         //不满足平衡条件
  40. 		if (diff(root) < -1)
  41.         {
  42.             if (diff(root->right) > 0)
  43.             {
  44.                 root = RL_rotate(root);
  45.             }
  46.             else
  47.             {
  48.                 root = RR_rotate(root);
  49.             }
  50.         }
  51.     }
  52.     //往右边删 
  53.     else
  54.     {
  55.         root->right = Delete(root->right, k);
  56.         //不满足平衡 条件 
  57.         if (diff(root) > 1)
  58.         {
  59.             if (diff(root->left) < 0)
  60.             {
  61.                 root = LR_rotate(root);
  62.             }
  63.             else
  64.             {
  65.                 root = LL_rotate(root);
  66.             }
  67.         }
  68.     }
  69.     return root;
  70. }

完整代码如下：

  1. #include<iostream>
  2. using namespace std;
  3.  
  4.  
  5. typedef int ElenmentType; 
  6. //平衡二叉树的结构 
  7. typedef struct AVLNode{
  8. 	int depth;//深度
  9. 	struct AVLNode *left;//左孩子 
  10. 	struct AVLNode *right;//右孩子 
  11. 	struct AVLNode *parent;//父结点 
  12. 	ElenmentType value; //值 
  13. }AVLtree,Tree;
  14. //初始化 
  15. Tree* Init(ElenmentType value){
  16. 	Tree* root=new Tree();
  17. 	root->parent = NULL;
  18.     root->depth = 0;
  19.     root->left = root->right = NULL;
  20.     root->value=value; 
  21.     return root;
  22. }
  23.  
  24. //LL型调整函数,执行右旋
  25. Tree* LL_rotate(Tree *root){
  26.     Tree *temp;
  27. 	temp = root->left;
  28. 	root->left = temp->right;
  29. 	temp->right = root;
  30. 	return temp; 
  31.    
  32. }
  33. //RR型调整函数,执行左旋 
  34. Tree* RR_rotate(Tree * root){
  35.     Tree* temp;
  36.     temp = root->right;
  37.     root->right = temp->left;
  38.     temp->left = root;
  39.     return temp;
  40. }
  41. //LR型调整函数，先左旋转，再右旋转
  42. Tree* LR_rotate(Tree* root){
  43. 	Tree* temp;
  44. 	temp = root->left;
  45.     root->left =RR_rotate(temp);
  46.     return LL_rotate(root);
  47. } 
  48. //RL型调整函数，先右旋转，再左旋转
  49. Tree* RL_rotate(Tree* root){
  50. 	 Tree* temp;
  51. 	 temp = root->right;
  52.     root->right=LL_rotate(temp);
  53.     return RR_rotate(root);
  54. } 
  55.  
  56. //树高
  57. int height(Tree* root)
  58. {
  59.     if (root == NULL)
  60.         return 0;
  61.     int max;
  62.     int left=height(root->left);
  63.     int right=height(root->right);
  64.     if(left>=right)
  65.     max=left;
  66.     else
  67.     max=right;
  68.     return max+1;
  69. }
  70. //求叶子节点个数
  71. int  GetSumOfLeafNode(Tree* root)
  72. {
  73. 	if(root == NULL)
  74. 		return 0;
  75. 	
  76. 	if(root->left == NULL && root->right == NULL)
  77. 		return 1;
  78. 	else
  79. 	{
  80. 		return GetSumOfLeafNode(root->left) 
  81. 			+ GetSumOfLeafNode(root->right);
  82. 	}
  83. }
  84. //平衡因子，即当前节点左右子树的差
  85. int diff(Tree* root)
  86. {
  87.     return height(root->left) - height(root->right);
  88. }
  89.  
  90. //平衡操作
  91. Tree* Balance(Tree* root)
  92. {
  93.     int balanceFactor = diff(root);//平衡因子（左右子树高度差）
  94.     if (balanceFactor > 1)//左子树高于右子树
  95.     {
  96.         if (diff(root->left) > 0)
  97. 		//LL的情况 
  98.             root=LL_rotate(root);
  99.         else
  100. 		//LR的情况 
  101.             root=LR_rotate(root);
  102.     }
  103.     else if (balanceFactor < -1)//右子树高于左子树
  104.     {
  105.         if (diff(root->right) > 0)
  106. 		//RL的情况 
  107.             root=RL_rotate(root);
  108.         else
  109. 		//RR的情况 
  110.             root=RR_rotate(root);
  111.     }
  112.     return root;
  113. } 
  114. //插入结点
  115. Tree* Insert(Tree* root,ElenmentType k )
  116. {
  117.     if (NULL == root)
  118.     {
  119.         root = Init(k);//如果根结点为null，则直接将值为根结点 
  120.         if(root==NULL)
  121.         	cout<<"创建失败"<<endl; 
  122.         return root;
  123.     }
  124.     else if (k < root->value)
  125.     {
  126.         root->left = Insert(root->left, k);//递归左子树
  127.         root = Balance(root);//平衡操作
  128.     }
  129.     else if (k>root->value)
  130.     {
  131.         root->right = Insert(root->right, k);//递归右子树
  132.         root = Balance(root);//平衡操作
  133.     }
  134.     return root;
  135. } 
  136. //前序遍历
  137. void displayTree_Pre(Tree* node){
  138.         if(node == NULL) return;
  139.         cout<<node->value<<" ";
  140.         if(node->left != NULL){
  141.             displayTree_Pre(node->left);
  142.         }
  143.         if(node->right != NULL){
  144.             displayTree_Pre(node->right);
  145.         }
  146. }
  147. //中序遍历
  148. void displayTree_Mid(Tree* node){
  149.         if(node == NULL) return;
  150.         if(node->left != NULL){
  151.             displayTree_Mid(node->left);
  152.         }
  153.         cout<<node->value<<" ";
  154.         if(node->right != NULL){
  155.             displayTree_Mid(node->right);
  156.         }
  157. }
  158. //后序遍历
  159. void displayTree_Post(Tree* node){
  160.         if(node == NULL) return;
  161.         if(node->left != NULL){
  162.             displayTree_Post(node->left);
  163.         }
  164.         if(node->right != NULL){
  165.             displayTree_Post(node->right);
  166.         }
  167.         cout<<node->value<<" ";
  168. }
  169. //查找value 
  170. Tree* binaryTreeSearch(Tree *node,int value){
  171. 	if(node->value==value)
  172. 		return node;
  173. 	//大于，在左边找 
  174. 	else if(node->value>value){
  175. 		if(node->left!=NULL)
  176. 			return binaryTreeSearch(node->left,value);
  177. 		else return NULL;
  178. 	}
  179. 	//否则，在右边找 
  180. 	else{
  181. 		if(node->right!=NULL)
  182. 			return binaryTreeSearch(node->right,value);
  183. 		else
  184. 			return NULL;
  185. 	}
  186. }
  187.  
  188. //平衡二叉树最大值 
  189. ElenmentType tree_max(Tree *node){
  190. 	int value;
  191. 	value=node->value;
  192. 	if(node->right!=NULL)
  193. 	return tree_max(node->right);
  194. 	else
  195. 	return value;
  196. 	
  197. }
  198. //平衡二叉树最小值 
  199. ElenmentType tree_min(Tree *node){
  200. 	int value;
  201. 	value=node->value;
  202. 	if(node->left!=NULL)
  203. 	return tree_min(node->left);
  204. 	else
  205. 	return value;
  206. }
  207.  
  208. //删除结点
  209. Tree* Delete(Tree *root, const ElenmentType k)
  210. {
  211.     if (NULL == root)
  212.         return root;
  213.     if (!binaryTreeSearch(root,k))//查找删除元素是否存在
  214.     {
  215.         cout<<"删除失败，未找到"<<endl;
  216.         return root;
  217.     }
  218.  
  219.     if (k == root->value)//根节点
  220.     {
  221.         if (root->left!=NULL&&root->right!=NULL)//左右子树都非空
  222.         {
  223.             if (diff(root) > 0)//左子树更高，在左边删除
  224.             {
  225.                 root->value = tree_max(root->left);//以左子树的最大值替换当前值
  226.                 root->left = Delete(root->left, root->value);//删除左子树中已经替换上去的节点
  227.             }
  228.             else//右子树更高，在右边删除
  229.             {
  230.                 root->value = tree_min(root->right);//以右子树的最小值替换当前值
  231.                 root->right = Delete(root->right, root->value);//删除右子树中已经替换上去的节点
  232.             }
  233.         }
  234.         else//有一个孩子、叶子节点的情况合并
  235.         {
  236.                 Tree * tmp = root;
  237.                 root = (root->left) ? (root->left) :( root->right);
  238.                 delete tmp;
  239.                 tmp = NULL;
  240.         }
  241.     }
  242.     //往左边删 
  243.     else if (k < root->value)
  244.     {
  245.         root->left = Delete(root->left, k);
  246.         //不满足平衡条件
  247. 		if (diff(root) < -1)
  248.         {
  249.             if (diff(root->right) > 0)
  250.             {
  251.                 root = RL_rotate(root);
  252.             }
  253.             else
  254.             {
  255.                 root = RR_rotate(root);
  256.             }
  257.         }
  258.     }
  259.     //往右边删 
  260.     else
  261.     {
  262.         root->right = Delete(root->right, k);
  263.         //不满足平衡 条件 
  264.         if (diff(root) > 1)
  265.         {
  266.             if (diff(root->left) < 0)
  267.             {
  268.                 root = LR_rotate(root);
  269.             }
  270.             else
  271.             {
  272.                 root = LL_rotate(root);
  273.             }
  274.         }
  275.     }
  276.     return root;
  277. }
  278.  
  279.  
  280.  
  281. int main(){
  282. 	int a[10]={12,13,55,66,44,77,99,33,46,79};
  283. 	Tree *root=NULL;
  284. 	for(int i=0;i<10;i++){
  285. 		root = Insert(root,a[i]);
  286. 	}
  287. 	cout<<"平衡二叉树前序遍历：";
  288. 	displayTree_Pre(root);
  289. 	cout<<endl; 
  290. 	cout<<"平衡二叉树中序遍历：";
  291. 	displayTree_Mid(root);
  292. 	cout<<endl; 
  293. 	cout<<"平衡二叉树高度："<<height(root)<<endl; 
  294. 	int value = 33;
  295. 	cout<<"平衡二叉树最大值："<<tree_max(root)<<endl;
  296. 	cout<<"平衡二叉树最小值："<<tree_min(root)<<endl;
  297. 	cout<<"平衡二叉树叶子结点："<<GetSumOfLeafNode(root)<<endl; 
  298. 	Tree* obj;
  299. 	if((obj=binaryTreeSearch(root,value))==NULL){
  300. 		cout<<value<<"值不存在"<<endl;
  301. 	}
  302. 	else 
  303. 	    cout<<value<<"值存在"<<endl;
  304. 	root = Insert(root,5);
  305. 	cout<<"插入结点5后，前序遍历：";
  306.     displayTree_Pre(root);
  307. 	cout<<endl;
  308. 	cout<<"插入结点5后，中序遍历：";
  309. 	displayTree_Mid(root);
  310. 	cout<<endl;
  311. 	int del=79;
  312. 	if (!binaryTreeSearch(root,del))//查找删除元素是否存在
  313.     {
  314.         cout<<"删除失败，未找到要删除的结点"<<endl;
  315.     }else{
  316.     	Delete(root,del);
  317.     	cout<<"删除结点后,前序遍历： ";
  318.     	displayTree_Pre(root);
  319.     	cout<<endl;
  320.     	cout<<"删除结点后,中序遍历： ";
  321.     	displayTree_Mid(root);
  322.     	cout<<endl;
  323. 	} 
  324. 	return 0;
  325. }

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

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

  

闽ICP备14008679号