共计 7145 个字符，预计需要花费 18 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、均衡二叉树
1、1 二叉树的右旋转
1、2 二叉树的双旋转
1、均衡二叉树
1、1 二叉树的右旋转
在均衡二叉树第一篇（Java 实现）这篇文章的时候，咱们学的更多的内容是二叉树的左旋转，好了，咱们这里学一下二叉树的右旋转；咱们进行一棵二叉树的右旋转，目标是让它变成一棵均衡二叉树对不对？进行右旋转的这棵树须要满足以下条件：左子树的高度比右子树的高度大，而且这个数值肯定至多是 2。
好了，当初咱们玩一下二叉树的右旋转，假如咱们拿到一个数列 array = {11,12,8,9,7,5}；依据二叉排序树（Java 实现）这篇文章所学到的常识，将 array 构建成一棵二叉排序树的话，那么就失去如图 1 所示的二叉树；
图片
看图 1，左子树的高度为 3，右子树的高度为 1，显然它不是一颗均衡二叉树，左子树的高度比右子树的高度大，而且这个数值是 2，所以咱们要对它进行右旋转，当初咱们剖析一下图 1 中二叉树右旋转的思路；
（1）新创建一个节点，这个新节点的值等于根节点的值，如图 2 所示；
图片
（2）咱们把根节点作为以后节点，把新节点的左子树指向以后节点的左子树的右子树，把新节点的右子树指向以后节点的右子树，这时候失去图 3 所示的结构图；
图片
（3）把以后节点的值改为以后节点的左子树的值，这时候就失去如图 4 所示的结构图；
图片
（4）把以后节点的左子树指向左子树的左子树（也就是红色数字 8 的左子树指向 7 节点），把以后节点的右子树指向新的节点（也就是红色数字 8 的右子树指向红色数字 11），这时候就失去如图 5 所示的结构图；
图片
（5）这时候红色数字 8 的节点作为新的根节点，而红色数字 8 的节点没有任何节点指向它，咱们就把它省略掉，咱们把图 5 的结构图简化一下，失去图 6 所示的二叉树；
图片
（6）第一次右旋转实现后，咱们判断一下这棵二叉树是不是均衡二叉树，如果不是，那就进行下一轮的右旋转；很显然，图 6 中的二叉树的左子树的高度和右子树的高度都是 2，所以是一棵均衡二叉树。
比照了一下图 1 和图 6，咱们发现啊，进行一轮右旋转后，旧的根节点的左子树就变成了新的根节点，新的根节点的右子树就变成了旧的根节点，旧的根节点的左子树的右子树就变成了新的根节点的右子树的左子树；这里左旋转的规定无非就是将旧的根节点的左子节点作为新的根节点，将旧的根节点作为新根节点的右子节点，将旧的根节点的左子节点的右子节点作为新根节点的右子节点的左子节点。
好，咱们当初对数列 array = {11,12,8,9,7,5} 进行构建一棵二叉排序树，并进行右旋转，当初用代码实现一把；
（1）写一个节点类 Node：
package com.xiaoer.demo;
public class Node {
private Node leftNode;
private Node rightNode;
private int value;
// 返回左子树的高度
public int leftHeight() {
int height = leftNode == null ? 0 : leftNode.height();
return height;}
// 返回右子树的高度
public int rightHeight() {
int height = rightNode == null ? 0 : rightNode.height();
return height;}
// 返回以后节点的高度
public int height() {
int height = Math.max(leftNode == null ? 0 : leftNode.height(),
rightNode == null ? 0 : rightNode.height()) + 1;
return height;}
public Node(int value) {
super();
this.value = value;}
/**
- 增加节点办法
- @param isRotate 示意是否进行旋转
*/
public void addNode(Node node, boolean isRotate) {
if (node == null) {System.out.println("该节点为空，不进行增加");
return;
}
// 判断传入节点的值是否比以后节点的值小
if (node.value < value) {
// 如果以后节点的左子节点为空，那么就把传入的节点作为以后节点的左子节点
if (leftNode == null) {
leftNode = node;
// 递归遍历以后节点的左子树增加 node
} else {leftNode.addNode(node, isRotate);
}
// 否则增加的节点的值大于等于以后节点的值
} else {
// 如果以后节点的右子节点为空，那么就把传入的节点作为以后节点的右子节点
if (rightNode == null) {
rightNode = node;
// 递归遍历以后节点的右子树增加 node
} else {rightNode.addNode(node, isRotate);
}
}
if (isRotate) {if (leftHeight() - rightHeight() > 1) {rightRotate();
}
}
}
// 这里进行右旋转
public void rightRotate() {
// 创立新的节点，以以后节点的值作为 value
Node newNode = new Node(value);
// 把新的结点的左子树指向以后结点的左子树的右子树
newNode.leftNode = leftNode.rightNode;
// 把新的结点的右子树指向以后节点的右子树
newNode.rightNode = rightNode;
// 把以后节点的值批改为左子树的值
value = leftNode.value;
// 把以后节点的左子树指向以后节点的左子树的左子树
leftNode = leftNode.leftNode;
// 把以后节点的右子树指向新的节点
rightNode = newNode;}
// 后续遍历
public void postOrder() {
if (leftNode != null) {leftNode.postOrder();
}
if (rightNode != null) {rightNode.postOrder();
}
System.out.println(this);}
@Override
public String toString() {
return "Node [value=" + value + "]";}
}
（2）写一个测试类 Test：
package com.xiaoer.demo;
public class Test {
private Node rootNode;
public static void main(String[] args) {
}
private void addNode(Node node,boolean isRotate) {
if (rootNode == null) {rootNode = node;} else {rootNode.addNode(node,isRotate);
}}
private void postOrder() {
if (rootNode == null) {System.out.println("这是一棵空树");
} else {rootNode.postOrder();
}}
}
首先咱们要验证一下咱们创立的二叉排序树的构造像图 1 所示，左子树的高度是 3，右子树的高度是 1，图 1 的二叉排序的后序遍历为：5 7 9 8 12 11；咱们在程序入口处加上如下代码；
public static void main(String[] args) {
int[] array = { 11,12,8,9,7,5};
Test test = new Test();
for (int i = 0; i < array.length; i++) {test.addNode(new Node(array[i]),false);
}
System.out.println("左子树的高度：" + test.rootNode.leftHeight());
System.out.println("右子树的高度：" + test.rootNode.rightHeight());
// 二叉树的后续遍历
test.postOrder();}
运行一下程序，日志打印如下所示；
图片
构建的二叉排序树和图 1 的一样，当初咱们批改一下程序入口的办法，让它对图 1 的二叉排序树执行右旋转操作；
public static void main(String[] args) {
int[] array = { 11,12,8,9,7,5};
Test test = new Test();
for (int i = 0; i < array.length; i++) {test.addNode(new Node(array[i]),true);
}
System.out.println("左子树的高度：" + test.rootNode.leftHeight());
System.out.println("右子树的高度：" + test.rootNode.rightHeight());
// 二叉树的后续遍历
test.postOrder();}
执行完右旋转操作后，重新组建的二叉树就会和图 6 的二叉树一样，左子树的高度是 2，右子树的高度是 2，后序遍历是 5 7 9 12 11 8；咱们执行一下程序，日志打印如下所示；
图片
构建的二叉排序树和图 6 的一样，阐明实现这个算法没有问题。
1、2 二叉树的双旋转
这里二叉树的双旋转就有两种状况了，第一种是先左旋转再右旋转，第二种是先右旋转再左旋转，好，咱们先说说它的第一种状况；
先左旋转再右旋转
为了能剖析分明这种状况，咱们用数列 array = {5，6，2，1，3，4} 构建一棵二叉排序树（无关构建二叉排序树的过程能够看二叉排序树（Java 实现）这篇文章），如图 7 所示；
图片
思路剖析：
（1）以后节点合乎右旋转条件时（例如图 7 中的根节点可看做是以后节点，那么就合乎右旋转条件）。
（2）如果以后节点的左子树的右子树高度大于以后节点的左子树的左子树的高度（例如图 7 中的以后节点是根节点，以后节点的左子节点就是 2 节点，2 节点的左子树显著就比 2 节点的右子树高度小对不对）。
（3）先对以后这个结点的左节点进行左旋转（例如图 7 中的 2 节点进行左旋转，无关二叉树的左旋转，可看均衡二叉树第一篇（Java 实现）这篇文章）。
（4）在对以后结点进行右旋转的操作（例如图 7 中的根节点进行右旋转的操作）。
先对以后这个结点的左节点进行左旋转，例如咱们拿图 7 中的 2 节点进行左旋转，失去图 8 所示的二叉树；
图片
在对以后结点进行右旋转的操作，例如就拿图 8 的二叉树而言，5 节点就是根节点，对 5 节点进行右旋转，那么就失去图 9 所示的二叉树；
图片
好，咱们当初说一下第二种状况，也就是先右旋转再左旋转；
先右旋转再左旋转
同样为了能剖析分明这种状况，咱们用数列 array = {2，1，5，6，3，4} 构建一棵二叉排序树，如图 10 所示；
图片
思路剖析：
（1）以后节点合乎左旋转条件时（例如图 10 中的根节点可看做是以后节点，那么就合乎左旋转条件）。
（2）如果以后节点的右子树的左子树高度大于以后节点的右子树的右子树的高度（例如图 10 中的以后节点是根节点，以后节点的右子节点就是 5 节点，5 节点的左子树显著就比 5 节点的右子树高度大）。
（3）先对以后这个结点的右节点进行右旋转（例如图 10 中的 5 节点进行右旋转）。
（4）在对以后结点进行左旋转的操作（例如图 10 中的根节点进行左旋转的操作）。
先对以后这个结点的右节点进行右旋转，例如咱们拿图 10 中的 5 节点进行右旋转，失去图 11 所示的二叉树；
图片
在对以后结点进行左旋转的操作，例如就拿图 11 的二叉树而言，2 节点就是根节点，对 2 节点进行左旋转，那么就失去图 12 所示的二叉树；
图片
好了，咱们当初用代码实现一把二叉树的双旋转，然而这里只实现“先左旋转再右旋转”的状况，“先右旋转再左旋转”这种状况就由有趣味的读者去实现吧；
（1）咱们拿数列 array = {5，6，2，1，3，4}，构建一棵如图 7 的二叉排序树，在下面右旋转的代码案例中持续增加相应的代码，在 Node 类中增加左旋转的办法 leftRotate：
// 这里进行左旋转
public void leftRotate() {
// 创立新的节点，以以后节点的值作为 value
Node newNode = new Node(value);
// 把新的结点的左子树指向以后结点的左子树
newNode.leftNode = leftNode;
// 把新的结点的右子树指向以后节点的右子树的左子树
newNode.rightNode = rightNode.leftNode;
// 把以后节点的值批改为右子树的值
value = rightNode.value;
// 把以后节点的右子树指向以后节点的右子树的右子树
rightNode = rightNode.rightNode;
// 把以后节点的左子树指向新的节点
leftNode = newNode;}
（2）在 Node 类中批改 addNode(Node node, boolean isRotate) 办法；
/**
- 增加节点办法
- @param isRotate 示意是否进行旋转
*/
public void addNode(Node node, boolean isRotate) {
if (node == null) {System.out.println("该节点为空，不进行增加");
return;
}
// 判断传入节点的值是否比以后节点的值小
if (node.value < value) {
// 如果以后节点的左子节点为空，那么就把传入的节点作为以后节点的左子节点
if (leftNode == null) {
leftNode = node;
// 递归遍历以后节点的左子树增加 node
} else {leftNode.addNode(node, isRotate);
}
// 否则增加的节点的值大于等于以后节点的值
} else {
// 如果以后节点的右子节点为空，那么就把传入的节点作为以后节点的右子节点
if (rightNode == null) {
rightNode = node;
// 递归遍历以后节点的右子树增加 node
} else {rightNode.addNode(node, isRotate);
}
}
if (isRotate) {
// 增加完一个节点后，如果以后节点的右子树的高度大于以后节点的左子树的高度
// 就进行左旋转
if (leftHeight() - rightHeight() < -1) {
// 如果以后节点的右子树的右子树高度小于以后节点的右子树的左子树高度
if (rightNode != null && rightNode.rightHeight() < rightNode.leftHeight()) {
// 对以后节点的右子树进行右旋转
rightNode.rightRotate();
// 对以后节点进行左旋转
leftRotate();} else {leftRotate();
}
return;
}
// 增加完一个节点后，如果以后节点的右子树的高度小于以后节点的左子树的高度
// 就进行右旋转
if (leftHeight() - rightHeight() > 1) {
// 如果以后节点的左子树的右子树高度大于以后节点的左子树的左子树高度
if (leftNode != null && leftNode.rightHeight() > leftNode.leftHeight()) {
// 对以后节点的左子树进行左旋转
leftNode.leftRotate();
// 对以后节点进行右旋转
rightRotate();} else {rightRotate();
}
}
}
}
（3）程序入口类 Test 的 main(String[] args) 办法调用如下所示；
public static void main(String[] args) {
int[] array = { 5,6,2,1,3,4};
Test test = new Test();
for (int i = 0; i < array.length; i++) {test.addNode(new Node(array[i]),false);
}
System.out.println("左子树的高度：" + test.rootNode.leftHeight());
System.out.println("右子树的高度：" + test.rootNode.rightHeight());
// 二叉树的后续遍历
test.postOrder();}
咱们晓得图 7 中的二叉树，左子树的高度为 3，右子树的高度为 1，后序遍历为：1 4 3 2 6 5；咱们执行一下程序，看看构建进去的二叉树是否和图 7 的一样，日志打印如下所示；
图片
从日志打印看出，构建进去的二叉树和图 7 的截然不同；
好，咱们当初要对它进行双旋转，图 9 的二叉树的左子树的高度为 2，右子树的高度为 2，后序遍历为：1 2 4 6 5 3，咱们略微改一下 main(String[] args) 办法调用；
public static void main(String[] args) {
int[] array = { 5,6,2,1,3,4};
Test test = new Test();
for (int i = 0; i < array.length; i++) {test.addNode(new Node(array[i]),true);
}
System.out.println("左子树的高度：" + test.rootNode.leftHeight());
System.out.println("右子树的高度：" + test.rootNode.rightHeight());
// 二叉树的后续遍历
test.postOrder();}
执行一下程序，日志打印如下所示；
图片
从日志能够看出，图 7 中的二叉树通过双旋转后就变成了图 9 中的二叉树，阐明咱们写的算法没有问题。
