devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java实现平衡二叉树_java 手写平衡二叉树

作者：我家小花儿 | 2024-07-20 19:49:14

赞

踩

java 手写平衡二叉树

创建平衡二叉树，主要是一旦出现不平衡状态如何更改，这个一直是一个比较晕的，什么左旋右旋很乱。下面跟大家说下如何比较好理解的来进行平衡，阅读本文前需要先明白，不平衡的四种情况即，左左，左右，右左，右右四种情况，如果不懂的，可以自己百度，关于这个很多理解。本文主要是针对对于左旋和右旋理解不了或者想学习用java编写的代码。

其实不管怎么转，其实只是重新改变不平衡节点的左右子树，因此，我们只需要记住不平衡节点的左右子树的左右子树分别该如何得到，就可以。

1、左左情况。

因为左边的过长，所以要吧左边的过长的部分从中间折断，这样就可以把3层节点来弄成两层，这样就可以平衡。

（图片来自网络，侵删）

因此可以看出，新的左子树的左子树为原不平衡节点K2的左子树的左子树的左子树。新的右子树的左子树为不平衡点的左子树的右子树，新右子树的右子树为不平衡点的右子树，右子树的节点为不平衡节点的值，不平衡点值为原不平衡点左子树的值。

代码化为：

  1. BalancedBinaryNode newleftnode=balancedBinaryNode.left.left;
  2. 		BalancedBinaryNode newrightnode=new BalancedBinaryNode();
  3. 		newrightnode.left=balancedBinaryNode.left.right;
  4. 		newrightnode.right=balancedBinaryNode.right;
  5. 		newrightnode.data=balancedBinaryNode.data;
  6. 		balancedBinaryNode.data=balancedBinaryNode.left.data;
  7. 		balancedBinaryNode.left=newleftnode;
  8. 		balancedBinaryNode.right=newrightnode;

分析：因为左边过长，所以要折半，即把不平衡点左子树的值作为这部分树的根，那么，根的左子树，也就是新的左子树，所有值都比根要小，而新的右子树要比根大。所以，比根小的 只有根的左子树比他小，所以：新的左子树就是新根原来的左子树：即BalancedBinaryNode newleftnode=balancedBinaryNode.left.left;。剩下的三部分很好理解，新根原来的右子树、原根的右子树、原根的大小关系，很明显：新根原来的右子树<原根<原根的右子树，所以将原根作为新根的右子树，也就是新的右子树，将新根的右子树作为新右子树的左子树，将原根的右子树作为新子树的右子树，

2、右右情况

与左左情况原理相同，只需要左换右即可

3、左右

先附上旋转图（来自网络，侵删）

说实话，这个做法很完美，但是，理解起来有点困难，尤其是没空间想象能力较差。那我们现在来看一看能不能从结果找到什么。

首先，既然是左右了，那么一定是存在 不平衡点、不平衡点左孩子、不平衡点左孩子的有孩子  （原因是左右就是左子树的右子树插入孩子），很显然大小关系：不平衡点左孩子<不平衡点左孩子的右孩子<不平衡点，所以平衡成一颗新树就是  新根节点一定是不平衡节点的左孩子的右孩子，那么新左子树是不平衡点的左孩子，新右子树是不平衡点   ok，来看左右子节点的左右子树分别是啥，先看新左子树的左子树，比新左子树小的 只有原来树中比它小的，那就是原树种不平衡点左子树（新左子树）的左子树，同理，新右子树的右子树就是原不平衡点（新右子树）的右子树。现在还剩下不平衡点的左子树的右子树（新根节点）的左右子树，先看左子树，小于新根节点，所以只能是位于新左子树的一部分，但是，它由于属于新左子树原来右子树的一部分，所以大于新左子树，所以为左子树的右子树，同理，新根节点的原右子树就是右子树的左子树。

所以结论就是：

根节点的值是：不平衡点的左子树的右子树的值

根的左子树节点是：不平衡点的左子树的值

根的右子树节点是：不平衡点的值

新左子树的左子树是：不平衡点的左子树的左子树

新左子树的右子树是：不平衡点左子树的右子树的左子树

新右子树的左子树是：不平衡点左子树的右子树的右子树

新右子树的右子树是：不平衡点的右子树

  1. BalancedBinaryNode newleftnode=new BalancedBinaryNode();
  2. 		BalancedBinaryNode newrightnode=new BalancedBinaryNode();
  3. 		newleftnode.data=balancedBinaryNode.left.data;
  4. 		newleftnode.left=balancedBinaryNode.left.left;
  5. 		newleftnode.right=balancedBinaryNode.left.right.left;
  6. 		newrightnode.data=balancedBinaryNode.data;
  7. 		newrightnode.left=balancedBinaryNode.left.right.right;
  8. 		newrightnode.right=balancedBinaryNode.right;
  9. 		balancedBinaryNode.data=balancedBinaryNode.left.right.data;
  10. 		balancedBinaryNode.left=newleftnode;
  11. 		balancedBinaryNode.right=newrightnode;

