十一、树结构实际应用

11.1 、堆排序

11.1.1 、堆排序基本介绍

1) 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序。

2) 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意: 没有要求结点的左孩子的值和右孩子的值的大小关系。

3) 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

4) 大顶堆举例说明

5) 小顶堆举例说明

6) 一般升序采用大顶堆，降序采用小顶堆

11.1.2 、堆排序基本思想

堆排序的基本思想是：

1) 将待排序序列构造成一个大顶堆

2) 此时，整个序列的最大值就是堆顶的根节点。

3) 将其与末尾元素进行交换，此时末尾就为最大值。

4) 然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.

11.1.3 、堆排序步骤图解说明

要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升

步骤一

构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。原始的数组 [4, 6, 8, 5, 9]

1) .假设给定无序序列结构如下

2) .此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点arr.length/2-1=5/2-1=1，也就是下面的 6 结点），从左至右，从下至上进行调整

3) .找到第二个非叶节点 4，由于[4,9,8]中 9 元素最大，4 和 9 交换。

4) 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换4 和6。

此时，我们就将一个无序序列构造成了一个大顶堆

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换

1) .将堆顶元素 9 和末尾元素 4 进行交换

2) .重新调整结构，使其继续满足堆定义

3) .再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8.

4) 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

1).将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

11.1.4 、堆排序代码实现

要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。

1) 堆排序不是很好理解，通过 Debug 帮助理解堆排序

2) 堆排序的速度非常快，在我的机器上 8 百万数据 3 秒左右。O(nlogn)

3) 代码实现

/**
 * description
 * 堆排序——树的实际应用
 *
 * @author xujicheng
 * @since 2022年12月04日 15:35
 */
public class HeapSort {
    public static void main(String[] args) {
        //要求将数组进行升序排列
        int[] arr = {4, 6, 8, 5, 9};
        headSort(arr);
    }

    /**
     * 编写一个堆排序的方法
     *
     * @param arr 需要进行堆排序的数组
     */
    public static void headSort(int[] arr) {
        int temp = 0; //临时变量，用于交换
        System.out.println("堆排序");
        //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或者小顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //将栈顶元素于末尾元素交换，将最大元素"沉"到数组末端
        //重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整，直到有序
        for (int j = arr.length - 1; j > 0; j--) {
            //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 将一个数组（二叉树），调整成一个大顶堆
     * 功能：完成将以i 对应的非叶子节点的数调整成大顶堆
     * 举例： int[] arr = {4, 6, 8, 5, 9}; -->  i = 1  => adjustHeap --> 得到 {4, 9, 8, 5, 6}
     * 如果我们再次调用adjustHeap 传入的是 i = 0 --> 得到 {9, 6, 8, 5, 4}
     *
     * @param arr    待调整的数组
     * @param i      表示非叶子节点在数组中的索引
     * @param length 表示对多少个元素进行调整，length是在逐渐的减少
     */
    public static void adjustHeap(int[] arr, int i, int length) {

        int temp = arr[i];  //先取出当前元素的值并保存在当前变量
        //开始调整,说明：k = i * 2 + 1是i这个节点的左子节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                //说明这个左子节点值小于右子节点的值
                k++; //k就指向右子节点
            }
            if (arr[k] > temp) { //如果子节点大于父节点
                arr[i] = arr[k];  //把较大的值赋给当前节点
                i = k;  //i 指向k，继续循环比较
            } else {
                break;
            }
        }
        //当for循环结束后，我们已经将以i 为父节点的树的最大值，放在了最顶上
        arr[i] = temp; //将temp值放到调整后的位置
    }
}

11.2 、赫夫曼树

11.2.1 、基本介绍

1) 给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。

2) 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近

11.2.2 、赫夫曼树几个重要概念和举例说明

1) 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为L-1

2) 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积

3) 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weightedpathlength) ,权值越大的结点离根结点越近的二叉树才是最优二叉树

4) WPL 最小的就是赫夫曼树

11.2.3 、赫夫曼树创建思路图解

给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树

思路分析(示意图)： {13, 7, 8, 3, 29, 6, 1}

构成赫夫曼树的步骤：

1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树

2) 取出根节点权值最小的两颗二叉树

3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4) 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

5) 图解:

11.2.4、赫夫曼树的代码实现

/**
 * description
 * 创建节点类
 * 为了让Node对象支持排序，让Node继承Comparable接口
 *
 * @author xujicheng
 * @since 2022年12月06日 10:29
 */
public class Node implements Comparable<Node> {

    int value;  //节点权值
    Node left;  //指向左子节点
    Node right; //指向右子节点

    //构造器，用于初始化权值
    public Node(int value) {
        this.value = value;
    }

    //写一个前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;  //表示从小到大进行排序
    }
}

/**
 * description
 * 赫夫曼树的代码实现
 *
 * @author xujicheng
 * @since 2022年12月06日 10:11
 */
public class HuffManTree {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node root = createHuffmanTree(arr);
        preOrder(root);
    }

    /**
     * 前序遍历的方法
     *
     * @param root 赫夫曼树的根节点
     */
    public static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("该霍夫曼树是空树");
        }
    }

    /**
     * 创建赫夫曼树的方法
     *
     * @param arr 需要进行霍夫曼树排序的数组
     */
    public static Node createHuffmanTree(int[] arr) {
        //遍历arr这个数组
        ArrayList<Node> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        while (nodes.size() > 1) {
            //从小到大进行排序
            Collections.sort(nodes);
            //取出权值最小的二叉树
            Node leftNode = nodes.get(0);
            //取出权值此小的二叉树
            Node rightNode = nodes.get(1);
            //构建一颗新的二叉树
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
            //从ArrayList中删除处理过的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将parent加入到nodes
            nodes.add(parent);
        }
        //返回最后这个节点
        return nodes.get(0);
    }
}

11.3 、赫夫曼编码

11.3.1 、基本介绍

1) 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法

2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。

3) 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间

4) 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码

11.3.2 、原理剖析

通信领域中信息的处理方式 1-定长编码

通信领域中信息的处理方式 2-变长编码

通信领域中信息的处理方式 3-赫夫曼编码

步骤如下：

传输的字符串

1) i like like like java do you like a java

2) d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数

3) 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

步骤：构成赫夫曼树的步骤：

1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树

2) 取出根节点权值最小的两颗二叉树

3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4) 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

