从二叉排序树(BST)我们知道，如图：

图片.png

或一个数组 int[] arr = {1,2,3,4,5,6}创建成二叉排序树后

图片.png

由于树的层数较多（可能会成为一个单链表 如上图），遍历起来会比较慢（如果数据很多的话），所以我们就改进此排序树。

左旋转：如果右边层数-左边层数的值大于1，则需要左旋转。（右边为4，左边为2，相差为2>1）

右旋转：如果左边层数-右边层数的值大于1，则需要右旋转。

以此排序二叉树为例子：
1.创建一个节点，节点的权 等于 根节点的 权（权就是节点的值，此时根节点为4）
2.让新节点的左指针指向根节点的左指针（newCode.left = root.left 指向3）
3.让新节点的右指针指向根节点的右子树的左子树（newCode.right = root.right.left 指向5）
4.根节点的右子树的权赋值给根节点（root.value = root.right.value 就是把6这个值赋给根节点）
5.让根节点的右子树指向根节点右子树的右子树（root.right = root.right.right 把根节点的右子树直接指向7）
6.让根节点的左子树指向新节点(root.left = newCode) 最后结果如下图所示

图片.png

由于没有任何节点指向6 所以被回收掉了，此时2边子树的高度是一样的。当然右旋转也同理，大家可以按照我的步骤画个图就知道了。代码如下：

public class BinarySortTreeDemo {

    public static void main(String[] args) {
        int[] arr = {4,3,6,5,7,8};
        //int[] arr = {10,12,8,9,7,6};
        //int[] arr = {8,7,5,6,3,4};
        BinarySortTree binarySortTree = new BinarySortTree();
        for(int i=0;i<arr.length;i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        binarySortTree.infixOrder();
        System.out.println("树的总高度:"+binarySortTree.getTreeHeight());
        System.out.println("树的左高度:"+binarySortTree.getLeftHeight());
        System.out.println("树的右高度:"+binarySortTree.getRightHeight());
    }
}

class BinarySortTree{
    private Node root;
    
    public int getLeftHeight() {
        return root.getLeftHeight();
    }
    
    public int getRightHeight() {
        return root.getRightHeight();
    }
    
    public int getTreeHeight() {
        return root.getTreeHeight();
    }
    
    public void add(Node node) {
        if(root == null) {
            root = node;
        }else {
            root.add(node);
        }
    }
    
    public void infixOrder() {
        if(root == null) {
            System.out.println("二叉排序树为空!");
        }else {
            root.infixOrder();
        }
    }
}

class Node{
    int value;//节点的权（值）
    Node left;//左子树
    Node right;//右子树
    @Override
    public String toString() {
        return "Node [value=" + value + "]";
    }
    public Node(int value) {
        this.value = value;
    }
    
    
    //得到左子树的高度
    public int getLeftHeight() {
        if(this.left==null) {
            return 0;
        }
        return this.left.getTreeHeight();
    }
    
    //得到右子树的高度
    public int getRightHeight() {
        if(this.right==null) {
            return 0;
        }
        return this.right.getTreeHeight();
    }
    //得到整个树的高度
    public int getTreeHeight() {
        return Math.max(this.left==null ? 0:this.left.getTreeHeight(), 
                this.right==null ? 0:this.right.getTreeHeight()) + 1;
    }
    
    //左旋转
    public void leftSpin() {
        //创建一个新节点
        Node newNode = new Node(value);
        //让新节点的右指针指向根节点的右子树的左子树
        newNode.right = this.right.left;
        //让新节点的左指针指向根节点的左子树
        newNode.left = this.left;
        //把根节点的值替换成根节点的右子树的值
        this.value = this.right.value;
        //让根节点的右指针指向根节点的右子树的右子树
        this.right = this.right.right;
        //让根节点的左子树指向新节点
        this.left = newNode;
    }
    //右旋转
    public void rightSpin() {
        Node newCode = new Node(value);
        newCode.left = this.left.right;
        newCode.right = this.right;
        this.value = this.left.value;
        this.left = this.left.left;
        this.right = newCode;
    }
    //添加的方法
    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);
            }
        }
        
        //如果右边的高度大于左边的高度，就左旋转
        if(getRightHeight()-getLeftHeight()>1) {
            leftSpin();
        }
        //如果左边的高度大于右边的高度，就左旋转
        if(getLeftHeight()-getRightHeight()>1) {
            rightSpin();
        }
    }
    
    //中序遍历
    public void infixOrder() {
        if(this.left!=null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null) {
            this.right.infixOrder();
        }
    }
}