devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

详细图解,二叉排序树的遍历、删除、插入，通过bf优化构建成平衡二叉树(avl树)的原理_二叉排序树构造和遍历b

作者：凡人多烦事01 | 2024-06-12 21:12:36

赞

踩

二叉排序树构造和遍历b

目录

一.二叉排序树的建立

二.二叉树的遍历

三.改造树结构

四.有序二叉树的查找

五.二叉排序树的节点删除

六.二叉排序树优化成平衡二叉树

七.平衡二叉树的建立过程

八.总结

一.二叉排序树的建立

1.数据结构定义

  1. class TreeNode
  2. {
  3. public:
  4. 	int m_data = 0; //数据
  5. 	TreeNode* m_lch = NULL; //左节点
  6. 	TreeNode* m_rch = NULL; //右节点
  7. 	TreeNode* m_father = NULL; //父亲节点
  8. };
  9.  
  10. class Tree
  11. {
  12. public:
  13. 	void PreOrderVisit(TreeNode* node); //前序遍历
  14. 	void InOrderVisit(TreeNode* node);  //中序遍历
  15. 	void PostOrderVisit(TreeNode* node);//后序遍历
  16. 	void InitTree(int* pArr, int n );
  17. 	
  18. private:
  19. 	void AddChild(TreeNode* TT, TreeNode* node);
  20. 	TreeNode* m_root = NULL;
  21. }

                                下图展示了数据10,7,20,3,1,5,17构建一个有序二叉树的过程。

1.当树为空时，第一个数据设置为root。                                                                               

2.新加入的数据如果比root小，root的左孩子为空，就加到root的左孩子节点。

3.新加入的数据如果比root大，root的右孩子为空，就加到root的右孩子节点。

4.如果新加入的数据比root小，且root的左孩子不为空，那把root的左孩子当作新ROOT，重复2，3，4，5步骤。

5.如果新加入的数据比root大，且root的右孩子不为空，那把root的右孩子当作新的ROOT，重复2，3，4，5步骤。

  1. void AddChild(TreeNode* TT, TreeNode* node)
  2. 	{
  3. 		if(m_root == NULL)
  4. 		{
  5. 			m_root = node;
  6. 			return ;
  7. 		}
  8. 		int cmp = node->m_data < TT->m_data;
  9. 		if(cmp > 0) //如果数据比TT节点小，就找TT节点的左孩子比较
  10. 		{
  11. 			if(TT->m_lch == NULL)
  12. 			{
  13. 				SetLChild(TT, node);
  14. 				return;
  15. 			}
  16. 			else //如果左节点不为空，递归到左节点
  17. 			{
  18. 				AddChild(TT->m_lch, node);
  19. 				return;
  20. 			}
  21. 		}
  22. 		else  //如果数据比TT节点大，就找TT节点的右孩子比较
  23. 		{
  24. 			if(TT->m_rch == NULL)
  25. 			{
  26. 				SetRChild(TT, node);
  27. 				return;
  28. 			}
  29. 			else //如果右节点不为空，递归到左节点
  30. 			{
  31. 				AddChild(TT->m_rch, node);
  32. 				return;
  33. 			}
  34. 		}
  35. 	}
  36. void SetLChild(TreeNode* node, TreeNode* L)
  37. 	{
  38. 		if(node == NULL)
  39. 			return;
  40. 		node->m_lch = L;
  41. 		if(L)
  42. 			L->m_father = node;
  43. 	}
  44. 	void SetRChild(TreeNode* node, TreeNode* R)
  45. 	{
  46. 		if(node == NULL)
  47. 			return;
  48. 		node->m_rch = R;
  49. 		if(R)
  50. 			R->m_father = node;
  51. 	}

二.二叉树的遍历

二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次。根据根节点的访问顺序有以下三种方式。

前序遍历，先访问根节点，再遍历左孩子，再遍历右孩子。上图访问顺序10 7 3 1 5 20 17

中序遍历，先中序遍历自己的左子树，再访问根节点，然后中序遍历自己右子树。上图访问顺序1 3 5 7 10 17 20

后序遍历，先后序遍历自己的左子树，再后序遍历自己的右子树，再访问根节点。上图访问顺序1 5 3 7 17 20 10

很显然一棵有序二叉树，用中序遍历就能按数据大小顺序依次输出。

代码利用递归方法实现很简单。

  1. void PreOrderVisit(TreeNode* node)
  2. 	{
  3. 		if(node == NULL)
  4. 			return;
  5. 		cout << node->m_data << " ";
  6. 		PreOrderVisit(node->m_lch);
  7. 		PreOrderVisit(node->m_rch);
  8. 	}
  9. 	void InOrderVisit(TreeNode* node)
  10. 	{
  11. 		if(node == NULL)
  12. 			return;
  13. 		InOrderVisit(node->m_lch);
  14. 		cout << node->m_data << " ";
  15. 		InOrderVisit(node->m_rch);
  16. 	}
  17. 	void PostOrderVisit(TreeNode* node)
  18. 	{
  19. 		if(node == NULL)
  20. 			return;
  21. 		PostOrderVisit(node->m_lch);
  22. 		PostOrderVisit(node->m_rch);
  23. 		cout << node->m_data << " ";
  24. 	}