4) 根据赫夫曼树，给各个字符,规定编码 (前缀编码)，向左的路径为0 向右的路径为1，编码如下:

o: 1000 u: 10010 d: 100110 y: 100111 i: 101

a : 110 k: 1110 e: 1111 j: 0000 v: 0001

l: 001 : 01

5) 按照上面的赫夫曼编码，我们的"i like like like java do you like a java" 字符串对应的编码为(注意这里我们使用的无损压缩)

1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通过赫夫曼编码处理长度为133

6）长度为： 133

说明: 原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%

此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性赫夫曼编码是无损处理方案

注意事项

注意, 这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl 是一样的，都是最小的, 最后生成的赫夫曼编码的长度是一样，比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为

11.3.3、最佳实践-数据压缩(创建赫夫曼树)

将给出的一段文本，比如 "i like like like java do you like a java" ，根据前面的讲的赫夫曼编码原理，对其进行数据压缩理处理形式：

如"1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 "

步骤 1：根据赫夫曼编码压缩数据的原理，需要创建 "i like like like java do you like a java" 对应的赫夫曼树

思路：

1、构建一个新的节点Node ，Node的属性 Node{ data(用于存放数据), weight(权值) ， left(指向左子节点) , right}
2、得到 "i like like like java do you like a java" 对应的byte[]数组
3、编写一个方法，将准备构建赫夫曼树的节点放到 List中，形式：[Node[date=97，weight = 5 ]，Node[data = 32 weight = 9]]体现 d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
4、可以通过List创建对应的赫夫曼树

/**
 * description
 * 创建Node，带数据和权值
 *
 * @author xujicheng
 * @since 2022年12月06日 17:15
 */
public class Node implements Comparable<Node> {

    Byte data; //用于存放数据本身，比如'a' --> 97
    int weight; //权值,表示数据出现的次数
    Node left;  //指向左边的节点
    Node right; //指向右边的节点

    //构造器，用于初始化权值和存放数据的data
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight; //代表将来比较的时候从小到大排序
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }
}

/**
 * description
 * 赫夫曼编码的代码是实现
 *
 * @author xujicheng
 * @since 2022年12月06日 17:14
 */
public class HuffManCode {
    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println(contentBytes.length);
        List<Node> nodes = getNodes(contentBytes);
        System.out.println(nodes);
        //测试创建二叉树
        System.out.println("赫夫曼树");
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        System.out.println("前序遍历");
        huffmanTreeRoot.preOrder();
    }

    //前序遍历的方法
    private static void preorder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("赫夫曼树为空");
        }
    }

    /**
     * 将左边构建赫夫曼树的Node 节点放到List
     *
     * @param bytes 需要构建的字节数
     * @return 返回的List形式 -->[Node[date=97，weight = 5 ]，Node[data = 32 weight = 9]]
     */
    private static List<Node> getNodes(byte[] bytes) {
        //创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<Node>();
        //存储每个byte出现的次数，使用map来统计,key为数据本身，Integer是次数
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) { //说明Map还没有这个字符数据，是第一次放入
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        //把每个键值对转成Node对象并加入到nodes集合
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    //通过一个List创建对应的赫夫曼树
    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //排序,从小到大
            Collections.sort(nodes);
            //取出第一颗最小的二叉树
            Node leftNode = nodes.get(0);
            //取出第二颗最小的二叉树
            Node rightNode = nodes.get(1);
            //创建一颗新的二叉树，它的根节点没有data，只有权值
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //将已经处理的两棵二叉树从nodes中删除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将新的二叉树加入到nodes
            nodes.add(parent);
        }
        //返回的nodes最后的节点，就是赫夫曼树的root节点
        return nodes.get(0);
    }
}

11.3.4 、最佳实践-数据压缩(生成赫夫曼编码和赫夫曼编码后的数据)

我们已经生成了赫夫曼树, 下面我们继续完成任务

1) 生成赫夫曼树对应的赫夫曼编码 , 如下表: =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011

2) 使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码，将"i like like like java do you like ajava"字符串生成对应的编码数据, 形式如下.

1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

3) 思路：

1、将赫夫曼编码表存放在Map中
2、在生成赫夫曼编码表时需要去拼接路径，定义一个StringBuilder 存储某个叶子节点的路径

4）代码实现

     //为了调用方便重载getCodes方法
    private static Map<Byte,String>getCodes(Node root){
        if (root == null){
            return null;
        }
        //处理root的左子树
        getCodes(root.left,"0",stringBuffer);
        //处理root的右子树
        getCodes(root.right,"1",stringBuffer);
        return huffManCodes;
    }

    //将赫夫曼编码表存放在Map中<Byte ，String>
    static Map<Byte, String> huffManCodes = new HashMap<>();
    //在生成赫夫曼编码表时需要去拼接路径，定义一个StringBuilder 存储某个叶子节点的路径
    static StringBuffer stringBuffer = new StringBuffer();

    /**
     * 将传入的node节点的所有叶子节点的赫夫曼编码得到，并放入到huffmanCodes集合中
     *
     * @param node 传入节点
     * @param code 路径：左子节点是0，右子节点是1
     * @param stringBuffer 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer stringBuffer2 = new StringBuffer(stringBuffer);
        //将传入的code加入stringBuffer2
        stringBuffer2.append(code);
        if (node != null){ //如果node等于空不处理
            //判断当前node是叶子节点还是非叶子节点
            if (node.data == null){  //说明是非叶子节点
                //向左递归处理
                getCodes(node.left,"0",stringBuffer2);
                //向右递归
                getCodes(node.right,"1",stringBuffer2);
            } else {  //说明是叶子节点
                //就表示找到了某个叶子节点的最后
                huffManCode.put(node.data,stringBuffer2.toString());
            }
        }
    }

    /**
     * 编写一个方法，将一个字符串对应的byte[]数组，通过生成的赫夫曼编码，返回一个压缩后的byte[]
     *
     * @param bytes        原始的字符串对应的byte数组
     * @param huffmanCodes 生成的赫夫曼编码map
     * @return 返回赫夫曼编码处理后的byte[]
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //利用huffmanCodes 将 bytes 转成赫夫曼编码对应的字符串
        StringBuffer stringBuffer = new StringBuffer();
        //遍历bytes 数组
        for (byte b : bytes) {
            stringBuffer.append(huffmanCodes.get(b));
        }
        //将对应的字符串转成byte[]

        //统计返回的byte[] huffManCodesBytes 长度
        int length;
        if (stringBuffer.length() % 8 == 0) {
            length = stringBuffer.length() / 8;
        } else {
            length = stringBuffer.length() / 8 + 1;
        }
        //创建存储压缩后的byte数组
        int index = 0; //记录是第几个byte
        byte[] huffManCodesBytes = new byte[length];
        for (int i = 0; i < stringBuffer.length(); i += 8) {  //因为是每八位对应一个byte，步长+8
            String strByte;
            if (i + 8 > stringBuffer.length()) { //不够八位
                strByte = stringBuffer.substring(i);
            } else {
                strByte = stringBuffer.substring(i, i + 8);
            }
            //将strByte转成一个byte数组，放入到huffManCodesBytes
            huffManCodesBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffManCodesBytes;
    }

    /**
     * 使用一个方法，将全面的方法封装起来便于我们调用
     *
     * @param bytes 原始的字符串对应的字节数组
     * @return 经过赫夫曼编码处理后的字节数组，即压缩后的数组
     */
    private static byte[] huffmanZip(byte[] bytes) {
        //1、将需要构建成赫夫曼树的节点放入List数组中
        List<Node> nodes = getNodes(bytes);
        //2、根据传入的节点创建赫夫曼树
        Node huffmanTree = createHuffmanTree(nodes);
        //3、根据赫夫曼树生成对应的赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTree);
        //4、根据生成的赫夫曼编码压缩，压缩后得到的赫夫曼编码字节数组
        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
        //5、将压缩后的编码字节返回即可
        return huffmanCodeBytes;
    }

