• 【数据结构】二叉树---AVL树的实现

          

    目录

    一.  什么是AVL树

    二.  AVL树的结点结构定义

    三.  AVL树的动态平衡法

    1. 左单旋转 --- RL(RotateLeft) 型调整操作

    2. 右单旋转 --- RR(RotateRight) 型调整操作

    3. 先左后右双旋转 --- RLR (RotateLeftRight) 型调整操作

    4. 先右后左双旋转 --- RRL (RotateRightLeft) 型调整操作

    四.  AVL树的插入操作

    五.  AVL树的验证操作

    六.  完整源代码

    一.  什么是AVL树

    AVL树，又称平衡二叉树。   

           它可以是一颗空树，或者是具有以下性质的二叉树：即它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度只差的绝对值不超过 1。 把二叉树上结点的平衡因子BF定义为该结点的左子树的高度和右子树的高度之差（即平衡二叉树上结点的平衡因子只可能是 -1、0 和 1）

           只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

       说明：后面所用到的平衡因子的都是右子树的高的 - 左子树的高度

    二.  AVL树的结点结构定义

           影响二叉搜索树平衡的操作只能是插入和删除，这里已插入为例，同样一组数据元素插  入的顺序不同，二叉搜索树的形状就不同。也就需要一种动态平衡方法，当插入操作破坏了平衡，便可以用来调整。这种方式需要在原来二叉搜索树结点中增加一个量为平衡因子(BF)

    结点结构图：

    在这里为了方便进行旋转操作对于AVL树的结点定义采用三叉链的结构：

    1. //类模板结点的定义
    2. template <class T>
    3. struct AVLTreeNode
    4. {
    5. 	AVLTreeNode* _left;
    6. 	AVLTreeNode* _right;
    7. 	AVLTreeNode* _parent;   //指向当前结点的父节点的指针
    8.     AVLTreeNode _data;
    9. 	int _bf;                      //平衡因子
    10.  
    11.     //结点的构造函数
    12. 	AVLTreeNode(const T& data)
    13. 		:_left(nullptr)
    14. 		,_right(nullptr)
    15. 		,_parent(nullptr)
    16. 		,_bf(0)
    17. 		,_data(data)
    18. 	{}
    19.  
    20. };

    三.  AVL树的动态平衡法

            如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构， 使之平衡化。根据节点插入位置的不同，AVL树的旋转分为以下四种：

    1. 左单旋转 --- RL(RotateLeft) 型调整操作

          单向左旋平衡处理: 由于在subR这个结点的右子树上插入结点 ，subR的平衡因子由0变为1，p的平衡因子由1变为2，导致以p为根的子树失去平衡，则需进行一次向左的逆时针旋转操作

        链接操作：b链接到p的右；

                          p链接到subR的左；

                          subR成为当前树的根

    注意：1. 链接时subRL为空的情况

               2. p可能是整棵树的子树 (p的上面可能还有结点) 或 整棵树的根 (p的上面无结点)

    图示：

    1.     //左单旋转
    2. 	void RotateL(Node* parent)
    3. 	{
    4. 		Node* subR = parent->_right;
    5. 		Node* subRL = subR->_left;
    6.  
    7. 		//做左旋转（修改结点的指向）
    8. 		parent->_right = subRL;
    9. 		if (subRL)                  //若subRL不为空，则修改subRL中指向父节点的指针(_parent)
    10. 			subRL->_parent = parent;
    11. 		subR->_left = parent;
    12.  
    13. 		//修改各结点中父指针(_parent)的指向
    14. 		Node* ppnode = parent->_parent;         //保存parent中父指针(_parent)的指向
    15. 		parent->_parent = subR;                 //修改parent中指向父节点的指针(_parent)
    16.  
    17. 		if (parent == _root)                    //判断当前结点是否为根节点
    18. 		{
    19. 			_root = subR;
    20. 			subR->_parent = nullptr;
    21. 		}
    22. 		else
    23. 		{
    24. 			if (ppnode->_right == parent)
    25. 			{
    26. 				ppnode->_right = subR;
    27. 			}
    28. 			else
    29. 			{
    30. 				ppnode->_left = subR;
    31. 			}
    32. 			subR->_parent = ppnode;
    33. 		}
    34. 		//更新平衡因子
    35. 		parent->_bf = 0;
    36. 		subR->_bf = 0;
    37. 	}

    2. 右单旋转 --- RR(RotateRight) 型调整操作

      单向右旋平衡处理: 由于在subL的左子树上插入结点，subL的平衡因子由 0变成 -1 ，p的平衡因子由 1 变为 -2，导致以p为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。

       链接操作：b链接到p的左；

                         p链接到subL的右；

                         subL成为当前树的根

    注意：1. 链接时subLR为空的情况

               2. p可能是整棵树的子树 (p的上面可能还有结点) 或 整棵树的根 (p的上面无结点)

    图示：

    1. 	//右单旋转
    2. 	void RotateR(Node* parent)
    3. 	{
    4. 		Node* subL = parent->_left;
    5. 		Node* subLR = subL->_right;
    6.  
    7. 		//做右旋转（修改结点的指向）
    8. 		parent->_left = subLR;
    9. 		if (subLR)                  //若subLR不为空，则修改subLR中指向父节点的指针(_parent)
    10. 			subLR->_parent = parent;
    11. 		subL->_right = parent;
    12.  
    13. 		//修改各结点中父指针(_parent)的指向
    14. 		Node* ppnode = parent->_parent;     //保存parent中父指针(_parent)的指向
    15. 		parent->_parent = subL;             //修改parent中指向父节点的指针(_parent)
    16.  
    17. 		if (parent == _root)                //判断当前结点是否为根节点
    18. 		{
    19. 			_root = subL;
    20. 			subL->_parent = nullptr;
    21. 		}
    22. 		else
    23. 		{
    24. 			if (ppnode->_left == parent)
    25. 			{
    26. 				ppnode->_left = subL;
    27. 			}
    28. 			else
    29. 			{
    30. 				ppnode->_right = subL;
    31. 			}
    32. 			subL->_parent = ppnode;
    33. 		}
    34.  
    35. 		//更改平衡因子
    36. 		parent->_bf = 0;
    37. 		subL->_bf = 0;
    38. 	}

    3. 先左后右双旋转 --- RLR (RotateLeftRight) 型调整操作

      双向旋转(先左后右)平衡处理：由于在subL的右子树上插入结点，subL的平衡因子由 0 变为 1，p的平衡因子由 -1 变为 -2，导致以p为根的子树失去平衡，则需进行两次旋转(先左旋后右旋)操作

       链接操作：左单旋：b链接到subL的右；

                                        subL链接到subLR的左；

                                        subLR链接到p的左

                          右单旋：c链接到p的左；

                                         p链接到subLR的右；

                                         subLR成为当前子树的根

    图示：

    1.     //先左后右双旋转
    2. 	void RotateLR(Node* parent)
    3. 	{
    4. 		Node* subL = parent->_left;
    5. 		Node* subLR = subL->_right;
    6.  
    7. 		int bf = subLR->_bf;    //先保存旋转前subLR结点的平衡因子
    8. 		RotateL(parent->_left); //左单旋转
    9. 		RotateR(parent);        //右单旋转
    10.  
    11. 		//更新旋转后的平衡因子
    12. 		if (bf == -1)
    13. 		{
    14. 			subLR->_bf = 0;
    15. 			subL->_bf = 0;
    16. 			parent->_bf = 1;
    17. 		}
    18. 		else if (bf == 1)
    19. 		{
    20. 			subLR->_bf = 0;
    21. 			subL->_bf = -1;
    22. 			parent->_bf = 0;
    23. 		}
    24. 		else if (bf == 0)
    25. 		{
    26. 			subLR->_bf = 0;
    27. 			subL->_bf = 0;
    28. 			parent->_bf = 0;
    29. 		}
    30. 		else
    31. 		{
    32. 			assert(false);
    33. 		}
    34. 	}

    4. 先右后左双旋转 --- RRL (RotateRightLeft) 型调整操作

      双向旋转(先右后左)平衡处理：由于在subR的左子树上插入结点，subR的平衡因子由 0 变为 -1，p的平衡因子由 1 变为 2，导致以p为根的子树失去平衡，则需进行两次旋转(先右旋后左旋)操作

       链接操作：右单旋：c链接到subR的左；

                                        subR链接到subRL的右；

                                        subRL链接到p的右

                         左单旋：b链接到p的右；

                                        p链接到subRL的左；

                                        subRL成为当前子树的根

         

    图示：

    1.     //先右后左双旋转
    2. 	void RotateRL(Node* parent)
    3. 	{
    4. 		Node* subR = parent->_right;
    5. 		Node* subRL = subR->_left;
    6.  
    7. 		int bf = subRL->_bf;    //先保存旋转前subRL结点的平衡因子            
    8. 		RotateR(subR);          //右单旋转
    9. 		RotateL(parent);        //左单旋转
    10.  
    11. 		//更新旋转后的平衡因子
    12. 		if (bf == 1)
    13. 		{
    14. 			subRL->_bf = 0;
    15. 			subR->_bf = 0;
    16. 			parent->_bf = -1;
    17. 		}
    18. 		else if (bf == -1)
    19. 		{
    20. 			subRL->_bf = 0;
    21. 			subR->_bf = 1;
    22. 			parent->_bf = 0;
    23. 		}
    24. 		else if(bf==0)
    25. 		{
    26. 			subRL->_bf = 0;
    27. 			subR->_bf = 0;
    28. 			parent->_bf = 0;
    29. 		}
    30. 		else
    31. 		{
    32. 			assert(false);
    33. 		}
    34. 	}

    四.  AVL树的插入操作

            AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步：

           1. 按照二叉搜索树的方式插入新节点

           2. 调整节点的平衡因子      

            插入一个结点cur(当前要插入的结点)后，Parent的平衡因子一定需要调整，在插入之前，Parent 的平衡因子分为三种情况：-1，0, 1;

    分以下两种情况：  

          1. 如果cur插入到Parent的左侧，只需给 Parent 的平衡因子 减1 即可  

          2. 如果cur插入到Parent的右侧，只需给 Parent 的平衡因子 加1 即可  

    此时：Parent的平衡因子可能有三种情况：0，1或-1， 2或-2  

          1. 如果Parent的平衡因子为 0，说明插入之前Parent的平衡因子为 1或-1，插入后被调整成 0，此时满足 AVL树的性质，插入成功  

          2. 如果Parent的平衡因子为 1或-1，说明插入前Parent的平衡因子一定为 0，插入后被更新成 1或-1，此时，以Parent为根的树的高度增加，需要继续向上更新  

          3. 如果Parent的平衡因子为 2或-2，则Parent的平衡因子违反平衡树的性质，需要对其进行旋转处理

    1. bool Insert(const T& data)
    2. {
    3.     //为空树
    4. 	if (_root == nullptr)
    5. 	{
    6. 		_root = new Node(data);
    7. 		return true;
    8. 	}
    9.     
    10.     //按照二叉搜索树的规则插入结点
    11. 	Node* parent = nullptr;  //记录插入结点的父节点
    12. 	Node* cur = _root;
    13. 	while (cur)
    14. 	{
    15. 		if (cur->_data < data)
    16. 		{
    17. 			parent = cur;
    18. 			cur = cur->_right;
    19. 		}
    20. 		else if (cur->_data > data)
    21. 		{
    22. 			parent = cur;
    23. 			cur = cur->_left;
    24. 		}
    25. 		else
    26. 		{
    27. 			return false;
    28. 		}
    29. 	}
    30.  
    31.     //判断链接到父节点的那边
    32. 	cur = new Node(data);
    33. 	if (parent->_data > data)
    34. 	{
    35. 		parent->_left = cur;
    36. 	}
    37. 	else
    38. 	{
    39. 		parent->_right = cur;
    40. 	}
    41.  
    42. 	//调整平衡因子 及 旋转调整 
    43. 	cur->_parent = parent; //修改当前结点(cur)的父指针（_parent）的指向
    44. 	while (parent)
    45. 	{
    46. 		if (cur == parent->_left) //插入到父结点的左边，父节点的平衡因子--
    47. 		{
    48. 			parent->_bf--;
    49. 		}
    50. 		else                 //插入到父结点的左边，父节点的平衡因子--
    51. 		{
    52. 			parent->_bf++;
    53. 		}
    54. 		//
    55. 		if (parent->_bf == 0)   //若（插入节点后）当前结点的平衡因子为零，则不会影响此节点的父及祖先结点；
    56. 		{                       //说明当前这颗子树插入节点后，其高度没有发生变化，也就不需要向上更新平衡因子
    57. 			break;
    58. 		}
    59. 		else if (parent->_bf == 1 || parent->_bf == -1)  //若当前结点的平衡因子为1或-1，则会影响上面的祖先结点的平衡因子
    60. 		{											     //需要更新上面祖先的平衡因子
    61. 			cur = cur->_parent;
    62. 			parent = parent->_parent;
    63. 		}
    64. 		else if (parent->_bf == 2 || parent->_bf == -2)//若当前结点的平衡因子为2或-2,则需做旋转调整
    65. 		{
    66. 			//旋转
    67. 			if (parent->_bf == 2 && cur->_bf == 1)
    68. 			{
    69. 				RotateL(parent); //左单旋转
    70. 			}
    71. 			else if (parent->_bf == -2 && cur->_bf == -1)
    72. 			{
    73. 				RotateR(parent); //右单旋转
    74. 			}
    75. 			else if (parent->_bf == -2 && cur->_bf == 1)
    76. 			{
    77. 				RotateLR(parent); //先左单旋转，在右单旋转
    78. 			}
    79. 			else
    80. 			{
    81. 				RotateRL(parent); //先右单旋转，在左单旋转
    82. 			}
    83.  
    84. 			break;
    85. 		}
    86. 		else            //说明插入之前AVL数就有问题
    87. 		{
    88. 			assert(false);
    89. 		}
    90. 	}
    91. 	return true;
    92. }

    五.  AVL树的验证操作

    AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

         1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

                验证方法：采用中序遍历即可

         2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1

             (注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确

                验证方法：1.验证每颗子树的左右高度差的绝对值是否超过 1（采用递归思想）；

                                  2.验证结点的平衡因子是否正确

    1.     //中序遍历
    2. 	void InOrder(Node* root)
    3. 	{
    4. 		if (root == nullptr)
    5. 			return;
    6. 		InOrder(root->_left);
    7. 		cout << root->_data << endl;
    8. 		InOrder(root->_right);
    9. 	}
    10.  
    11.  
    12.     //求树的高度
    13.     int _Height(Node* root)
    14. 	{
    15. 		if (root == nullptr)
    16. 			return 0;
    17. 		int leftheight = _Height(root->_left);
    18. 		int rightheight = _Height(root->_right);
    19. 		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
    20. 	}
    21.  
    22.  
    23.     // 验证AVL树的平衡
    24. 	bool _IsAVLTree1(Node* root) //前序遍历 
    25. 	{
    26. 		if (root == nullptr)
    27. 			return true;
    28.  
    29. 		int leftheight = _Height(root->_left);  //左子树的高度
    30. 		int rightheight = _Height(root->_right); //右子树的高度
    31.         
    32.         //判断左右高度差是否超过1
    33. 		if (abs(rightheight - leftheight) >= 2)
    34. 		{
    35. 			cout << root->_data << "不平衡" << endl;
    36. 			return false;
    37. 		}
    38. 		
    39.         //判断结点的平衡因子是否有异常	
    40. 		if (rightheight - leftheight != root->_bf)
    41. 		{
    42. 			cout << root->_data << "平衡因子异常" << endl;
    43. 			return false;
    44. 		}
    45.  
    46. 		return _IsAVLTree1(root->_left) && _IsAVLTree1(root->_right);
    47. 	}

    六.  完整源代码

    1. template <class T>
    2. struct AVLTreeNode
    3. {
    4. 	AVLTreeNode* _left;
    5. 	AVLTreeNode* _right;
    6. 	AVLTreeNode* _parent;   //指向当前结点的父节点的
    7. 	int _bf;                      //平衡因子
    8. 	T _data;
    9.  
    10. 	AVLTreeNode(const T& data)
    11. 		:_left(nullptr)
    12. 		,_right(nullptr)
    13. 		,_parent(nullptr)
    14. 		,_bf(0)
    15. 		,_data(data)
    16. 	{}
    17.  
    18. };
    19.  
    20. template<class T>
    21. class AVLTree
    22. {
    23. 	typedef AVLTreeNode Node;
    24. public:
    25.  
    26. 	AVLTree()
    27. 		: _root(nullptr)
    28. 	{}
    29.  
    30. 	bool Insert(const T& data)
    31. 	{
    32. 		if (_root == nullptr)
    33. 		{
    34. 			_root = new Node(data);
    35. 			return true;
    36. 		}
    37.  
    38. 		Node* parent = nullptr;
    39. 		Node* cur = _root;
    40. 		while (cur)
    41. 		{
    42. 			if (cur->_data < data)
    43. 			{
    44. 				parent = cur;
    45. 				cur = cur->_right;
    46. 			}
    47. 			else if (cur->_data > data)
    48. 			{
    49. 				parent = cur;
    50. 				cur = cur->_left;
    51. 			}
    52. 			else
    53. 			{
    54. 				return false;
    55. 			}
    56. 		}
    57.  
    58. 		cur = new Node(data);
    59. 		if (parent->_data > data)
    60. 		{
    61. 			parent->_left = cur;
    62. 		}
    63. 		else
    64. 		{
    65. 			parent->_right = cur;
    66. 		}
    67.  
    68. 		//调整平衡因子 及 旋转调整 
    69. 		cur->_parent = parent; 
    70. 		while (parent)
    71. 		{
    72. 			if (cur == parent->_left) //插入到父结点的左边，父节点的平衡因子--
    73. 			{
    74. 				parent->_bf--;
    75. 			}
    76. 			else                 //插入到父结点的左边，父节点的平衡因子--
    77. 			{
    78. 				parent->_bf++;
    79. 			}
    80. 			
    81. 			if (parent->_bf == 0)   
    82. 			{                       
    83. 				break;
    84. 			}
    85. 			else if (parent->_bf == 1 || parent->_bf == -1) 
    86. 			{											     //需要更新上面祖先的平衡因子
    87. 				cur = cur->_parent;
    88. 				parent = parent->_parent;
    89. 			}
    90. 			else if (parent->_bf == 2 || parent->_bf == -2)
    91. 			{
    92. 				//旋转
    93. 				if (parent->_bf == 2 && cur->_bf == 1)
    94. 				{
    95. 					RotateL(parent); //左单旋转
    96. 				}
    97. 				else if (parent->_bf == -2 && cur->_bf == -1)
    98. 				{
    99. 					RotateR(parent); //右单旋转
    100. 				}
    101. 				else if (parent->_bf == -2 && cur->_bf == 1)
    102. 				{
    103. 					RotateLR(parent); //先左单旋转，在右单旋转
    104. 				}
    105. 				else
    106. 				{
    107. 					RotateRL(parent); //先右单旋转，在左单旋转
    108. 				}
    109.  
    110. 				break;
    111. 			}
    112. 			else            //说明插入之前AVL数就有问题
    113. 			{
    114. 				assert(false);
    115. 			}
    116. 		}
    117. 		return true;
    118. 	}
    119.  
    120. 	//左单旋转
    121. 	void RotateL(Node* parent)
    122. 	{
    123. 		Node* subR = parent->_right;
    124. 		Node* subRL = subR->_left;
    125.  
    126. 		//做左旋转（修改结点的指向）
    127. 		parent->_right = subRL;
    128. 		if (subRL)                  //若subRL不为空，则修改subRL中指向父节点的指针(_parent)
    129. 			subRL->_parent = parent;
    130. 		subR->_left = parent;
    131.  
    132. 		//修改各结点中父指针(_parent)的指向
    133. 		Node* ppnode = parent->_parent;         //保存parent中父指针(_parent)的指向
    134. 		parent->_parent = subR;                 //修改parent中指向父节点的指针(_parent)
    135.  
    136. 		if (parent == _root)                    //判断当前结点是否为根节点
    137. 		{
    138. 			_root = subR;
    139. 			subR->_parent = nullptr;
    140. 		}
    141. 		else
    142. 		{
    143. 			if (ppnode->_right == parent)
    144. 			{
    145. 				ppnode->_right = subR;
    146. 			}
    147. 			else
    148. 			{
    149. 				ppnode->_left = subR;
    150. 			}
    151. 			subR->_parent = ppnode;
    152. 		}
    153. 		//更新平衡因子
    154. 		parent->_bf = 0;
    155. 		subR->_bf = 0;
    156. 	}
    157.  
    158. 	//右单旋转
    159. 	void RotateR(Node* parent)
    160. 	{
    161. 		Node* subL = parent->_left;
    162. 		Node* subLR = subL->_right;
    163.  
    164. 		//做右旋转（修改结点的指向）
    165. 		parent->_left = subLR;
    166. 		if (subLR)                  //若subLR不为空，则修改subLR中指向父节点的指针(_parent)
    167. 			subLR->_parent = parent;
    168. 		subL->_right = parent;
    169.  
    170. 		Node* ppnode = parent->_parent;   
    171. 		parent->_parent = subL;             
    172.  
    173. 		if (parent == _root)              
    174. 		{
    175. 			_root = subL;
    176. 			subL->_parent = nullptr;
    177. 		}
    178. 		else
    179. 		{
    180. 			if (ppnode->_left == parent)
    181. 			{
    182. 				ppnode->_left = subL;
    183. 			}
    184. 			else
    185. 			{
    186. 				ppnode->_right = subL;
    187. 			}
    188. 			subL->_parent = ppnode;
    189. 		}
    190.  
    191. 		//更改平衡因子
    192. 		parent->_bf = 0;
    193. 		subL->_bf = 0;
    194. 	}
    195.  
    196. 	//先左后右双旋转
    197. 	void RotateLR(Node* parent)
    198. 	{
    199. 		Node* subL = parent->_left;
    200. 		Node* subLR = subL->_right;
    201.  
    202. 		int bf = subLR->_bf;    
    203. 		RotateL(parent->_left); 
    204. 		RotateR(parent);        
    205.  
    206. 		//更新旋转后的平衡因子
    207. 		if (bf == -1)
    208. 		{
    209. 			subLR->_bf = 0;
    210. 			subL->_bf = 0;
    211. 			parent->_bf = 1;
    212. 		}
    213. 		else if (bf == 1)
    214. 		{
    215. 			subLR->_bf = 0;
    216. 			subL->_bf = -1;
    217. 			parent->_bf = 0;
    218. 		}
    219. 		else if (bf == 0)
    220. 		{
    221. 			subLR->_bf = 0;
    222. 			subL->_bf = 0;
    223. 			parent->_bf = 0;
    224. 		}
    225. 		else
    226. 		{
    227. 			assert(false);
    228. 		}
    229. 	}
    230.  
    231. 	//先右后左双旋转
    232. 	void RotateRL(Node* parent)
    233. 	{
    234. 		Node* subR = parent->_right;
    235. 		Node* subRL = subR->_left;
    236.  
    237. 		int bf = subRL->_bf;    
    238. 		RotateR(subR); 
    239. 		RotateL(parent);   
    240.     
    241. 		//更新旋转后的平衡因子
    242. 		if (bf == 1)
    243. 		{
    244. 			subRL->_bf = 0;
    245. 			subR->_bf = 0;
    246. 			parent->_bf = -1;
    247. 		}
    248. 		else if (bf == -1)
    249. 		{
    250. 			subRL->_bf = 0;
    251. 			subR->_bf = 1;
    252. 			parent->_bf = 0;
    253. 		}
    254. 		else if(bf==0)
    255. 		{
    256. 			subRL->_bf = 0;
    257. 			subR->_bf = 0;
    258. 			parent->_bf = 0;
    259. 		}
    260. 		else
    261. 		{
    262. 			assert(false);
    263. 		}
    264. 	}
    265.     
    266.     //高度
    267. 	int Height()
    268. 	{
    269. 		return _Height(_root);
    270. 	}
    271.  
    272. 	// AVL树的验证
    273. 	bool IsAVLTree()
    274. 	{
    275. 		return _IsAVLTree1(_root);
    276. 	}
    277.  
    278. 	//中序遍历
    279. 	void InOrder()
    280. 	{
    281. 		_InOrder(_root);
    282. 	}
    283.  
    284. private:
    285. 	int _Height(Node* root)
    286. 	{
    287. 		if (root == nullptr)
    288. 			return 0;
    289. 		int leftheight = _Height(root->_left);
    290. 		int rightheight = _Height(root->_right);
    291. 		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
    292. 	}
    293.  
    294. 	// AVL树的验证
    295. 	bool _IsAVLTree1(Node* root) //前序遍历 
    296. 	{
    297. 		if (root == nullptr)
    298. 			return true;
    299.  
    300. 		int leftheight = _Height(root->_left);
    301. 		int rightheight = _Height(root->_right);
    302.  
    303. 		if (abs(rightheight - leftheight) >= 2)
    304. 		{
    305. 			cout << root->_data << "不平衡" << endl;
    306. 			return false;
    307. 		}
    308. 			
    309. 		if (rightheight - leftheight != root->_bf)
    310. 		{
    311. 			cout << root->_data << "平衡因子异常" << endl;
    312. 			return false;
    313. 		}
    314.  
    315. 		return _IsAVLTree1(root->_left) && _IsAVLTree1(root->_right);
    316. 	}
    317.  
    318. 	//中序遍历
    319. 	void _InOrder(Node* root)
    320. 	{
    321. 		if (root == nullptr)
    322. 			return;
    323. 		_InOrder(root->_left);
    324. 		cout << root->_data << endl;
    325. 		_InOrder(root->_right);
    326. 	}
    327.  
    328. private:
    329. 	Node* _root;
    330. };

  • 相关阅读:
    解密Prompt系列28. LLM Agent之金融领域摸索：FinMem & FinAgent
    从编译器对指令集的要求看API设计原则
    凉鞋的 Unity 笔记 203. 变量的常用类型
    设置IDEA快捷生成方法头，类头注释
    Linux三剑客：awk的基本用法
    SparkSQL外部数据源
    LeetCode精选100题-【3数之和】-2
    冷知识：Mysql最大列限制和行限制
    [论文-ing]Weakly Supervised Universal Fracture Detectionin Pelvic X-rays
    怎么写出美观，可读性高的代码？
  • 原文地址：https://blog.csdn.net/HZ_ENG/article/details/136658987