三.改造树结构

1.上述树节点存储的是int类型数据，我们使用模版TreeNode<T>使其能存储各种类型数据。

2.上述树默认是根据int类型数据升序排序，构建的有序二叉树。我们改造成能自定义排序使用升序还是降序，如果是存储自定义数据结构的，还可以自定义比较函数。

3.把树的遍历(打印输出)，改成自定义方法。

四.有序二叉树的查找

根据比较函数和排序顺序，选择左子树或者右子树进行递归遍历查找。

  1. TreeNode<T>* FindTreeNode(TreeNode<T>* node, T data, int sort(T, T)=NULL)
  2. 	{
  3. 		if(node == NULL)
  4. 			return NULL;
  5. 		else if(node->m_data == data)
  6. 			return node;
  7. 		
  8. 		int cmp = 0;
  9. 		if(sort!=NULL)
  10. 			cmp = sort(data, node->m_data);
  11. 		else
  12. 			cmp = data - node->m_data;
  13. 		
  14. 		if(m_ascendorder)
  15. 		{
  16. 			if(cmp >= 0)
  17. 				return FindTreeNode(node->m_rch, data);
  18. 			else
  19. 				return FindTreeNode(node->m_lch, data);
  20. 		}
  21. 		else
  22. 		{
  23. 			if(cmp >= 0)
  24. 				return FindTreeNode(node->m_lch, data);
  25. 			else
  26. 				return FindTreeNode(node->m_rch, data);
  27. 				
  28. 		}
  29. 		return NULL;
  30. 	}

五.二叉排序树的节点删除

1.对于删除只有左子树或者右子树的节点，那很简单只需要子承父业就行。

2.对于删除即有左子树又有右子树的节点，那就不太容易了，比如下图。

上面的中序遍历是29，35，36，37，47，48，49，50，51，56，58....... ，我们可以用47的前驱节点37，或者使用后驱节点48替换47的位置。

分析使用前驱节点替换方法：

1.先找到前驱节点，即删除节点的第一个左孩子的最后一个右孩子。为37，设为pre。

2.删除节点的右子树51，成为pre的右子树。

3.pre的左子树36，过继给pre的父节点35，成为35的右子树。

4.被删节点的第一个左节点35，成为pre的左孩子。

5.删除节点47(node)。把node替换成pre

  1. 	//删除节点，使用前驱节点替换方法
  2. 	//1.对于删除的节点，只有左孩子或右孩子时，很简单直接子承父业就行。
  3. 	//2.如果被删除的节点即有左孩子，又有右孩子，可以使用前驱节点替换方法，或者使用后驱节点替换方法。
  4. 	void DelTreeNode(TreeNode<T>* node)
  5. 	{
  6. 		if(node == NULL)
  7. 			return;
  8. 		
  9. 		if(node != m_root)
  10. 		{
  11. 			TreeNode<T>** pfatherchild;
  12. 			if(node->m_father->m_lch == node)
  13. 				pfatherchild = &node->m_father->m_lch;
  14. 			else
  15. 				pfatherchild = &node->m_father->m_rch;
  16. 			
  17. 			if(node->m_lch == NULL)//只有右支，子承父业
  18. 			{
  19. 				*pfatherchild = node->m_rch;
  20. 				if(node->m_rch)
  21. 					node->m_rch->m_father = node->m_father;
  22. 			}
  23. 			else if(node->m_rch == NULL)//只有左支，子承父业
  24. 			{
  25. 				*pfatherchild = node->m_lch;
  26. 				if(node->m_lch)
  27. 					node->m_lch->m_father = node->m_father;
  28. 				
  29. 			}
  30. 			else//即有左支，又有右支，使用中序遍历时的前驱节点替换
  31. 			{
  32. 				//第1步，找到删除节点的第一个左孩子的最右孩子，是中序遍历时node的前驱节点。
  33. 				TreeNode<T>* pre = node->m_lch;
  34. 				while (pre->m_rch)
  35. 					pre = pre->m_rch;
  36. 				
  37. 				//第2步，被删除节点的右支过继到pre的右孩子。
  38. 				SetRChild(pre, node->m_rch);
  39. 			
  40. 				if(pre == pre->m_father->m_rch)
  41. 				{
  42. 					//第3步，pre节点的左支过继给pre节点的父节点
  43. 					SetRChild(pre->m_father, pre->m_lch);
  44. 					//第4步，被删节点的第一个左节点，成为pre的左孩子
  45. 					SetLChild(pre, node->m_lch);
  46. 				}
  47. 				
  48. 				//第4步，node替换成pre节点
  49. 				{
  50. 					*pfatherchild = pre;
  51. 					pre->m_father = node->m_father;
  52. 				}
  53. 			}
  54. 			
  55. 		}
  56. 		else  //同样的方法对node==root时的特殊处理
  57. 		{
  58. 			TreeNode<T>* pre = m_root->m_lch; //找到删除节点的第一个左孩子
  59. 			if(pre)
  60. 			{
  61. 				while (pre->m_rch)
  62. 					pre = pre->m_rch;//第一个左孩子的最右孩子，就是中序遍历时node的前驱节点。
  63. 				
  64. 				if(pre == pre->m_father->m_rch)
  65. 				{
  66. 					SetRChild(pre->m_father, pre->m_lch);
  67. 					SetLChild(pre,  node->m_lch);
  68. 				}
  69. 				SetRChild(pre , node->m_rch);
  70.  
  71. 				m_root = pre;
  72. 				m_root->m_father = NULL;
  73. 			}
  74. 			else //删除的是根节点，且根节点没有左子树的情况
  75. 			{
  76. 				m_root = m_root->m_rch;
  77. 				if(m_root)
  78. 					m_root->m_father = NULL;
  79. 			}
  80. 		}
  81. 		
  82. 		delete node;
  83. 	}

