这篇文章主要讲解了“如何使用Java的平衡二叉树”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“如何使用Java的平衡二叉树”吧！
给定一个数列{1,2,3,4,5,6}，要求创建一个二叉排序树(BST)，分析问题所在
问题分析：
鸿蒙官方战略合作共建——HarmonyOS技术社区
左子树全部为空，从形式上看，更像一个单链表;
插入速度没有影响;
查询速度明显降低(因为需要一次比较)，不能发挥BST的优势。因为每次还要比较左子树，其查询速度，比单链表还慢。
解决方案-平衡二叉树(ALV)
鸿蒙官方战略合作共建——HarmonyOS技术社区
平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)，又称为AVL树，可以保证查询效率较高。
具有以下特点：它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用实现方法有 红黑树、AVL、替罪羊树、Treap、伸展树等;
举例说明，下图前两个都是平衡二叉树，第一个左右子树的高度差绝对值是1，第二个左右子树高度差的绝对值是0，而第三个的左右子树高度差的绝对值是2，这样第三个就不是平衡二叉树;
步骤：
鸿蒙官方战略合作共建——HarmonyOS技术社区
创建一个新的节点newNode，值等于当前根节点的值。
把新节点的左子树设置成当前节点的左子树。
把新节点的右子树设置成当前节点的右子树的左子树。
把当前节点的值换为当前右子节点的值。
把当前节点的右子树设置成右子树的右子树。
把当前节点的左子树设置为新的节点。
步骤：
鸿蒙官方战略合作共建——HarmonyOS技术社区
创建一个新的节点，值等于当前根的节点的值。
把新节点的右子树设置成当前节点的右子树。
把新节点的左子树设置成当前节点的左子树的右子树。
把当前节点的值换位左子节点的值。
把当前节点的左子树设置成左子树的左子树。
把当前节点的右子树设置为新的节点。
在某些情况下，单旋转不能完成完成平衡二叉树的转换，需要进行两次旋转。
鸿蒙官方战略合作共建——HarmonyOS技术社区
如果它的右子树的左子树的高度大于它的右子树的右子树的高度，需要先对右子树进行右旋转，再对当前节点进行左旋转。
如果它的左子树的右子树高度大于它的左子树的左子树高度，
需要对左子树先进行左旋转,再对当前节点进行右旋转。
package com.xie.avl; public class AVLTreeDemo { public static void main(String[] args) { int[] arr = {4, 3, 6, 5, 7, 8}; AVLTree avlTree = new AVLTree(); for (int i = 0; i < arr.length; i++) { avlTree.add(new Node(arr[i])); } System.out.println("中序遍历"); avlTree.infixOrder(); System.out.println("在没有平衡处理前~~"); System.out.println("树的高度=" + avlTree.getRoot().height()); System.out.println("树的左子树的高度=" + avlTree.getRoot().leftHeight()); System.out.println("树的右子树的高度=" + avlTree.getRoot().rightHeight()); } } class AVLTree { private Node root; public Node getRoot() { return root; } public void setRoot(Node root) { this.root = root; } //查找要删除的节点的父节点 public Node searchParent(Node node) { if (root != null) { return root.searchParent(node); } else { return null; } } //查找要删除的节点 public Node search(int value) { if (root == null) { return null; } else { return root.search(value); } } /** * 找到以node 根的二叉排序树的最小值，并删除以node 为根节点的二叉排序树的最小节点 * * @param node 传入节点（当做二叉排序树的根节点) * @return 返回以node为根节点的二叉排序树的最小节点值 */ public int delRightTreeMin(Node node) { Node target = node; //循环查找左节点 while (target.left != null) { target = target.left; } //删除最小节点 delNode(target.value); return target.value; } /** * 找到以node 根的二叉排序树的最大值，并删除以node 为根节点的二叉排序树的最大节点 * * @param node 传入节点（当做二叉排序树的根节点) * @return 返回以node为根节点的二叉排序树的最大节点值 */ public int delLeftTreeMax(Node node) { Node target = node; while (target.right != null) { target = target.right; } //删除最大节点 delNode(target.value); return target.value; } //删除节点 public void delNode(int value) { if (root == null) { return; } else { Node targetNode = search(value); if (targetNode == null) { return; } if (targetNode == root) { root = null; return; } Node parentNode = searchParent(targetNode); if (targetNode.left == null && targetNode.right == null) { //如果要删除的节点是叶子节点 if (parentNode.left != null && parentNode.left.value == targetNode.value) { parentNode.left = null; } if (parentNode.right != null && parentNode.right.value == targetNode.value) { parentNode.right = null; } } else if (targetNode.left != null && targetNode.right != null) { //如果要删除的节点是有两个子树的节点 int minValue = delRightTreeMin(targetNode.right); targetNode.value = minValue; //上下代码删除效果一样 //int maxValue = delLeftTreeMax(targetNode.left); //targetNode.value = maxValue; } else { //要删除的节点是只有左子节点 if (targetNode.left != null) { if (parentNode != null) { if (parentNode.left == targetNode) { parentNode.left = targetNode.left; } else { parentNode.right = targetNode.left; } } else { //如果父节点是空，让root换位 root = targetNode.left; } } else {//要删除的节点是只有右子节点 if (parentNode != null) { if (parentNode.left == targetNode) { parentNode.left = targetNode.right; } else { parentNode.right = targetNode.right; } } else { //如果父节点是空，让root换位 root = targetNode.right; } } } } } //添加节点 public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } //中序遍历 public void infixOrder() { if (root != null) { root.infixOrder(); } else { System.out.println("二叉排序为空，不能遍历"); } } } class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } /** * 返回左子树的高度 * * @return */ public int leftHeight() { if (left == null) { return 0; } return left.height(); } /** * 返回右子树的高度 * * @return */ public int rightHeight() { if (this.right == null) { return 0; } return right.height(); } /** * 返回以该节点为根节点的树的高度 * * @return */ public int height() { return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1; } /** * 左旋转 */ public void leftRotate() { //创建新的节点，以当前根节点的值 Node newNode = new Node(value); //把新的节点的左子树设置为当前节点的左子树 newNode.left = left; //把新的右子树设置为当前节点的右子树的左子树 newNode.right = right.left; //把当前节点的值替换成右子节点的值 value = right.value; //把当前节点的右子树设置成当前节点的右子节点的右子树 right = right.right; //把当前的节点的左子节点(左子树),设置成新的节点 left = newNode; } /** * 右旋转 */ public void rightRotate() { //创建新的节点，以当前根节点的值 Node newNode = new Node(value); //把新的节点的右子树设置成当前节点的右子树 newNode.right = right; //把新的节点的左子树设置为当前节点左子树的右子树 newNode.left = left.right; //把当前节点的值换为左子节点的值 value = left.value; //把当前节点左子树设置成左子树的左子树 left = left.left; //把当前节点的右子树设置新节点 right = newNode; } /** * 查找要删除节点的父节点 * * @param node 要删除的节点 * @return 要删除节点的父节点 */ public Node searchParent(Node node) { //如果当前节点就是要删除节点的父节点就返回 if ((this.left != null && this.left.value == node.value) || (this.right != null && this.right.value == node.value)) { return this; } else { if (this.left != null && node.value < this.value) { //如果查找的节点的值小于当前节点的值，向左子树递归查找 return this.left.searchParent(node); } else if (this.right != null && value >= this.value) { //如果查找的节点的值小于当前节点的值，向左子树递归查找 return this.right.searchParent(node); } else { return null; } } } /** * 查找要删除的节点 * * @param value 要删除的节点的值 * @return 删除的节点 */ public Node search(int value) { if (value == this.value) { return this; } else if (value < this.value) { if (this.left != null) { return this.left.search(value); } else { return null; } } else { if (this.right != null) { return this.right.search(value); } else { return null; } } } //递归的形式添加节点，满足二叉排序树的要求 public void add(Node node) { if (node == null) { return; } if (node.value < this.value) { if (this.left == null) { this.left = node; } else { //递归向左子树添加 this.left.add(node); } } else { if (this.right == null) { this.right = node; } else { //递归向右子节点添加 this.right.add(node); } } //当添加完一个节点后，如果（右子树高度-左子树高度）> 1 ，进行左旋转 if (rightHeight() - leftHeight() > 1) { //如果它的右子树的左子树的高度大于它的右子树的右子树的高度，需要先对右子树进行右旋转，再对当前节点进行左旋转 if(right != null && right.leftHeight()>right.rightHeight()){ right.rightRotate(); leftRotate(); }else{ //直接进行左旋转即可 leftRotate(); } return; } //当添加完一个节点后，如果（左子树高度-右子树高度）> 1 ，进行右旋转 if (leftHeight() - rightHeight() > 1) { //如果它的左子树的右子树高度大于它的左子树的左子树高度，需要对左子树先进行左旋转,再对当前节点进行右旋转 if(left != null && left.rightHeight() > left.leftHeight()){ left.leftRotate(); rightRotate(); }else{ //直接进行右旋转即可 rightRotate(); } } } //中序遍历 public void infixOrder() { if (this.left != null) { this.left.infixOrder(); } System.out.println(this); if (this.right != null) { this.right.infixOrder(); } } @Override public String toString() { return "Node{" + "value=" + value + '}'; } }感谢各位的阅读，以上就是“如何使用Java的平衡二叉树”的内容了，经过本文的学习后，相信大家对如何使用Java的平衡二叉树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