11.3.5 、最佳实践-数据解压(使用赫夫曼编码解码)

使用赫夫曼编码来解码数据，具体要求是

1) 前面我们得到了赫夫曼编码和对应的编码 byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77 , -57, 6, -24, -14, -117, -4, -60, -90, 28]

2) 现在要求使用赫夫曼编码，进行解码，又重新得到原来的字符串"i like like like java do you like a java"

3) 思路：解码过程，就是编码的一个逆向操作

1、先将赫夫曼的数组重新转成赫夫曼编码对应的二进制字符串
2、将赫夫曼编码对应的二进制字符串--->对照赫夫曼编码--->转成最初的字符串

4）代码实现

    /**
     * 将一个byte转成一个二进制的字符串
     *
     * @param bytes 需要转换的byte
     * @param flag  标志位，用于判断是否需要补高位
     * @return byte对应的二进制字符串，按补码返回的
     */
    private static String byteToBitString(boolean flag, byte bytes) {
        //使用一个变量保存bytes
        int temp = bytes;  //将bytes转成int类型
        //如果是正数还存在一个补高位
        if (flag) {
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);   //返回的是temp对应的二进制的补码
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }    

    /**
     * 编写一个方法，完成对压缩数据的解码
     *
     * @param huffManCodes 赫夫曼编码map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 原来字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffManCodes, byte[] huffmanBytes) {
        //1、先得到huffmanBytes对应的二进制的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //2、将byte[]转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        //把字符串按照指定的赫夫曼编码进行解码,即把赫夫曼编码表进行调换，反向查询
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffManCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        //创建一个集合存放byte
        List<Byte> list = new LinkedList<>();
        //i可以理解成一个索引，在扫描二进制对应的字符串
        for (int i = 0; i < stringBuilder.length();) {
            int count = 0;  //计数器
            boolean flag = true;
            Byte b = null;
            while (flag) {
                //递增取出key
                String key = stringBuilder.substring(i, i + count); //i不动，让count移动
                b = map.get(key);
                if (b == null) { //说明还没有匹配到
                    count++;
                } else {
                    flag = false;
                }
            }
            list.add(b);
            i += count;  //让i直接移动到count的位置
        }
        //当for循环结束后，list中就存放了所有的字符，把list中放入一个byte[]并返回
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }

11.3.6 、最佳实践-文件压缩

我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压，具体要求：给你一个图片文件，要求对其进行无损压缩, 看看压缩效果如何。

1) 思路：读取文件-> 得到赫夫曼编码表 -> 完成压缩

2) 代码实现：

    /**
     * 编写一个方法，将一个文件进行压缩
     *
     * @param srcFile  传入的希望压缩文件的完整的路径
     * @param destFile 压缩后将压缩文件放到哪个目录下
     */
    public static void zipFile(String srcFile, String destFile) {
        //创建输出流
        OutputStream os = null;
        //创建一个文件的输入流，准备读取文件
        FileInputStream is = null;
        //创建一个和文件输出流关联的ObjectOutputStream
        ObjectOutputStream oos = null;
        try {
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一致的byte[]
            byte[] bytes = new byte[is.available()];
            //读取文件
            is.read(bytes);
            //直接对源文件进行压缩，得到赫夫曼对应的字节数组
            byte[] huffmanBytes = huffmanZip(bytes);
            //创建文件的输出流准备存放压缩文件
            os = new FileOutputStream(destFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //这里我们以对象流的方式写入赫夫曼的编码，目的是为了恢复源文件时使用
            oos.writeObject(huffManCodes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                is.close();
                os.close();
                oos.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }

11.3.7 、最佳实践-文件解压(文件恢复)

具体要求：将前面压缩的文件，重新恢复成原来的文件。

1) 思路：读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)

2) 代码实现：

/**
     * 编写一个方法，完成对压缩文件的解压
     *
     * @param zipFile 准备解压的文件
     * @param dstFile 将文件解压到哪个位置
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //定义文件的输出流
        OutputStream os = null;
        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和is关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte[] huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //解码
            byte[] bytes = decode(huffmanCodes, huffmanBytes);
            //将bytes数组写入到目标文件
            os = new FileOutputStream(dstFile);
            //写数据到dstFile文件中
            os.write(bytes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }

11.3.8 、代码汇总，把前面所有的方法放在一起

/**
 * description
 * 赫夫曼编码的代码是实现
 *
 * @author xujicheng
 * @since 2022年12月06日 17:14
 */
public class HuffManCode {
    public static void main(String[] args) {
        String zipFile = "D://001-file//dst.zip";
        String dstFile = "D://001-file";
        unZipFile(zipFile, dstFile);
        System.out.println("解压成功");
    }