六.二叉排序树优化成平衡二叉树

如果插入的数据顺序是1，2，3，4，5那么根据二叉排序树的建立过程，最后的树会是下图所示。此时查找5的话，需要遍历所有节点。为了提高查找效率，需要是它变成平衡二叉树，这样查找时间复杂度能变成O(log2N)

七.平衡二叉树的建立过程

1.平衡二叉树的特点

⑴：左子树和右子树深度之差的绝对值不大于1；

⑵：左子树和右子树也都是平衡二叉树。

平衡因子BF(Balance Factor) ：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子，因此平衡二叉树上每个结点的平衡因子只可能是-1、0和1

2.平衡二叉树，插入时平衡原理

在二叉排序树建立的基础上，每当插入一个新数据，计算各节点的平衡因子，如果绝对值大于1，就旋转使子树平衡。

 3.代码实现LL型，RR型，LR型，RL型树的旋转平衡

  1. 	//左左型树旋转,往右旋转
  2. 	void Rotate_LL(TreeNode<T>* root)
  3. 	{
  4. 		TreeNode<T>* rootf = root->m_father;
  5. 		TreeNode<T>* node = root->m_lch;
  6. 		if(rootf)
  7. 		{
  8. 			if(rootf->m_lch == root)
  9. 				SetLChild(rootf, node);
  10. 			else
  11. 				SetRChild(rootf, node);
  12. 		}
  13. 		else
  14. 		{
  15. 			m_root = node;
  16. 			m_root->m_father = NULL;
  17. 		}
  18. 		
  19. 		SetLChild(root, node->m_rch);
  20. 		SetRChild(node, root);
  21. 	}
  22. 	//右右型树旋转，往左旋转
  23. 	void Rotate_RR(TreeNode<T>* root)
  24. 	{
  25. 		
  26. 		TreeNode<T>* rootf = root->m_father;
  27. 		TreeNode<T>* node = root->m_rch;
  28. 		if(rootf)
  29. 		{
  30. 			if(rootf->m_lch == root)
  31. 				SetLChild(rootf, node);
  32. 			else
  33. 				SetRChild(rootf, node);
  34. 		}
  35. 		else
  36. 		{
  37. 			m_root = node;
  38. 			m_root->m_father = NULL;
  39. 		}
  40. 			
  41. 		SetRChild(root, node->m_lch);
  42. 		SetLChild(node, root);
  43. 	}
  44. 	//左右型树旋转
  45. 	void Rotate_LR(TreeNode<T>* root)
  46. 	{
  47. 		Rotate_RR(root->m_lch);
  48. 		Rotate_LL(root);
  49. 	}
  50. 	//右左型树旋转
  51. 	void Rotate_RL(TreeNode<T>* root)
  52. 	{
  53. 		Rotate_LL(root->m_rch);
  54. 		Rotate_RR(root);
  55. 	}

 4.旋转后BF值的更新

