平衡二叉树第二篇（Java实现）

vlambda
2022-05-09

平衡二叉树第二篇（Java实现）

文章收藏的好句子：书籍是全世界的营养品，生活里没有书籍，就好像大地没有阳光；智慧里没有书籍，就好像鸟儿没有翅膀。

1、平衡二叉树

1、1 二叉树的右旋转

1、2 二叉树的双旋转

1、平衡二叉树

1、1 二叉树的右旋转

在这篇文章的时候，我们学的更多的内容是二叉树的左旋转，好了，我们这里学一下二叉树的右旋转；我们进行一棵二叉树的右旋转，目的是让它变成一棵平衡二叉树对不对？进行右旋转的这棵树需要满足以下条件：左子树的高度比右子树的高度大，而且这个数值一定至少是2。

好了，现在我们玩一下二叉树的右旋转，假设我们拿到一个数列 array = {11,12,8,9,7,5}；根据这篇文章所学到的知识，将 array 构建成一棵二叉排序树的话，那么就得到如图1所示的二叉树；

看图1，左子树的高度为3，右子树的高度为1，显然它不是一颗平衡二叉树，左子树的高度比右子树的高度大，而且这个数值是2，所以我们要对它进行右旋转，现在我们分析一下图1中二叉树右旋转的思路；

（1）新创建一个节点，这个新节点的值等于根节点的值，如图2所示；

平衡二叉树第二篇（Java实现）

（2）我们把根节点作为当前节点，把新节点的左子树指向当前节点的左子树的右子树，把新节点的右子树指向当前节点的右子树，这时候得到图3所示的结构图；

平衡二叉树第二篇（Java实现）

（3）把当前节点的值改为当前节点的左子树的值，这时候就得到如图4所示的结构图；

平衡二叉树第二篇（Java实现）

（4）把当前节点的左子树指向左子树的左子树（也就是红色数字8的左子树指向7节点），把当前节点的右子树指向新的节点（也就是红色数字8的右子树指向红色数字11），这时候就得到如图5所示的结构图；

平衡二叉树第二篇（Java实现）

（5）这时候红色数字8的节点作为新的根节点，而白色数字8的节点没有任何节点指向它，我们就把它省略掉，我们把图5的结构图简化一下，得到图6所示的二叉树；

平衡二叉树第二篇（Java实现）

（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(); }

运行一下程序，日志打印如下所示；

平衡二叉树第二篇（Java实现）

构建的二叉排序树和图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；我们执行一下程序，日志打印如下所示；

平衡二叉树第二篇（Java实现）

构建的二叉排序树和图6的一样，说明实现这个算法没有问题。

1、2 二叉树的双旋转

这里二叉树的双旋转就有两种情况了，第一种是先左旋转再右旋转，第二种是先右旋转再左旋转，好，我们先说说它的第一种情况；

先左旋转再右旋转

为了能分析清楚这种情况，我们用数列 array = {5，6，2，1，3，4}构建一棵二叉排序树（有关构建二叉排序树的过程可以看这篇文章），如图7所示；

平衡二叉树第二篇（Java实现）

思路分析：

（1）当前节点符合右旋转条件时（例如图7中的根节点可看做是当前节点，那么就符合右旋转条件）。

（2）如果当前节点的左子树的右子树高度大于当前节点的左子树的左子树的高度（例如图7中的当前节点是根节点，当前节点的左子节点就是2节点，2节点的左子树明显就比2节点的右子树高度小对不对）。

（3）先对当前这个结点的左节点进行左旋转（例如图7中的2节点进行左旋转，有关二叉树的左旋转，可看这篇文章）。

（4）在对当前结点进行右旋转的操作（例如图7中的根节点进行右旋转的操作）。

先对当前这个结点的左节点进行左旋转，例如我们拿图7中的2节点进行左旋转，得到图8所示的二叉树；

平衡二叉树第二篇（Java实现）

在对当前结点进行右旋转的操作，例如就拿图8的二叉树而言，5节点就是根节点，对5节点进行右旋转，那么就得到图9所示的二叉树；

平衡二叉树第二篇（Java实现）

好，我们现在说一下第二种情况，也就是先右旋转再左旋转；

先右旋转再左旋转

同样为了能分析清楚这种情况，我们用数列 array = {2，1，5，6，3，4}构建一棵二叉排序树，如图10所示；

平衡二叉树第二篇（Java实现）

思路分析：

（1）当前节点符合左旋转条件时（例如图10中的根节点可看做是当前节点，那么就符合左旋转条件）。

（2）如果当前节点的右子树的左子树高度大于当前节点的右子树的右子树的高度（例如图10中的当前节点是根节点，当前节点的右子节点就是5节点，5节点的左子树明显就比5节点的右子树高度大）。

（3）先对当前这个结点的右节点进行右旋转（例如图10中的5节点进行右旋转）。

（4）在对当前结点进行左旋转的操作（例如图10中的根节点进行左旋转的操作）。

先对当前这个结点的右节点进行右旋转，例如我们拿图10中的5节点进行右旋转，得到图11所示的二叉树；

平衡二叉树第二篇（Java实现）

在对当前结点进行左旋转的操作，例如就拿图11的二叉树而言，2节点就是根节点，对2节点进行左旋转，那么就得到图12所示的二叉树；

平衡二叉树第二篇（Java实现）

好了，我们现在用代码实现一把二叉树的双旋转，但是这里只实现 “先左旋转再右旋转” 的情况，“先右旋转再左旋转” 这种情况就由有兴趣的读者去实现吧；

（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中的二叉树，说明我们写的算法没有问题。

vlambda博客
学习文章列表