java数据结构和算法——平衡二叉树之右旋转

1、平衡二叉树右旋转思路图解

2、什么时候进行平衡二叉树右旋转

• 当左子树与右子树高度差的绝对值大于1是进行右旋转

3、平衡二叉树右旋转目的

• 降低左子树高度

4、求二叉树高度代码示例

1）、创建一个节点类 Node

package com.rf.springboot01.dataStructure.avlTree;

/**
 * @description: 创建一个节点类 Node
 * @author: xiaozhi
 * @create: 2020-10-13 22:04
 */
public class Node {
    public int value;//节点的值
    public Node left;//左节点
    public Node right;//右节点

    //构造方法
    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    /** 
    * @Description:  返回以当前节点为根节点的树的高度
    * @Author: xz
    * @Date: 2020/10/13 22:07
    */
    public int height(){
        return  Math.max(left ==null ? 0 : left.height(),right == null ? 0 : right.height())+1;
    }
    /** 
    * @Description: 返回左子树的高度
    * @Author: xz
    * @Date: 2020/10/13 22:10
    */
    public int leftHeight(){
        if(left == null){
            return 0;
        }
        return  left.height();
    }
    /**
    * @Description: 返回右子树的高度
    * @Author: xz
    * @Date: 2020/10/13 22:11
    */
    public int rightHeight(){
        if(right ==null){
            return 0;
        }
        return right.height();
    }
    /**
     * @Description: 一、递归的形式添加结点，注意需要满足二叉排序树的要求
     * @Param:  node 传入的几点
     * @Author: xz
     * @Date: 2020/9/27 21:58
     */
    public void addNode(Node node){
        if(node == null){
            return;
        }
        if(node.value  当前结点的值
            if(this.right == null){ //如果当前结点右子结点为null
                this.right = node;
            }else{//递归的向右子树添加
                this.right.addNode(node);
            }
        }
    }

    /**
     * @Description: 二、中序遍历二叉排序树
     * @Param:
     * @Author: xz
     * @return:
     * @Date: 2020/9/27 22:09
     */
    public void infixOrder(){
        //左子节点不为null，向左子节点中序遍历
        if(this.left != null){
            this.left.infixOrder();
        }

        //输出当前节点
        System.out.println(this);

        //右子节点不为null，向右子节点中序遍历
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

}

2）、创建平衡二叉树类（即AVL树类）

package com.rf.springboot01.dataStructure.avlTree;

/**
 * @description: 创建平衡二叉树（即AVL树）
 * @author: xiaozhi
 * @create: 2020-10-13 22:13
 */
public class AVLTree {
    public Node root;

    public Node getRoot() {
        return root;
    }

    /**
     * @Description:  一、添加二叉排序树节点方法
     * @Param:  node 传入的节点
     * @Author: xz
     * @Date: 2020/9/27 22:18
     */
    public void addBstNode(Node node){
        if(root == null){//如果root为空则直接让root指向node
            root = node;
        }else{
            root.addNode(node);
        }
    }
    /**
     * @Description:  二、中序遍历二叉排序树方法
     * @Param:
     * @Author: xz
     * @return:
     * @Date: 2020/9/27 22:25
     */
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

}

3）、创建二叉树测试类

package com.rf.springboot01.dataStructure.avlTree;

/**
 * @description: 平衡二叉树测试类
 * @author: xiaozhi
 * @create: 2020-10-13 22:15
 */
public class AVLTreeTest {
    public static void main(String[] args) {
        //定义一个数组
        int[] arr={10,12,8,9,7,6};
        //创建一个AVL树对象
        AVLTree avlTree = new AVLTree();
        //添加节点
        for(int i=0;i 1, 右旋转
        if(leftHeight() - rightHeight() > 1) {
            rightRotate();//调用右旋转
        }
    }

    /**
     * @Description: 二、中序遍历二叉排序树
     * @Param:
     * @Author: xz
     * @return:
     * @Date: 2020/9/27 22:09
     */
    public void infixOrder(){
        //左子节点不为null，向左子节点中序遍历
        if(this.left != null){
            this.left.infixOrder();
        }

        //输出当前节点
        System.out.println(this);

        //右子节点不为null，向右子节点中序遍历
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

}

2）、创建平衡二叉树类（即AVL树）

package com.rf.springboot01.dataStructure.avlTree;

/**
 * @description: 创建平衡二叉树（即AVL树）
 * @author: xiaozhi
 * @create: 2020-10-13 22:13
 */
public class AVLTree {
    public Node root;

    public Node getRoot() {
        return root;
    }

    /**
     * @Description:  一、添加二叉排序树节点方法
     * @Param:  node 传入的节点
     * @Author: xz
     * @Date: 2020/9/27 22:18
     */
    public void addBstNode(Node node){
        if(root == null){//如果root为空则直接让root指向node
            root = node;
        }else{
            root.addNode(node);
        }
    }
    /**
     * @Description:  二、中序遍历二叉排序树方法
     * @Param:
     * @Author: xz
     * @return:
     * @Date: 2020/9/27 22:25
     */
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

}

3）、创建平衡二叉树测试类

package com.rf.springboot01.dataStructure.avlTree;

/**
 * @description: 平衡二叉树测试类
 * @author: xiaozhi
 * @create: 2020-10-13 22:15
 */
public class AVLTreeTest {
    public static void main(String[] args) {
        //定义一个数组，测试左旋转数组
        //int[] arr={4,3,6,5,7,8};
        //测试右旋转数组
        int[] arr={10,12,8,9,7,6};
        //创建一个AVL树对象
        AVLTree avlTree = new AVLTree();
        //添加节点
        for(int i=0;i