    /**
     * 编写一个方法，将一个文件进行压缩
     *
     * @param srcFile  传入的希望压缩文件的完整的路径
     * @param destFile 压缩后将压缩文件放到哪个目录下
     */
    public static void zipFile(String srcFile, String destFile) {
        //创建输出流
        OutputStream os = null;
        //创建一个文件的输入流，准备读取文件
        FileInputStream is = null;
        //创建一个和文件输出流关联的ObjectOutputStream
        ObjectOutputStream oos = null;
        try {
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一致的byte[]
            byte[] bytes = new byte[is.available()];
            //读取文件
            is.read(bytes);
            //直接对源文件进行压缩，得到赫夫曼对应的字节数组
            byte[] huffmanBytes = huffmanZip(bytes);
            //创建文件的输出流准备存放压缩文件
            os = new FileOutputStream(destFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //这里我们以对象流的方式写入赫夫曼的编码，目的是为了恢复源文件时使用
            oos.writeObject(huffManCodes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                is.close();
                os.close();
                oos.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }

    /**
     * 编写一个方法，完成对压缩文件的解压
     *
     * @param zipFile 准备解压的文件
     * @param dstFile 将文件解压到哪个位置
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //定义文件的输出流
        OutputStream os = null;
        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和is关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte[] huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //解码
            byte[] bytes = decode(huffmanCodes, huffmanBytes);
            //将bytes数组写入到目标文件
            os = new FileOutputStream(dstFile);
            //写数据到dstFile文件中
            os.write(bytes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }

    /**
     * 编写一个方法，完成对压缩数据的解码
     *
     * @param huffManCodes 赫夫曼编码map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 原来字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffManCodes, byte[] huffmanBytes) {
        //1、先得到huffmanBytes对应的二进制的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //2、将byte[]转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        //把字符串按照指定的赫夫曼编码进行解码,即把赫夫曼编码表进行调换，反向查询
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffManCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        //创建一个集合存放byte
        List<Byte> list = new LinkedList<>();
        //i可以理解成一个索引，在扫描二进制对应的字符串
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 0;  //计数器
            boolean flag = true;
            Byte b = null;
            while (flag) {
                //递增取出key
                String key = stringBuilder.substring(i, i + count); //i不动，让count移动
                b = map.get(key);
                if (b == null) { //说明还没有匹配到
                    count++;
                } else {
                    flag = false;
                }
            }
            list.add(b);
            i += count;  //让i直接移动到count的位置
        }
        //当for循环结束后，list中就存放了所有的字符，把list中放入一个byte[]并返回
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }

    /**
     * 将一个byte转成一个二进制的字符串
     *
     * @param bytes 需要转换的byte
     * @param flag  标志位，用于判断是否需要补高位,若是最后一个字节，无需补高位
     * @return byte对应的二进制字符串，按补码返回的
     */
    private static String byteToBitString(boolean flag, byte bytes) {
        //使用一个变量保存bytes
        int temp = bytes;  //将bytes转成int类型
        //如果是正数还存在一个补高位
        if (flag) {
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);   //返回的是temp对应的二进制的补码
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    /**
     * 使用一个方法，将全面的方法封装起来便于我们调用
     *
     * @param bytes 原始的字符串对应的字节数组
     * @return 经过赫夫曼编码处理后的字节数组，即压缩后的数组
     */
    private static byte[] huffmanZip(byte[] bytes) {
        //1、将需要构建成赫夫曼树的节点放入List数组中
        List<Node> nodes = getNodes(bytes);
        //2、根据传入的节点创建赫夫曼树
        Node huffmanTree = createHuffmanTree(nodes);
        //3、根据赫夫曼树生成对应的赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTree);
        //4、根据生成的赫夫曼编码压缩，压缩后得到的赫夫曼编码字节数组
        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
        //5、将压缩后的编码字节返回即可
        return huffmanCodeBytes;
    }

    /**
     * 编写一个方法，将一个字符串对应的byte[]数组，通过生成的赫夫曼编码，返回一个压缩后的byte[]
     *
     * @param bytes        原始的字符串对应的byte数组
     * @param huffmanCodes 生成的赫夫曼编码map
     * @return 返回赫夫曼编码处理后的byte[]
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //利用huffmanCodes 将 bytes 转成赫夫曼编码对应的字符串
        StringBuffer stringBuffer = new StringBuffer();
        //遍历bytes 数组
        for (byte b : bytes) {
            stringBuffer.append(huffmanCodes.get(b));
        }
        //将对应的字符串转成byte[]

        //统计返回的byte[] huffManCodesBytes 长度
        int length;
        if (stringBuffer.length() % 8 == 0) {
            length = stringBuffer.length() / 8;
        } else {
            length = stringBuffer.length() / 8 + 1;
        }
        //创建存储压缩后的byte数组
        int index = 0; //记录是第几个byte
        byte[] huffManCodesBytes = new byte[length];
        for (int i = 0; i < stringBuffer.length(); i += 8) {  //因为是每八位对应一个byte，步长+8
            String strByte;
            if (i + 8 > stringBuffer.length()) { //不够八位
                strByte = stringBuffer.substring(i);
            } else {
                strByte = stringBuffer.substring(i, i + 8);
            }
            //将strByte转成一个byte数组，放入到huffManCodesBytes
            huffManCodesBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffManCodesBytes;
    }

    //前序遍历的方法
    private static void preorder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("赫夫曼树为空");
        }
    }

    //为了调用方便重载getCodes方法
    private static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //处理root的左子树
        getCodes(root.left, "0", stringBuffer);
        //处理root的右子树
        getCodes(root.right, "1", stringBuffer);
        return huffManCodes;
    }

    //将赫夫曼编码表存放在Map中<Byte ，String>
    static Map<Byte, String> huffManCodes = new HashMap<>();
    //在生成赫夫曼编码表时需要去拼接路径，定义一个StringBuilder 存储某个叶子节点的路径
    static StringBuffer stringBuffer = new StringBuffer();

    /**
     * 将传入的node节点的所有叶子节点的赫夫曼编码得到，并放入到huffmanCodes集合中
     *
     * @param node         传入节点
     * @param code         路径：左子节点是0，右子节点是1
     * @param stringBuffer 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer stringBuffer2 = new StringBuffer(stringBuffer);
        //将传入的code加入stringBuffer2
        stringBuffer2.append(code);
        if (node != null) { //如果node等于空不处理
            //判断当前node是叶子节点还是非叶子节点
            if (node.data == null) {  //说明是非叶子节点
                //向左递归处理
                getCodes(node.left, "0", stringBuffer2);
                //向右递归
                getCodes(node.right, "1", stringBuffer2);
            } else {  //说明是叶子节点
                //就表示找到了某个叶子节点的最后
                huffManCodes.put(node.data, stringBuffer2.toString());
            }
        }
    }

    /**
     * 将左边构建赫夫曼树的Node 节点放到List
     *
     * @param bytes 需要构建的字节数
     * @return 返回的List形式 -->[Node[date=97，weight = 5 ]，Node[data = 32 weight = 9]]
     */
    private static List<Node> getNodes(byte[] bytes) {
        //创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<Node>();
        //存储每个byte出现的次数，使用map来统计,key为数据本身，Integer是次数
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) { //说明Map还没有这个字符数据，是第一次放入
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        //把每个键值对转成Node对象并加入到nodes集合
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    //通过一个List创建对应的赫夫曼树
    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //排序,从小到大
            Collections.sort(nodes);
            //取出第一颗最小的二叉树
            Node leftNode = nodes.get(0);
            //取出第二颗最小的二叉树
            Node rightNode = nodes.get(1);
            //创建一颗新的二叉树，它的根节点没有data，只有权值
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //将已经处理的两棵二叉树从nodes中删除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将新的二叉树加入到nodes
            nodes.add(parent);
        }
        //返回的nodes最后的节点，就是赫夫曼树的root节点
        return nodes.get(0);
    }
}

11.3.9、赫夫曼编码压缩文件注意事项

1) 如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件[举例压一个.ppt]
2) 赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件) [举例压一个.xml 文件]
3) 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显