当时LL型或者RR型树，旋转平衡后，TT，L的BF都变为0。当LR型树，旋转平衡后，根据原树的Lr的BF值0，1，-1这3种情况，有三种结果。RL型树同理LR树。

 代码实现

  1. 	void LeftBalance(TreeNode<T>* TT)
  2. 	{
  3. 		assert(TT->m_bf == TreeLH);
  4. 		TreeNode<T>* L = TT->m_lch;
  5. 		if(L->m_bf == TreeLH) // LL型树，插在树root的左孩子的左边
  6. 		{
  7. 			TT->m_bf = TreeEH;
  8. 			L->m_bf = TreeEH;
  9. 			Rotate_LL(TT);
  10. 		}
  11. 		else if(L->m_bf == TreeRH) //LR型树，插在树root的左孩子的右边,双旋处理
  12. 		{
  13. 			TreeNode<T>* lr = L->m_rch;
  14. 			if(lr->m_bf == TreeLH)
  15. 			{
  16. 				TT->m_bf = TreeRH;
  17. 				L->m_bf = TreeEH;
  18. 			}
  19. 			else if(lr->m_bf == TreeEH)
  20. 			{
  21. 				TT->m_bf = TreeEH;
  22. 				L->m_bf = TreeEH;
  23. 			}
  24. 			else if(lr->m_bf == TreeRH)//
  25. 			{
  26. 				TT->m_bf = TreeEH;
  27. 				L->m_bf = TreeLH;
  28. 			}
  29. 			
  30. 			lr->m_bf = TreeEH;
  31. 			Rotate_LR(TT);
  32. 		}
  33. 		else
  34. 			assert(false);
  35. 		
  36. 	}

八.总结

学习二叉树前需要熟练掌握递归。平衡二叉树的删除，和插入旋转是难点。但是只要多画图，根据图写代码还是容易分析的。指针指来指去的可能会懵圈，多些assert，自检下。

