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

文章收藏的好句子：苦难，是人生的试金石。

目录

1、二叉排序树可能存在的问题

2、平衡二叉树

     2、1 平衡二叉树的基本介绍

     2、2 二叉树的左旋转

1、二叉排序树可能存在的问题

在二叉排序树（Java实现）这篇文章，我们学习了二叉排序树，但是它可能存在一些问题，假设我们拿到的是一个从小到大排序的数列 array = {3 , 4 , 5 , 6 , 7 , 8 , 9}，那么构建出来的二叉排序树就如图1所示；

从图1可以看出，构建出来的二叉排序树有如下问题：左子树全部为空，像一个单链表；插入速度不受影响；查询速度会降低，不能发挥二叉排序树的优点，每次还需要比较左子树，其查询速度比单链表还慢；这时候如果要解决图1中出现的问题，就要引入到平衡二叉树了。

2、平衡二叉树

2、1 平衡二叉树的基本介绍

平衡二叉树也叫平衡二叉搜索树又被称为AVL树，可以保证查询效率；它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

好，为了方便理解平衡二叉树，我这里列举2个案例一下；

案例1：看图2中的二叉树，根节点的左子节点2（以2节点看做是 “根节点”，此时红框里的3个节点也可以当做一棵小的二叉树）的高度为2，根节点的右子节5（以5节点看做是 “根节点”，此时红框里的1个节点也可以当做一棵小的二叉树）的高度为1，这时候根节点的左右子树的高度差的绝对值为1，不超过1，所以图2中的二叉树是平衡二叉树。

案例2：看图3中的二叉树，根节点的左子节点8（以8节点看做是 “根节点”，此时红框里的4个节点也可以当做一棵小的二叉树）的高度为3，根节点的右子节11（以11节点看做是 “根节点”，此时红框里的1个节点也可以当做一棵小的二叉树）的高度为1，这时候根节点的左右子树的高度差的绝对值为2，超过了1，所以图3中的二叉树不是平衡二叉树。

2、2 二叉树的左旋转

我们进行一棵二叉树的左旋转，目的无非就是让这棵二叉树变成平衡二叉树；那进行左旋转无非就是这颗二叉树不是平衡二叉树，而且它左子树的高度比右子树的高度小，而且这个数值一定至少是2。好了，假设我们拿到一个数列 array = {2,1,4,3,5,6}，根据二叉排序树（Java实现）这篇文章所学到的知识，我们构建的二叉排序树就如图4所示；

看图4，左子树的高度为1，右子树的高度为3，显然它不是一颗平衡二叉树，左子树的高度比右子树的高度小，而且这个数值是2，所以如果我们要把图4中的二叉树变成平衡二叉树，就要对图4这棵二叉树进行左旋转，如何进行左旋转呢？我们对它进行思路分析一下。

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

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

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

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

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

（6）第一次左旋转完成后，我们判断一下这棵二叉树是不是平衡二叉树，如果不是，那就进行下一轮的左旋转；很显然，图9中的二叉树的左子树的高度和右子树的高度都是2，所以是一棵平衡二叉树。

对比了一下图4和图9，我们发现啊，进行一轮左旋转后，旧的根节点的右子树就变成了新的根节点，新的根节点的左子树就变成了旧的根节点，新的根节点的左子树就变成了旧的根节点的右子树；这里左旋转的规则无非就是将旧的右子节点作为新的根节点，将旧的根节点作为新根节点的左子节点，将旧的根节点的右子节点的左子节点作为新根节点的左子节点的右子节点。

好了，我们现在对数列 array =  {2,1,4,3,5,6} 进行构建一棵二叉排序树，并进行左旋转，现在用代码实现一把；

（1）新建一个节点类 Node ：

package com.xiaoer.binarysorttree;


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;
  }
  
  //添加节点方法
  public void addNode(Node node) {
    if (node == null) {
      System.out.println("该节点为空，不进行添加");
      return;
    }
    
    //判断传入节点的值是否比当前节点的值小
    if (node.value < value) {
      
      //如果当前节点的左子节点为空，那么就把传入的节点作为当前节点的左子节点
      if (leftNode == null) {
        leftNode = node;
        
        //递归遍历当前节点的左子树添加 node
      } else {
        leftNode.addNode(node);
      }
      
      //否则添加的节点的值大于等于当前节点的值
    } else {
      
      //如果当前节点的右子节点为空，那么就把传入的节点作为当前节点的右子节点
      if (rightNode == null) {
        rightNode = node;
        
        //递归遍历当前节点的右子树添加 node
      } else {
        rightNode.addNode(node);
      }
    }
    
  }
  
  //这里进行左旋转，当前节点是指根节点
  public void leftRotate() {
    
    //创建新的节点，以当前节点的值作为 value
    Node newNode = new Node(value);
    
    //把新的结点的左子树指向当前结点的左子树
    newNode.leftNode = leftNode;
    
    //把新的结点的右子树指向当前节点的右子树的左子树
    newNode.rightNode = rightNode.leftNode;
    
    //把当前节点的值修改为右子树的值
    value = rightNode.value;
    
    //把当前节点的右子树指向当前节点的右子树的右子树
    rightNode = rightNode.rightNode;
    
    //把当前节点的左子树指向新的节点
    leftNode = 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.binarysorttree;


public class Test {
  private Node rootNode;


  public static void main(String[] args) {
    int[] array = { 2, 1, 4, 3, 5, 6 };
    Test test = new Test();


    // for 循环将数组转化成二叉排序树
    for (int i = 0; i < array.length; i++) {
      test.addNode(new Node(array[i]));
    }
    System.out.println("在没有进行左旋转之前");
    System.out.println("左子树的高度：" + test.rootNode.leftHeight());
    System.out.println("右子树的高度：" + test.rootNode.rightHeight());
    // 二叉排序树的后续遍历
    test.postOrder();


    System.out.println("进行左旋转之后");
    test.leftRotate();
    System.out.println("左子树的高度：" + test.rootNode.leftHeight());
    System.out.println("右子树的高度：" + test.rootNode.rightHeight());
    // 二叉排序树的后续遍历
    test.postOrder();
  }
  
  private void leftRotate() {
    if (rootNode == null) {
      System.out.println("这是一棵空树，不能进行左旋转");
    } else {
      if (rootNode.rightHeight() - rootNode.leftHeight() > 1) {
        rootNode.leftRotate();
        leftRotate();
      }
    }
  }


  private void addNode(Node node) {
    if (rootNode == null) {
      rootNode = node;
    } else {
      rootNode.addNode(node);
    }
  }


  private void postOrder() {
    if (rootNode == null) {
      System.out.println("这是一棵空树");
    } else {
      rootNode.postOrder();
    }
  }
}

这里如何判断我们的左旋转是否成功呢？我们看没旋转之前的图4，左子树的高度为1，右子树的高度为3，后序遍历为：1 3 6 5 4 2；旋转之后的图9，左子树的高度为2，右子树的高度为2，后序遍历为：1 3 2 6 5 4；运行程序一把；

看到运行结果了没，和图9的结果是一样的，左子树的高度为2，右子树的高度为2，后序遍历为：1 3 2 6 5 4 。