11.4、二叉排序树

11.4.1、先看一个需求

给你一个数列 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数据的查询和添加

11.4.2 、解决方案分析

使用数组数组未排序

优点：直接在数组尾添加，速度快。缺点：查找速度慢. [示意图] 数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。

使用链式存储-链表

不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动

使用二叉排序树

11.4.3 、二叉排序树介绍

二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：

11.4.4 、二叉排序树创建和遍历

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ，创建成对应的二叉排序树为 :

代码实现如下：

/**
 * description
 * 节点
 *
 * @author xujicheng
 * @since 2022年12月08日 9:28
 */
public class Node {

    int value;  //权值

    Node left;  //左子节点

    Node right; //右子节点

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    /**
     * 添加节点的方法，使用递归的方式添加节点，需要满足二叉排序树的要求
     *
     * @param node 需要添加的节点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //判断传入节点的值和当前子树的根节点的值的关系
        if (node.value < this.value) {
            if (this.left == null) { //如果当前节点左子节点为空，直接挂在左子节点即可
                this.left = node;
            } else {
                this.left.add(node);  //递归的向左子树添加
            }
        } else {  //添加的节点的值大于当前节点的值
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);  //递归的向右子树添加
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}

/**
 * description
 * 二叉排序树
 *
 * @author xujicheng
 * @since 2022年12月08日 9:39
 */
public class BinarySortTree {

    private Node root; //根节点

    /**
     * 添加节点的方法
     *
     * @param node 需要加入的节点
     */
    public void add(Node node) {
        if (root == null){
            root = node;  //如果root为空则直接让root指向node
        } else {
            root.add(node);
        }
    }
    //中序遍历
    public void infixOrder(){
        if (root != null){
            root.infixOrder();
        }else {
            System.out.println("当前二叉排序树为空，不能遍历");
        }
    }
}

/**
 * description
 * 二叉排序数代码实现
 *
 * @author xujicheng
 * @since 2022年12月08日 9:27
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BinarySortTree binarySortTree = new BinarySortTree();
        //循环的添加节点到二叉排序树
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        //中序遍历二叉排序树
        System.out.println("中序遍历二叉排序树");
        binarySortTree.infixOrder();
    }
}

11.4.5 、二叉排序树的删除

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑

1) 删除叶子节点 (比如：2, 5, 9, 12)
2) 删除只有一颗子树的节点 (比如：1)
3) 删除有两颗子树的节点. (比如：7, 3，10 )
4) 操作的思路分析

对删除节点的各种情况的思路分析：

第一种情况：删除叶子节点
- 思路
- 1、需要先去找到要删除的节点 targetNode
- 2、找到targetNode 的父节点 parent
- 3、确定 targetNode 是 parent 的左子结点还是右子结点
- 4、根据前面的情况来对应删除
  - 左子结点 parent.left = null 右子结点 parent.right = null;
第二种情况: 删除只有一颗子树的节点
- 思路
- 1、(1) 需求先去找到要删除的结点 targetNode
- 2、找到 targetNode 的父结点 parent
- 3、确定 targetNode 的子结点是左子结点还是右子结点
- 4、targetNode 是 parent 的左子结点还是右子结点
- 5、如果 targetNode 有左子结点
  - 5.1、如果 targetNode 是 parent 的左子结点
    parent.left = targetNode.left;
  - 5.2、如果 targetNode 是 parent 的右子结点
    parent.right = targetNode.left;
- 6、如果 targetNode 有右子结点
  - 6.1、如果 targetNode 是 parent 的左子结点
    parent.left = targetNode.right;
  - 6.2、如果 targetNode 是 parent 的右子结点
    parent.right = targetNode.right；
情况三：删除有两颗子树的节点.
- 思路：
- 1、需要先去找到要删除的结点 targetNode
- 2、找到 targetNode 的父结点 parent
- 3、从 targetNode 的右子树找到最小的结点
- 4、用一个临时变量，将最小结点的值保存 temp
- 5、删除该最小结点
- 6、targetNode.value = temp

11.4.6 、二叉排序树删除结点的代码实现

在Node节点中加入以下两个方法：
    /**
     * 查找要删除的节点
     *
     * @param value 希望删除的结点的值
     * @return 如果找到返回该结点，否则返回 null
     */
    public Node search(int value) {
        if (value == this.value) { //找到就是该结点
            return this;
        } else if (value < this.value) {//如果查找的值小于当前结点，向左子树递归查找//如果左子结点为空
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else { //如果查找的值不小于当前结点，向右子树递归查找
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    /**
     * 查找要删除节点的父节点
     *
     * @param value 需要查找的值
     * @return 要删除的节点的父节点，如果没有就返回null
     */
    public Node searchParent(int value) {
        //如果当前结点就是要删除的结点的父结点，就返回
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value)) {
            return this;
        } else {
            //如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value); //向左子树递归查找
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value); //向右子树递归查找
            } else {
                return null; // 没有找到父结点
            }
        }
    }