附上所有源码

  1. #include "utility.h"
  2.  
  3. template <typename T>
  4. class TreeNode
  5. {
  6. public:
  7. 	T m_data = 0;  //可以存储自定义的数据结构的数据
  8. 	char m_bf = 0;  //平衡二叉树每个节点的平衡因子，只能为 -1，0，1.
  9. 	int m_depth = -1; //节点所在的深度
  10. 	TreeNode* m_lch = NULL;
  11. 	TreeNode* m_rch = NULL;
  12. 	TreeNode* m_father = NULL;
  13. };
  14.  
  15. template<typename T>
  16. using  dealTreeNode = void (*)(TreeNode<T>* node);
  17.  
  18. template <typename T>
  19. class Tree
  20. {
  21. public:
  22. 	~Tree()
  23. 	{
  24. 		PostOrderVisit(m_root,  [](TreeNode<T>* node){ //通过传人自定义遍历函数，释放所有节点。
  25. 			delete node;
  26. 		});
  27. 	}
  28. 	
  29. 	//获取树的深度
  30. 	int GetTreeDepth()
  31. 	{
  32. 		if(m_root == NULL)
  33. 			return 0;
  34. 		return GetDepth(m_root);
  35. 	}
  36. 	
  37. 	//删除节点，使用前驱节点替换方法
  38. 	//1.对于删除的节点，只有左孩子或右孩子时，很简单直接子承父业就行。
  39. 	//2.如果被删除的节点即有左孩子，又有右孩子，可以使用前驱节点替换方法，或者使用后驱节点替换方法。
  40. 	void DelTreeNode(TreeNode<T>* node)
  41. 	{
  42. 		if(node == NULL)
  43. 			return;
  44. 		
  45. 		if(node != m_root)
  46. 		{
  47. 			TreeNode<T>** pfatherchild;
  48. 			if(node->m_father->m_lch == node)
  49. 				pfatherchild = &node->m_father->m_lch;
  50. 			else
  51. 				pfatherchild = &node->m_father->m_rch;
  52. 			
  53. 			if(node->m_lch == NULL)//只有右支，子承父业
  54. 			{
  55. 				*pfatherchild = node->m_rch;
  56. 				if(node->m_rch)
  57. 					node->m_rch->m_father = node->m_father;
  58. 			}
  59. 			else if(node->m_rch == NULL)//只有左支，子承父业
  60. 			{
  61. 				*pfatherchild = node->m_lch;
  62. 				if(node->m_lch)
  63. 					node->m_lch->m_father = node->m_father;
  64. 				
  65. 			}
  66. 			else//即有左支，又有右支，使用中序遍历时的前驱节点替换
  67. 			{
  68. 				//第1步，找到删除节点的第一个左孩子的最右孩子，是中序遍历时node的前驱节点。
  69. 				TreeNode<T>* pre = node->m_lch;
  70. 				while (pre->m_rch)
  71. 					pre = pre->m_rch;
  72. 				
  73. 				//第2步，被删除节点的右支过继到pre的右孩子。
  74. 				SetRChild(pre, node->m_rch);
  75. 			
  76. 				if(pre == pre->m_father->m_rch)
  77. 				{
  78. 					//第3步，pre节点的左支过继给pre节点的父节点
  79. 					SetRChild(pre->m_father, pre->m_lch);
  80. 					//第4步，被删节点的第一个左节点，成为pre的左孩子
  81. 					SetLChild(pre, node->m_lch);
  82. 				}
  83. 				
  84. 				//第4步，node替换成pre节点
  85. 				{
  86. 					*pfatherchild = pre;
  87. 					pre->m_father = node->m_father;
  88. 				}
  89. 			}
  90. 			
  91. 		}
  92. 		else  //同样的方法对node==root时的特殊处理
  93. 		{
  94. 			TreeNode<T>* pre = m_root->m_lch; //找到删除节点的第一个左孩子
  95. 			if(pre)
  96. 			{
  97. 				while (pre->m_rch)
  98. 					pre = pre->m_rch;//第一个左孩子的最右孩子，就是中序遍历时node的前驱节点。
  99. 				
  100. 				if(pre == pre->m_father->m_rch)
  101. 				{
  102. 					SetRChild(pre->m_father, pre->m_lch);
  103. 					SetLChild(pre,  node->m_lch);
  104. 				}
  105. 				SetRChild(pre , node->m_rch);
  106.  
  107. 				m_root = pre;
  108. 				m_root->m_father = NULL;
  109. 			}
  110. 			else //删除的是根节点，且根节点没有左子树的情况
  111. 			{
  112. 				m_root = m_root->m_rch;
  113. 				if(m_root)
  114. 					m_root->m_father = NULL;
  115. 			}
  116. 		}
  117. 		
  118. 		delete node;
  119. 	}
  120. 	void InitTree(int* pArr, int n , int sort(const T, const T) = NULL)
  121. 	{
  122. 		for(int i = 0; i < n; i++)
  123. 		{
  124. 			TreeNode<T>* node = new TreeNode<T>();
  125. 			node->m_data = pArr[i];
  126. 			if(m_bavl)
  127. 				AVLAddChild(m_root, node, sort);
  128. 			else
  129. 				AddChild(m_root, node, sort);
  130. 				
  131. 		}
  132. 	}
  133. 	void InitAVLTree(int* pArr, int n, int sort(const T, const T) = NULL)
  134. 	{
  135. 		m_bavl = true;
  136. 		InitTree(pArr, n, sort);
  137. 	}
  138. 	
  139. 	TreeNode<T>* FindTreeNode(T data, int sort(T, T) = NULL)
  140. 	{
  141. 		return FindTreeNode(m_root, data, sort);
  142. 	}
  143. 	
  144. 	
  145. 	void PreOrderVisit(dealTreeNode<T> fun)
  146. 	{
  147. 		PreOrderVisit(m_root, fun);
  148. 	}
  149. 	void InOrderVisit(dealTreeNode<T> fun)
  150. 	{
  151. 		InOrderVisit(m_root, fun);
  152. 	}
  153. 	void PostOrderVisit(dealTreeNode<T> fun)
  154. 	{
  155. 		PostOrderVisit(m_root, fun);
  156. 	}
  157. 	
  158. private:
  159. 	
  160. 	int GetDepth(TreeNode<T>* node)
  161. 	{
  162. 		if(node == NULL)
  163. 			return 0;
  164. 		node->m_depth = max(GetDepth(node->m_lch), GetDepth(node->m_rch)) + 1;
  165. 		return node->m_depth;
  166. 	}
  167. 	
  168. 	TreeNode<T>* FindTreeNode(TreeNode<T>* node, T data, int sort(T, T)=NULL)
  169. 	{
  170. 		if(node == NULL)
  171. 			return NULL;
  172. 		else if(node->m_data == data)
  173. 			return node;
  174. 		
  175. 		int cmp = 0;
  176. 		if(sort!=NULL)
  177. 			cmp = sort(data, node->m_data);
  178. 		else
  179. 			cmp = data - node->m_data;
  180. 		
  181. 		if(m_ascendorder)
  182. 		{
  183. 			if(cmp >= 0)
  184. 				return FindTreeNode(node->m_rch, data);
  185. 			else
  186. 				return FindTreeNode(node->m_lch, data);
  187. 		}
  188. 		else
  189. 		{
  190. 			if(cmp >= 0)
  191. 				return FindTreeNode(node->m_lch, data);
  192. 			else
  193. 				return FindTreeNode(node->m_rch, data);
  194. 				
  195. 		}
  196. 		return NULL;
  197. 	}
  198.  
  199. 	
  200. 	void LeftBalance(TreeNode<T>* TT)
  201. 	{
  202. 		assert(TT->m_bf == TreeLH);
  203. 		TreeNode<T>* L = TT->m_lch;
  204. 		if(L->m_bf == TreeLH) // LL型树，插在树root的左孩子的左边
  205. 		{
  206. 			TT->m_bf = TreeEH;
  207. 			L->m_bf = TreeEH;
  208. 			Rotate_LL(TT);
  209. 		}
  210. 		else if(L->m_bf == TreeRH) //LR型树，插在树root的左孩子的右边,双旋处理
  211. 		{
  212. 			TreeNode<T>* lr = L->m_rch;
  213. 			if(lr->m_bf == TreeLH)
  214. 			{
  215. 				TT->m_bf = TreeRH;
  216. 				L->m_bf = TreeEH;
  217. 			}
  218. 			else if(lr->m_bf == TreeEH)
  219. 			{
  220. 				TT->m_bf = TreeEH;
  221. 				L->m_bf = TreeEH;
  222. 			}
  223. 			else if(lr->m_bf == TreeRH)//
  224. 			{
  225. 				TT->m_bf = TreeEH;
  226. 				L->m_bf = TreeLH;
  227. 			}
  228. 			
  229. 			lr->m_bf = TreeEH;
  230. 			Rotate_LR(TT);
  231. 		}
  232. 		else
  233. 			assert(false);
  234. 		
  235. 	}
  236. 	void RightBalance(TreeNode<T>* TT)
  237. 	{
  238. 		assert(TT->m_bf == TreeRH);
  239. 		TreeNode<T>* R = TT->m_rch;
  240. 		if(R->m_bf == TreeRH) //RR型树， 插在树root的右孩子的右边
  241. 		{
  242. 			TT->m_bf = TreeEH;
  243. 			R->m_bf = TreeEH;
  244. 			Rotate_RR(TT);
  245. 		}
  246. 		else if(R->m_bf == TreeLH)//RL型树，插在树root的右孩子的左边,双旋处理
  247. 		{
  248. 			TreeNode<T>* rl = R->m_lch;
  249. 			if(rl->m_bf == TreeLH)
  250. 			{
  251. 				TT->m_bf =TreeEH;
  252. 				R->m_bf = TreeRH;
  253. 				
  254. 			}
  255. 			else if(rl->m_bf == TreeEH)
  256. 			{
  257. 				TT->m_bf = TreeEH;
  258. 				R->m_bf = TreeEH;
  259. 			}
  260. 			else if(rl->m_bf == TreeRH)
  261. 			{
  262. 				TT->m_bf = TreeLH;
  263. 				R->m_bf = TreeEH;
  264. 			}
  265. 			
  266. 			rl->m_bf = TreeEH;
  267. 			Rotate_RL(TT);
  268. 		}
  269. 		else
  270. 			assert(false);
  271. 		
  272. 	}
  273. 	
  274. 	void AddChild(TreeNode<T>* TT, TreeNode<T>* node, int sort(T, T))
  275. 	{
  276. 		if(m_root == NULL)
  277. 		{
  278. 			m_root = node;
  279. 			return ;
  280. 		}
  281. 		
  282. 		int cmp = 0;
  283. 		if(sort)
  284. 			cmp = sort(node->m_data, TT->m_data);
  285. 		else
  286. 			cmp = node->m_data < TT->m_data;
  287. 		
  288. 		if((m_ascendorder && cmp > 0) || (!m_ascendorder && cmp < 0))
  289. 		{
  290. 			if(TT->m_lch == NULL)
  291. 			{
  292. 				SetLChild(TT, node);
  293. 				return;
  294. 			}
  295. 			else
  296. 			{
  297. 				AddChild(TT->m_lch, node, sort);
  298. 				return;
  299. 			}
  300. 		}
  301. 		else
  302. 		{
  303. 			if(TT->m_rch == NULL)
  304. 			{
  305. 				SetRChild(TT, node);
  306. 				return;
  307. 			}
  308. 			else
  309. 			{
  310. 				AddChild(TT->m_rch, node, sort);
  311. 				return;
  312. 			}
  313. 		}
  314. 		assert(false);
  315. 	}
  316. 	
  317. 	
  318. 	//返回值是，TT的深度增加值
  319. 	int AVLAddChild(TreeNode<T>* TT, TreeNode<T>* node, int sort(T, T))
  320. 	{
  321. 		if(m_root == NULL)
  322. 		{
  323. 			m_root = node;
  324. 			m_root->m_bf = TreeEH;
  325. 			return 1;
  326. 		}
  327. 		
  328. 		int cmp = 0;
  329. 		if(sort)
  330. 			cmp = sort(node->m_data, TT->m_data);
  331. 		else
  332. 			cmp = node->m_data < TT->m_data;
  333. 		
  334. 		if((m_ascendorder && cmp > 0) || (!m_ascendorder && cmp < 0))
  335. 		{
  336. 			if(TT->m_lch == NULL)
  337. 			{
  338. 				SetLChild(TT, node);
  339. 				node->m_bf = TreeEH;
  340. 				if(TT->m_rch == NULL)
  341. 				{
  342. 					assert(TT->m_bf == TreeEH);
  343. 					TT->m_bf = TreeLH;
  344. 					return 1;
  345. 				}
  346. 				else
  347. 				{
  348. 					assert(TT->m_bf == TreeRH);
  349. 					TT->m_bf = TreeEH;
  350. 					return 0;
  351. 				}
  352. 			}
  353. 			else
  354. 			{
  355. 				int ret = AVLAddChild(TT->m_lch, node, sort);
  356. 				if(ret) // 插入结果：TT的左树增加一层。
  357. 				{
  358. 					if(TT->m_bf == TreeLH)//TT本来就左树高，又在TT的左树增加1层。
  359. 					{
  360. 						LeftBalance(TT);
  361. 						return 0;
  362. 					}
  363. 					else if(TT->m_bf == TreeEH)
  364. 					{
  365. 						TT->m_bf = TreeLH;
  366. 						return 1;
  367. 					}
  368. 					else if(TT->m_bf == TreeRH)
  369. 					{
  370. 						TT->m_bf = TreeEH;
  371. 						return 0;
  372. 					}
  373. 				}
  374. 				else
  375. 					return ret; //equal return 0;
  376. 			}
  377. 		}
  378. 		else
  379. 		{
  380. 			if(TT->m_rch == NULL)
  381. 			{
  382. 				SetRChild(TT, node);
  383. 				node->m_bf = TreeEH;
  384. 				if(TT->m_lch == NULL)
  385. 				{
  386. 					assert(TT->m_bf == TreeEH);
  387. 					TT->m_bf = TreeRH;
  388. 					return 1;
  389. 				}
  390. 				else
  391. 				{
  392. 					assert(TT->m_bf==TreeLH);
  393. 					TT->m_bf = TreeEH;
  394. 					return 0;
  395. 				}
  396. 				
  397. 			}
  398. 			else
  399. 			{
  400. 				int ret = AVLAddChild(TT->m_rch, node, sort);
  401. 				if(ret)//插入结果：TT的右树增加一层。
  402. 				{
  403. 					if(TT->m_bf == TreeRH) //TT的右树高，又在右树上加一成
  404. 					{
  405. 						RightBalance(TT);
  406. 						return 0;
  407. 					}
  408. 					else if(TT->m_bf == TreeEH)
  409. 					{
  410. 						TT->m_bf = TreeRH;
  411. 						return 1;
  412. 					}
  413. 					else if(TT->m_bf == TreeLH)
  414. 					{
  415. 						TT->m_bf = TreeEH;
  416. 						return 0;
  417. 					}
  418. 				}
  419. 				else
  420. 					return ret;
  421. 			}
  422. 		}
  423.  
  424. 		assert(false);
  425. 	}
  426. 	
  427. 	//前序遍历，每个节点使用函数fun访问
  428. 	void PreOrderVisit(TreeNode<T>* node,  dealTreeNode<T> fun)
  429. 	{
  430. 		if(node == NULL)
  431. 			return;
  432. 		if(fun!=NULL)
  433. 			fun(node);
  434. 		PreOrderVisit(node->m_lch, fun);
  435. 		PreOrderVisit(node->m_rch, fun);
  436. 	}
  437. 	
  438. 	//中序遍历，每个节点使用函数fun访问
  439. 	void InOrderVisit(TreeNode<T>* node,  dealTreeNode<T> fun)
  440. 	{
  441. 		if(node == NULL)
  442. 			return;
  443. 		InOrderVisit(node->m_lch, fun);
  444. 		if(fun!=NULL)
  445. 			fun(node);
  446. 		
  447. #ifdef DEBUG //for check 
  448. 		{
  449. 			if(node->m_father!=NULL)
  450. 			{
  451. 				if(node!=m_root)
  452. 				{
  453. 					assert(node->m_father);
  454. 					assert(node->m_father != node);
  455. 					assert(node->m_lch!=node);
  456. 					assert(node->m_rch!=node);
  457. 					assert(node->m_father!=node->m_lch);
  458. 					assert(node->m_father!=node->m_rch);
  459. 				}
  460. 				else
  461. 				{
  462. 					assert(node->m_father == NULL);
  463. 					assert(node->m_lch!=node);
  464. 					assert(node->m_rch!=node);
  465. 				}
  466. 			
  467. 			}
  468. 			if(node->m_lch)
  469. 				assert(node->m_lch->m_father==node);
  470. 			if(node->m_rch)
  471. 				assert(node->m_rch->m_father==node);
  472. 		}
  473. #endif
  474. 		InOrderVisit(node->m_rch, fun);
  475. 	}
  476. 	
  477. 	//后序遍历，每个节点使用函数fun访问
  478. 	void PostOrderVisit(TreeNode<T>* node,  dealTreeNode<T> fun)
  479. 	{
  480. 		if(node == NULL)
  481. 			return;
  482. 		PostOrderVisit(node->m_lch, fun);
  483. 		PostOrderVisit(node->m_rch, fun);
  484. 		if(fun!=NULL)
  485. 			fun(node);
  486. 	}
  487. 	
  488. 	//把L设置成node的左孩子
  489. 	void SetLChild(TreeNode<T>* node, TreeNode<T>* L)
  490. 	{
  491. 		if(node == NULL)
  492. 			return;
  493. 		node->m_lch = L;
  494. 		if(L)
  495. 			L->m_father = node;
  496. 	}
  497. 	
  498. 	//把R设置成node的右孩子
  499. 	void SetRChild(TreeNode<T>* node, TreeNode<T>* R)
  500. 	{
  501. 		if(node == NULL)
  502. 			return;
  503. 		node->m_rch = R;
  504. 		if(R)
  505. 			R->m_father = node;
  506. 	}
  507. 	//左左型树旋转,往右旋转
  508. 	void Rotate_LL(TreeNode<T>* root)
  509. 	{
  510. 		TreeNode<T>* rootf = root->m_father;
  511. 		TreeNode<T>* node = root->m_lch;
  512. 		if(rootf)
  513. 		{
  514. 			if(rootf->m_lch == root)
  515. 				SetLChild(rootf, node);
  516. 			else
  517. 				SetRChild(rootf, node);
  518. 		}
  519. 		else
  520. 		{
  521. 			m_root = node;
  522. 			m_root->m_father = NULL;
  523. 		}
  524. 		
  525. 		SetLChild(root, node->m_rch);
  526. 		SetRChild(node, root);
  527. 	}
  528. 	//右右型树旋转，往左旋转
  529. 	void Rotate_RR(TreeNode<T>* root)
  530. 	{
  531. 		
  532. 		TreeNode<T>* rootf = root->m_father;
  533. 		TreeNode<T>* node = root->m_rch;
  534. 		if(rootf)
  535. 		{
  536. 			if(rootf->m_lch == root)
  537. 				SetLChild(rootf, node);
  538. 			else
  539. 				SetRChild(rootf, node);
  540. 		}
  541. 		else
  542. 		{
  543. 			m_root = node;
  544. 			m_root->m_father = NULL;
  545. 		}
  546. 			
  547. 		SetRChild(root, node->m_lch);
  548. 		SetLChild(node, root);
  549. 	}
  550. 	//左右型树旋转
  551. 	void Rotate_LR(TreeNode<T>* root)
  552. 	{
  553. 		Rotate_RR(root->m_lch);
  554. 		Rotate_LL(root);
  555. 	}
  556. 	//右左型树旋转
  557. 	void Rotate_RL(TreeNode<T>* root)
  558. 	{
  559. 		Rotate_LL(root->m_rch);
  560. 		Rotate_RR(root);
  561. 	}
  562. 	
  563. 	TreeNode<T>* m_root = NULL;
  564. 	bool m_ascendorder = true; //是否升序排序
  565. 	bool m_bavl = false; //是否是平衡二叉树
  566. 	const static int TreeLH = 1;//左子树比右子树深度大1.
  567. 	const static int TreeEH = 0;//左子树和右子树深度一样.
  568. 	const static int TreeRH = -1;//右子树和子子树深度一样.
  569. };
  570.  
  571.  
  572.  
  573. int main()
  574. {	
  575. 	vector<int > v;
  576. 	int arr[] = {62,188,58,47,0,2,35,432,431,430,444,455,73,6,7,51,-10,1,99,37,828,88,93};
  577. 	static int allsum = 0;
  578. 	for(int i = 0 ; i < arraysize(arr); ++i)
  579. 	{
  580. 		Tree<double> tree;
  581. 		tree.InitTree(arr, arraysize(arr));
  582. 		tree.DelTreeNode(tree.FindTreeNode(arr[i]));
  583. 		tree.InOrderVisit([](TreeNode<double>* node){
  584. 			cout << node->m_data << " ";
  585. 			allsum += node->m_data;
  586. 		});
  587. 		cout << endl;
  588. 	}
  589. 	
  590. 	int sum = 0;
  591. 	for(int i = 0; i <arraysize(arr); ++i)
  592. 		sum+=arr[i];
  593. 	
  594. 	assert(allsum/sum == arraysize(arr) -1);
  595. 	
  596. 	cout << endl << endl;
  597. 	int avltreedepth = 0;
  598. 	for(int i = 0 ; i < arraysize(arr); ++i)
  599. 	{
  600. 		Tree<double> tree;
  601. 		tree.InitAVLTree(arr, arraysize(arr));
  602. 		tree.DelTreeNode(tree.FindTreeNode(arr[i]));
  603. 		tree.InOrderVisit([](TreeNode<double>* node){
  604. 			cout << node->m_data << " ";
  605. 			allsum += node->m_data;
  606. 		});
  607. 		cout << endl;
  608. 	}
  609.  
  610. 	cout << endl;
  611. 	int arr1[] = {1,2,3,4,5,6,7,8};
  612. 	Tree<double> tree;
  613. 	tree.InitTree(arr1, arraysize(arr1));
  614. 	Tree<double> tree1;
  615. 	tree1.InitAVLTree(arr1, arraysize(arr1));
  616. 	cout << "tree depth:" << tree.GetTreeDepth() << " AVLtree depth:" << tree1.GetTreeDepth() << endl;
  617. 	return 0;
  618. }
  619.  
  620.

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

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

  

闽ICP备14008679号