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;}@Overridepublic 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 < this.value){//添加的结点的值 < 当前结点的值if(this.left == null){ //如果当前结点左子结点为nullthis.left = node;}else{//递归的向左子树添加this.left.addNode(node);}}else{//添加的结点的值 > 当前结点的值if(this.right == null){ //如果当前结点右子结点为nullthis.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指向noderoot = 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};//创建一个AVL树对象AVLTree avlTree = new AVLTree();//添加节点for(int i=0;i<arr.length;i++){avlTree.addBstNode(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());}
}

4）、运行main函数，输出结果如下：

5、平衡二叉树左旋转代码示例（基于求二叉树高度的基础上添加左旋转方法代码）

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;}@Overridepublic 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:  左旋转方法* @Author: xz* @Date: 2020/10/13 22:44*/public void leftRotate() {//创建新的结点，以当前根结点的值Node newNode = new Node(value);//把新的结点的左子树设置成当前结点的左子树newNode.left = left;//把新的结点的右子树设置成带你过去结点的右子树的左子树newNode.right = right.left;//把当前结点的值替换成右子结点的值value = right.value;//把当前结点的右子树设置成当前结点右子树的右子树right = right.right;//把当前结点的左子树(左子结点)设置成新的结点left = newNode;}/*** @Description: 一、递归的形式添加结点，注意需要满足二叉排序树的要求* @Param:  node 传入的几点* @Author: xz* @Date: 2020/9/27 21:58*/public void addNode(Node node){if(node == null){return;}if(node.value < this.value){//添加的结点的值 < 当前结点的值if(this.left == null){ //如果当前结点左子结点为nullthis.left = node;}else{//递归的向左子树添加this.left.addNode(node);}}else{//添加的结点的值 > 当前结点的值if(this.right == null){ //如果当前结点右子结点为nullthis.right = node;}else{//递归的向右子树添加this.right.addNode(node);}}//当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转if(rightHeight() - leftHeight() > 1) {leftRotate();}}/*** @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指向noderoot = 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};//创建一个AVL树对象AVLTree avlTree = new AVLTree();//添加节点for(int i=0;i<arr.length;i++){avlTree.addBstNode(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());}
}

4）、运行main函数，输出结果如下：