在BinarySortTree中加入对应的具体实现方法
/**
     * 查找要删除的节点
     *
     * @param value 希望删除的节点的值
     * @return 如果找到返回该节点，否则返回null
     */
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    /**
     * 查找父节点
     *
     * @param value 需要查找的值
     * @return 要删除的节点的父节点，如果没有就返回null
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    /**
     * 删除节点
     *
     * @param value 需要删除的节点的值
     */
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //需要先找到要删除的节点 targetNode
            Node targetNode = search(value);
            //如果没有找到要删除的节点就无需向下执行
            if (targetNode == null) {
                return;
            }
            //如果我们发现当前这颗二叉树排序树只有一个节点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //去找到 targetNode 的父结点
            Node parent = searchParent(value);
            //如果要删除的结点是叶子结点
            if (targetNode.left == null && targetNode.right == null) {
                //判断 targetNode 是父结点的左子结点，还是右子结点
                if (parent.left != null && parent.left.value == value) { //是左子结点
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {//是由子结点parent.right = null;
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点int minVal = delRightTreeMin(targetNode.right);
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else { // 删除只有一颗子树的结点
                //如果要删除的结点有左子结点
                if (targetNode.left != null) {
                    if (parent != null) {
                        //如果 targetNode 是 parent 的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else { // targetNode 是 parent 的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else { //如果要删除的结点有右子结点
                    if (parent != null) {
                        //如果 targetNode 是 parent 的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else { //如果 targetNode 是 parent 的右子结点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

11.4.7 、课后练习：完成老师代码，并使用第二种方式来解决

如果我们从左子树找到最大的结点，然后前面的思路完成

    //作业
    //编写方法
    //1.返回以node为根节点的二叉排序树的最大节点的值
    //2.删除以node为根节点的二叉排序树的最大节点
    public int delLeftTreeMin(Node node){
        Node target = node;
        //循环的查找右节点，就会找到最大值
        while (target.right != null){
            target = target.right;
        }
        //这时，target就指向了最小节点
        //删除最小节点
        delNode(target.value);
        return target.value;
}

//这一段在delNode方法里
else if(targetNode.left != null && targetNode.right != null){//删除左右两边都有子树的节点
                //int minValue = delRightTreeMin(targetNode.right);
                int minValue = delLeftTreeMin(targetNode.left);//这里解释一下，目标节点的右子树的最小节点比目标节点的左子树里的所有节点都大，所以向右找，就找一个最小的(老师代码的含义),向左找左子树那就要找最大的，说的通俗一点就是，矮个子里挑高个，高个子里挑矮个
                targetNode.value = minValue;
}

11.4.8、完整代码整合

/**
 * description
 * 节点
 *
 * @author xujicheng
 * @since 2022年12月08日 9:28
 */
public class Node {

    int value;  //权值

    Node left;  //左子节点

    Node right; //右子节点

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    /**
     * 查找要删除的节点
     *
     * @param value 希望删除的结点的值
     * @return 如果找到返回该结点，否则返回 null
     */
    public Node search(int value) {
        if (value == this.value) { //找到就是该结点
            return this;
        } else if (value < this.value) {//如果查找的值小于当前结点，向左子树递归查找//如果左子结点为空
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else { //如果查找的值不小于当前结点，向右子树递归查找
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }



    /**
     * 查找要删除节点的父节点
     *
     * @param value 需要查找的值
     * @return 要删除的节点的父节点，如果没有就返回null
     */
    public Node searchParent(int value) {
        //如果当前结点就是要删除的结点的父结点，就返回
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value)) {
            return this;
        } else {
            //如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value); //向左子树递归查找
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value); //向右子树递归查找
            } else {
                return null; // 没有找到父结点
            }
        }
    }

    /**
     * 添加节点的方法，使用递归的方式添加节点，需要满足二叉排序树的要求
     *
     * @param node 需要添加的节点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //判断传入节点的值和当前子树的根节点的值的关系
        if (node.value < this.value) {
            if (this.left == null) { //如果当前节点左子节点为空，直接挂在左子节点即可
                this.left = node;
            } else {
                this.left.add(node);  //递归的向左子树添加
            }
        } else {  //添加的节点的值大于当前节点的值
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);  //递归的向右子树添加
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}

/**
 * description
 * 二叉排序树
 *
 * @author xujicheng
 * @since 2022年12月08日 9:39
 */
public class BinarySortTree {

    private Node root; //根节点

    /**
     * 查找要删除的节点
     *
     * @param value 希望删除的节点的值
     * @return 如果找到返回该节点，否则返回null
     */
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    /**
     * 查找父节点
     *
     * @param value 需要查找的值
     * @return 要删除的节点的父节点，如果没有就返回null
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    /**
     * 课后作业
     *
     * @param node 传入的结点(当做二叉排序树的根结点)
     * @return 返回的 以 node 为根结点的二叉排序树的最小结点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //循环的查找左子节点，就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这时 target 就指向了最小结点,删除最小结点
        delNode(target.value);
        return target.value;
    }

    /**
     * 删除节点
     *
     * @param value 需要删除的节点的值
     */
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //需要先找到要删除的节点 targetNode
            Node targetNode = search(value);
            //如果没有找到要删除的节点就无需向下执行
            if (targetNode == null) {
                return;
            }
            //如果我们发现当前这颗二叉树排序树只有一个节点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //去找到 targetNode 的父结点
            Node parent = searchParent(value);
            //如果要删除的结点是叶子结点
            if (targetNode.left == null && targetNode.right == null) {
                //判断 targetNode 是父结点的左子结点，还是右子结点
                if (parent.left != null && parent.left.value == value) { //是左子结点
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {//是由子结点parent.right = null;
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点int minVal = delRightTreeMin(targetNode.right);
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else { // 删除只有一颗子树的结点
                //如果要删除的结点有左子结点
                if (targetNode.left != null) {
                    if (parent != null) {
                        //如果 targetNode 是 parent 的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else { // targetNode 是 parent 的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else { //如果要删除的结点有右子结点
                    if (parent != null) {
                        //如果 targetNode 是 parent 的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else { //如果 targetNode 是 parent 的右子结点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    /**
     * 添加节点的方法
     *
     * @param node 需要加入的节点
     */
    public void add(Node node) {
        if (root == null) {
            root = node;  //如果root为空则直接让root指向node
        } else {
            root.add(node);
        }
    }

    //中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("当前二叉排序树为空，不能遍历");
        }
    }
}

//测试部分省略

11.5 、平衡二叉树(AVL 树)

11.5.1、看一个案例(说明二叉排序树可能的问题)

给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在.

左边 BST 存在的问题分析:
- 1) 左子树全部为空，从形式上看，更像一个单链表.
- 2) 插入速度没有影响
- 3) 查询速度明显降低(因为需要依次比较), 不能发挥 BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
- 的优势，因为每次还需要比较左子树，其查询速度比单链表还慢

11.5.2、基本介绍

1) 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树，可以保证查询效率较高。

2) 具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

3) 举例说明, 看看下面哪些 AVL 树

11.5.3、二平衡树的高度求解

在Node节点中加入以下方法
    //返回右子树的高度
    public int rightHeight() {
        if (right == null){
            return 0;
        }
        return right.height();
    }

    //返回以该节点为根节点的树的高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

/**
 * description
 * 二叉平衡树的高度求解测试
 *
 * @author xujicheng
 * @since 2022年12月09日 9:47
 */
public class AvlTreeDemo {
    public static void main(String[] args) {
        int[] arr = {4, 3, 6, 5, 7, 8};
        //创建一个AVLTree对象
        AvlTree avlTree = new AvlTree();
        //添加节点
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(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());
    }
}

代码说明：Node节点和二叉排序树的代码我可以复用，直接添加相应求高度解的方法即可

这里我们经过测试可以得出在二叉平衡树之前左子树和右子树的高度为

11.5.4、应用案例-单旋转(左旋转)

1) 要求: 给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}

2) 思路分析(示意图)

3) 代码实现

    在Node节点类中加入左旋转的方法，并在加入节点的方法中加入左旋转的判断逻辑
    //左旋转的方法
    private void leftRotate() {
        //创建新的节点，以当前根节点的值创建的
        Node node = new Node(value);
        //把新的节点的左子树，设置成当前节点的左子树
        node.left = left;
        //把新的节点的右子树，设置成当前节点的右子树的左子树
        node.right = right.left;
        //把当前节点的值换成右子节点的值
        value = right.value;
        //把当前节点的右子树设置成右子树的右子树
        right = right.right;
        //把当前节点的左子树设置成新的节点
        left = node;
    }

    /**
     * 添加节点的方法，使用递归的方式添加节点，需要满足二叉排序树的要求
     *
     * @param node 需要添加的节点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //判断传入节点的值和当前子树的根节点的值的关系
        if (node.value < this.value) {
            if (this.left == null) { //如果当前节点左子节点为空，直接挂在左子节点即可
                this.left = node;
            } else {
                this.left.add(node);  //递归的向左子树添加
            }
        } else {  //添加的节点的值大于当前节点的值
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);  //递归的向右子树添加
            }
        }

        //当添加完一个节点后，如果 (右子树的高度 - 左子树的高度) > 1，就将该树左旋转
        if (rightHeight() - leftHeight() > 1) {
            leftRotate();  //左旋转
        }
    }

在经过左旋转之后的二叉树高度为

11.5.5、应用案例-单旋转(右旋转)

1) 要求: 给你一个数列，创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}

2)右旋转的思路分析

3）代码实现

    在Node节点类中加入右旋转的方法，并在加入节点的方法中加入左旋转的判断逻辑
        //右旋转的方法
           private void rightRotate() {
        //创建新的节点，以当前根节点的值创建的
        Node node = new Node(value);
        //把新的节点的右子树，设置成当前节点的右子树
        node.right = right;
        //把新的节点的左子树，设置成当前节点的左子树的右子树
        node.left = left.right;
        //把当前节点的值换成左子节点的值
        value = left.value;
        //把当前节点的做指数设置成左子树的左子树
        left = left.left;
        //把当前节点的右子树设置成新的节点
        right = node;
    }

    /**
     * 添加节点的方法，使用递归的方式添加节点，需要满足二叉排序树的要求
     *
     * @param node 需要添加的节点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //判断传入节点的值和当前子树的根节点的值的关系
        if (node.value < this.value) {
            if (this.left == null) { //如果当前节点左子节点为空，直接挂在左子节点即可
                this.left = node;
            } else {
                this.left.add(node);  //递归的向左子树添加
            }
        } else {  //添加的节点的值大于当前节点的值
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);  //递归的向右子树添加
            }
        }

        //当添加完一个节点后，如果 (右子树的高度 - 左子树的高度) > 1，就将该树左旋转
        if (rightHeight() - leftHeight() > 1) {
            leftRotate();  //左旋转
        }
        //当添加完一个节点后，如果 (左子树的高度 - 右子树的高度) > 1，就将该树右旋转
        if (leftHeight() - rightHeight() > 1) {
            rightRotate();
        }
    }

/**
 * description
 * 测试右旋转
 *
 * @author xujicheng
 * @since 2022年12月09日 9:47
 */
public class AvlTreeDemo {
    public static void main(String[] args) {
        int[] arr = {10, 12, 8, 9, 7, 6};
        //创建一个AVLTree对象
        AvlTree avlTree = new AvlTree();
        //添加节点
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(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());
    }
}

在经过右旋转之后的二叉树高度为

11.5.6、应用案例-双旋转

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列 int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL 树. int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL 树

1) 问题分析

