#|数据结构——平衡二叉树（Java代码实现）数据结构|Java|平衡二叉树|左右

当对一个数组[1,2,3,4,5,6,]创建排序二叉树的时候看起来更像是一个链表，这个时候就需要使用到平衡二叉树。
基本介绍

平衡二叉树也叫平衡二叉搜索树(Self-balancing binarysearchtree)又被称为AVL树，可以保证查询效率较高。
具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

二叉排序树和平衡二叉树的转化
进行左旋转.

创建一个新的节点newNode (以4这个值创建)，创建一个新的节点，值等于当前根节点的值，把新节点的左子树设置成当前节点的左子树：newNode.left = left
把新节点的右子树设置为当前节点的右子树的左子树：newNode.right =right，
把当前节点的值换为右子节点的值：value=https://www.it610.com/article/right.value;
把当前节点的右子树设置成右子树的右子树：right=right.right ，
把当前节点的左子树设置为新节点：left=newNode;

文章图片

在节点类当中添加方法。在上一篇文章：数据结构——二叉排序树（Java代码实现）

// 返回左子树的高度 public int leftHight() { if (left == null) { return 0; } return left.hight(); } // 返回右子树的高度 public int rightHight() { if (right == null) { return 0; } return right.hight(); } // 返回当前节点的高度,以该节点为根节点的这棵树的高度 public int hight() { return Math.max(left == null ? 0 : left.hight(), right == null ? 0 : right.hight()) + 1; } // 左旋转 public void leftRotate() { // 创建新节点,用当前的根节点 Node newnode = new Node(value); // 把新节点的左子树设置成当前节点的左子树 newnode.left = left; // 把新节点的右子树设置为当前节点的右子树的左子树 newnode.right = right.left; // 把当前节点的值换为右子节点的值 value = https://www.it610.com/article/right.value; // 把当前节点的右子树设置成右子树的右子树： right = right.right; // 把当前节点的左子树设置为新节点 left = newnode; }

以及在进行add添加节点的时候加上判断语句，表示判断是否进行左旋转

// 添加完一个节点之后,右子树的高度减左子树的高度大于一 if (rightHight() - leftHight() > 1) { leftRotate(); }

最后进行测试：

public static void main(String[] args) { int [] arr= {4,3,6,5,7,8}; AVL avl = new AVL(); // 添加节点 for (int i = 0; i < arr.length; i++) { avl.add(new Node(arr[i])); } // 前序遍历 avl.DLR(); System.out.println("处理之后："); System.out.println("树高 = " + avl.getRoot().hight()); // 4 // 4 System.out.println("左子树高 = " + avl.getRoot().leftHight()); // 1 //3 System.out.println("右子树高 = " + avl.getRoot().rightHight()); // 3 //1 System.out.println("根节点 =" + avl.getRoot()); // 4 //6 }

【#|数据结构——平衡二叉树（Java代码实现）】查看结果：

文章图片

进行右旋转.
进行右选择，当一棵树的左子树的高度 - 右子树的高度大于一的时候进行右旋转，原理与左旋转相同，
在Node节点类当中新加一个右旋转的方法：

// 右旋转 public void rightRotate() { // 创建新节点,用当前的根节点 Node newnode = new Node(value); // 把新节点的右子树设置成当前节点的右子树 newnode.right = right; newnode.left = left.right; value = https://www.it610.com/article/left.value; left = left.left; right = newnode; }

在add添加节点方法当中添加判断是否进行右旋转：

if (leftHight() - rightHight() > 1) { rightRotate(); }

使用一个新的数组进行测试：

文章图片

进行双旋转.

当符号右旋转的条件时
如果它的左子树的右子树高度大于它的左子树的高度
先对当前这个结点的左节点进行左旋转
再对当前结点进行右旋转的操作即可

文章图片

修改代码：

if (rightHight() - leftHight() > 1) { if (right != null && right.rightHight() < right.leftHight()) { right.rightRotate(); } leftRotate(); return ; } if (leftHight() - rightHight() > 1) { // 先左旋转，再右旋转 if (left != null && left.rightHight() > left.leftHight()) { left.leftRotate(); } rightRotate(); }

测试数组