4、右左理解方式一样

5、下面放入整体代码：

  1. package DataStruct;
  2.  
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5.  
  6.  
  7. public class BalancedBinaryTree {
  8. 	public static class BalancedBinaryNode{
  9. 		public int data;
  10. 		public BalancedBinaryNode left;
  11. 		public BalancedBinaryNode right;
  12. 		public int ceng ;
  13. 		public int du;
  14. 	}
  15. 	public static BalancedBinaryNode init(int data){
  16. 		BalancedBinaryNode root=new BalancedBinaryNode();
  17. 		root.data=data;
  18. 		root.left=null;
  19. 		root.right=null;
  20. 		root.du=0;
  21. 		return root;
  22. 	}
  23. 	public static void add(BalancedBinaryNode root,int data){
  24. 		BalancedBinaryNode temp=root;
  25. 		BalancedBinaryNode newNode=new BalancedBinaryNode();
  26. 		newNode.left=null;newNode.right=null;newNode.data=data;
  27. 		while(true){
  28. 			if(data<temp.data){
  29. 				if(temp.left!=null){
  30. 					temp=temp.left;
  31. 				}else{
  32. 					temp.left=newNode;
  33. 					return ;
  34. 				}
  35. 			}else if(data>temp.data){
  36. 				if(temp.right!=null){
  37. 					temp=temp.right;
  38. 				}else{
  39. 					temp.right=newNode;
  40. 					return ;
  41. 				}
  42. 			}else{
  43. 				return;
  44. 			}
  45. 		}
  46. 		
  47. 	}
  48. 	public static void balance(BalancedBinaryNode root,int data){
  49. 		Queue<BalancedBinaryNode> queue=new LinkedList<>();
  50. 		if(root==null){
  51. 			return ;
  52. 		}
  53. 		queue.add(root);
  54. 		root.ceng=1;
  55. 		BalancedBinaryNode balancedBinaryNode;
  56. 		while(queue.size()!=0){
  57. 			balancedBinaryNode=queue.poll();
  58. 			int leftheaght=balancedBinaryNode.left==null?0:getDu(balancedBinaryNode.left);
  59. 			int rightheaght=balancedBinaryNode.right==null?0:getDu(balancedBinaryNode.right);
  60. 			//该节点平衡
  61. 			if(Math.abs(leftheaght-rightheaght)<2){
  62. 				if(balancedBinaryNode.left!=null){
  63. 					queue.add(balancedBinaryNode.left);
  64. 				}
  65. 				if(balancedBinaryNode.right!=null){
  66. 					queue.add(balancedBinaryNode.right);
  67. 				}
  68. 			}
  69. 			//否则不平衡
  70. 			else{
  71. 				
  72. 				if(leftheaght>rightheaght){
  73. 					if(data<balancedBinaryNode.left.data){
  74. 						leftAndLeft(balancedBinaryNode);
  75. 					}else{
  76. 						leftandright(balancedBinaryNode);
  77. 					}
  78. 				}else{
  79. 					if(data<balancedBinaryNode.right.data){
  80. 						System.out.println("右左");
  81. 						rightandleft(balancedBinaryNode);
  82. 					}else{
  83. 						rightandright(balancedBinaryNode);
  84. 					}
  85. 				}
  86. 			}
  87. 		}
  88. 	}
  89. 	//左左的平衡
  90. 	public static void leftAndLeft(BalancedBinaryNode balancedBinaryNode){
  91. 		BalancedBinaryNode newleftnode=balancedBinaryNode.left.left;
  92. 		BalancedBinaryNode newrightnode=new BalancedBinaryNode();
  93. 		newrightnode.left=balancedBinaryNode.left.right;
  94. 		newrightnode.right=balancedBinaryNode.right;
  95. 		newrightnode.data=balancedBinaryNode.data;
  96. 		balancedBinaryNode.data=balancedBinaryNode.left.data;
  97. 		balancedBinaryNode.left=newleftnode;
  98. 		balancedBinaryNode.right=newrightnode;
  99. 	}
  100. 	//右右的平衡
  101. 	public static void rightandright(BalancedBinaryNode balancedBinaryNode){
  102. 		BalancedBinaryNode newleftnnode=new BalancedBinaryNode();
  103. 		BalancedBinaryNode newrightnode=balancedBinaryNode.right.right;
  104. 		newleftnnode.left=balancedBinaryNode.left;
  105. 		newleftnnode.right=balancedBinaryNode.right.left;
  106. 		newleftnnode.data=balancedBinaryNode.data;
  107. 		balancedBinaryNode.data=balancedBinaryNode.right.data;
  108. 		balancedBinaryNode.left=newleftnnode;
  109. 		balancedBinaryNode.right=newrightnode;
  110. 	}
  111. 	//左右的平衡
  112. 	public static void leftandright(BalancedBinaryNode balancedBinaryNode){
  113. 		BalancedBinaryNode newleftnode=new BalancedBinaryNode();
  114. 		BalancedBinaryNode newrightnode=new BalancedBinaryNode();
  115. 		newleftnode.data=balancedBinaryNode.left.data;
  116. 		newleftnode.left=balancedBinaryNode.left.left;
  117. 		newleftnode.right=balancedBinaryNode.left.right.left;
  118. 		newrightnode.data=balancedBinaryNode.data;
  119. 		newrightnode.left=balancedBinaryNode.left.right.right;
  120. 		newrightnode.right=balancedBinaryNode.right;
  121. 		balancedBinaryNode.data=balancedBinaryNode.left.right.data;
  122. 		balancedBinaryNode.left=newleftnode;
  123. 		balancedBinaryNode.right=newrightnode;
  124. 	}
  125. 	//右左的旋转
  126. 	public static void rightandleft(BalancedBinaryNode balancedBinaryNode){
  127. 		BalancedBinaryNode newleftnode=new BalancedBinaryNode();
  128. 		BalancedBinaryNode newrightnode=new BalancedBinaryNode();
  129. 		newleftnode.data=balancedBinaryNode.data;
  130. 		newleftnode.left=balancedBinaryNode.left;
  131. 		newleftnode.right=balancedBinaryNode.right.left.left;
  132. 		newrightnode.data=balancedBinaryNode.right.data;
  133. 		newrightnode.left=balancedBinaryNode.right.left.right;
  134. 		newrightnode.right=balancedBinaryNode.right.right;
  135. 		balancedBinaryNode.data=balancedBinaryNode.right.left.data;
  136. 		balancedBinaryNode.left=newleftnode;
  137. 		balancedBinaryNode.right=newrightnode;
  138. 		
  139. 		
  140. 	}
  141. 	//获得某个节点的度
  142. 	public static int getDu(BalancedBinaryNode binaryNode){
  143. 		int result=0;
  144. 		if(binaryNode.left==null && binaryNode.right==null){
  145. 			result=1;
  146. 		}else if(binaryNode.left==null){
  147. 			result=1+getDu(binaryNode.right);
  148.  
  149. 		}else if(binaryNode.right==null){
  150. 			result=1+getDu(binaryNode.left);
  151. 		}else{
  152. 			result=1+Math.max(getDu(binaryNode.left),getDu(binaryNode.right));
  153.  
  154. 		}
  155. 		return result;
  156. 	}
  157. 	//
  158. 	public static void show(BalancedBinaryNode root){
  159. 		Queue<BalancedBinaryNode> queue=new LinkedList<>();
  160. 		if(root==null){
  161. 			System.out.println("空的");
  162. 			return ;
  163. 		}
  164. 		queue.add(root);
  165. 		root.ceng=1;
  166. 		BalancedBinaryNode balancedBinaryNode;
  167. 		while(queue.size()!=0){
  168. 			balancedBinaryNode=queue.poll();
  169. 			if(balancedBinaryNode.left!=null){
  170. 				balancedBinaryNode.left.ceng=balancedBinaryNode.ceng+1;
  171. 				queue.add(balancedBinaryNode.left);
  172. 			}
  173. 			if(balancedBinaryNode.right!=null){
  174. 				balancedBinaryNode.right.ceng=balancedBinaryNode.ceng+1;
  175. 				queue.add(balancedBinaryNode.right);
  176. 			}
  177. 			System.out.println("数据为："+balancedBinaryNode.data+" 所在层数 "+balancedBinaryNode.ceng);
  178. 		}
  179. 		
  180. 	}
  181.  
  182. }

 

6、测试代码和结果

  1. 	package TestMain;
  2.  
  3. import DataStruct.BalancedBinaryTree;
  4. import DataStruct.BalancedBinaryTree.BalancedBinaryNode;
  5.  
  6. public class Main {
  7. 		public static void main(String args[]) {
  8. //			int data[]={62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
  9. 			int data[]={1,2,3,4,5,6,7,8};
  10. 			BalancedBinaryNode root=BalancedBinaryTree.init(data[0]);
  11. 			for(int i=1;i<data.length;i++){
  12. 				BalancedBinaryTree.add(root, data[i]);
  13. 				BalancedBinaryTree.balance(root,data[i]);
  14. 			}
  15. 			BalancedBinaryTree.show(root);
  16. 		}
  17. 	}
  18.

数据为：5 所在层数 1
数据为：3 所在层数 2
数据为：6 所在层数 2
数据为：2 所在层数 3
数据为：4 所在层数 3
数据为：7 所在层数 3
数据为：1 所在层数 4
数据为：8 所在层数 4
 

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

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

  

闽ICP备14008679号