2) 解决思路分析

当符号右旋转的条件时
如果它的左子树的右子树高度大于它的左子树的高度
先对当前这个结点的左节点进行左旋转
在对当前结点进行右旋转的操作即可

3) 代码实现[AVL 树的汇总代码(完整代码)]

/**
 * description
 * 节点复用
 *
 * @author xujicheng
 * @since 2022年12月08日 9:28
 */
public class Node {

    int value;  //权值

    Node left;  //左子节点

    Node right; //右子节点

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //返回左子树的高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    //返回右子树的高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }

    //返回以该节点为根节点的树的高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    //左旋转的方法
    private void leftRotate() {
        //创建新的节点，以当前根节点的值创建的
        Node node = new Node(value);
        //把新的节点的左子树，设置成当前节点的左子树
        node.left = left;
        //把新的节点的右子树，设置成当前节点的右子树的左子树
        node.right = right.left;
        //把当前节点的值换成右子节点的值
        value = right.value;
        //把当前节点的右子树设置成右子树的右子树
        right = right.right;
        //把当前节点的左子树设置成新的节点
        left = node;
    }

    //右旋转的方法
    private void rightRotate() {
        //创建新的节点，以当前根节点的值创建的
        Node node = new Node(value);
        //把新的节点的右子树，设置成当前节点的右子树
        node.right = right;
        //把新的节点的左子树，设置成当前节点的左子树的右子树
        node.left = left.right;
        //把当前节点的值换成左子节点的值
        value = left.value;
        //把当前节点的做指数设置成左子树的左子树
        left = left.left;
        //把当前节点的右子树设置成新的节点
        right = node;
    }

    /**
     * 查找要删除的节点
     *
     * @param value 希望删除的结点的值
     * @return 如果找到返回该结点，否则返回 null
     */
    public Node search(int value) {
        if (value == this.value) { //找到就是该结点
            return this;
        } else if (value < this.value) {//如果查找的值小于当前结点，向左子树递归查找//如果左子结点为空
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else { //如果查找的值不小于当前结点，向右子树递归查找
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }


    /**
     * 查找要删除节点的父节点
     *
     * @param value 需要查找的值
     * @return 要删除的节点的父节点，如果没有就返回null
     */
    public Node searchParent(int value) {
        //如果当前结点就是要删除的结点的父结点，就返回
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value)) {
            return this;
        } else {
            //如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value); //向左子树递归查找
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value); //向右子树递归查找
            } else {
                return null; // 没有找到父结点
            }
        }
    }

    /**
     * 添加节点的方法，使用递归的方式添加节点，需要满足二叉排序树的要求
     *
     * @param node 需要添加的节点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //判断传入节点的值和当前子树的根节点的值的关系
        if (node.value < this.value) {
            if (this.left == null) { //如果当前节点左子节点为空，直接挂在左子节点即可
                this.left = node;
            } else {
                this.left.add(node);  //递归的向左子树添加
            }
        } else {  //添加的节点的值大于当前节点的值
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);  //递归的向右子树添加
            }
        }

        //当添加完一个节点后，如果 (右子树的高度 - 左子树的高度) > 1，就将该树左旋转
        if (rightHeight() - leftHeight() > 1) {
            //如果它的右子树的左子树的高度大于它的右子树的高度
            if (right != null && right.leftHeight() > right.rightHeight()) {
                //先进行右旋转，在进行左旋转
                right.rightRotate();
                //再对当前节点进行左旋转
                leftRotate();
            } else {
                //直接进行左旋转
                leftRotate();
            }
            return;
        }
        //当添加完一个节点后，如果 (左子树的高度 - 右子树的高度) > 1，就将该树右旋转
        if (leftHeight() - rightHeight() > 1) {
            //如果它的左子树的右子树的高度大于它的左子树的高度
            if (left != null && left.rightHeight() > left.leftHeight()) {
                //先进行左旋转，在进行右旋转
                left.leftRotate();
                //再对当前节点进行右旋转
                rightRotate();
            } else {
                //直接进行右旋转
                rightRotate();
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}

/**
 * description
 * 二叉平衡树,二叉排序树的代码复用
 *
 * @author xujicheng
 * @since 2022年12月09日 9:56
 */
public class AvlTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    /**
     * 查找要删除的节点
     *
     * @param value 希望删除的节点的值
     * @return 如果找到返回该节点，否则返回null
     */
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    /**
     * 查找父节点
     *
     * @param value 需要查找的值
     * @return 要删除的节点的父节点，如果没有就返回null
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    /**
     * 课后作业
     *
     * @param node 传入的结点(当做二叉排序树的根结点)
     * @return 返回的 以 node 为根结点的二叉排序树的最小结点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //循环的查找左子节点，就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这时 target 就指向了最小结点,删除最小结点
        delNode(target.value);
        return target.value;
    }

    /**
     * 删除节点
     *
     * @param value 需要删除的节点的值
     */
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //需要先找到要删除的节点 targetNode
            Node targetNode = search(value);
            //如果没有找到要删除的节点就无需向下执行
            if (targetNode == null) {
                return;
            }
            //如果我们发现当前这颗二叉树排序树只有一个节点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //去找到 targetNode 的父结点
            Node parent = searchParent(value);
            //如果要删除的结点是叶子结点
            if (targetNode.left == null && targetNode.right == null) {
                //判断 targetNode 是父结点的左子结点，还是右子结点
                if (parent.left != null && parent.left.value == value) { //是左子结点
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {//是由子结点parent.right = null;
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点int minVal = delRightTreeMin(targetNode.right);
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else { // 删除只有一颗子树的结点
                //如果要删除的结点有左子结点
                if (targetNode.left != null) {
                    if (parent != null) {
                        //如果 targetNode 是 parent 的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else { // targetNode 是 parent 的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else { //如果要删除的结点有右子结点
                    if (parent != null) {
                        //如果 targetNode 是 parent 的左子结点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else { //如果 targetNode 是 parent 的右子结点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    /**
     * 添加节点的方法
     *
     * @param node 需要加入的节点
     */
    public void add(Node node) {
        if (root == null) {
            root = node;  //如果root为空则直接让root指向node
        } else {
            root.add(node);
        }
    }

    //中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("当前二叉排序树为空，不能遍历");
        }
    }
}


/**
 * description
 * 二叉平衡树的左旋转代码实现
 *
 * @author xujicheng
 * @since 2022年12月09日 9:47
 */
public class AvlTreeDemo {
    public static void main(String[] args) {
        int[] arr = {10, 11, 7，6，8，9};
        //创建一个AVLTree对象
        AvlTree avlTree = new AvlTree();
        //添加节点
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(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());
        System.out.println("当前的根节点=" + avlTree.getRoot());
        System.out.println("根节点的左子节点" + avlTree.getRoot().left);
        System.out.println("根节点的右子节点" + avlTree.getRoot().right);
    }
}

经过双旋转的处理后的二叉树就变成了平衡二叉树

数据结构和算法的学习笔记（第十部分）