树结构应用

一、堆排序

1、堆排序概述

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好、平均时间复杂度均为 O(nlogn)，它也是不稳定排序
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
结点的左孩子的值和右孩子的值的大小关系无要求

2、堆排序思路

将待排序序列构造成一个大顶堆（数组形式）
整个序列的最大值就是堆顶的根节点
将其与末尾元素进行交换，此时末尾就为最大值
然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n-1 个元素的次小值。如此反复执行，便能得到一个有序序列了

3、堆排序代码实现

java

package work.rexhao.tree;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author 王铭颢
 * @Date 2022/7/5 21:36
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] num = new int[]{3, 2, 4, 1, 5};
        System.out.println(Arrays.toString(num));
        heapSort(num, num.length);
        System.out.println(Arrays.toString(num));
    }

    /**
     * 维护大顶堆
     *
     * @param num   数组
     * @param len   数组长度
     * @param index 待维护元素的下表
     */
    public static void heapify(int[] num, int len, int index) {
        int max = index;
        // 找到最大值
        int leftSon = index * 2 + 1;
        int rightSon = index * 2 + 2;
        if (leftSon < len && num[max] < num[leftSon]) {
            max = leftSon;
        }
        if (rightSon < len && num[max] < num[rightSon]) {
            max = rightSon;
        }
        // 最大的不是父节点 => 交换
        if (max != index) {
            // 1.交换
            int temp = num[max];
            num[max] = num[index];
            num[index] = temp;
            // 2.继续维护下面的子堆
            heapify(num, len, max);
        }

    }


    /**
     * 堆排序入口
     *
     * @param num 待排序数组
     * @param len 数组长度
     */
    public static void heapSort(int[] num, int len) {
        // 建堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(num, len, i);
        }
        // 交换首尾元素
        for (int i = len - 1; i > 0; i--) {
            int temp = num[i];
            num[i] = num[0];
            num[0] = temp;
            heapify(num, i, 0);
        }
    }
}

二、赫夫曼树

1、赫夫曼树基本介绍

赫夫曼树(Hufriman Tree)：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树

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

2、赫夫曼树的概念

1）路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。

通路中分支的数目称为路径长度。

若规定根结点的层数为1，则从根结点到第工层结点的路径长度为L-1

2）结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积

3）树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL(weighted path length)

权值越大的结点离根结点越近的二叉树才是最优二叉树。

4）WPL

WPL 最小的就是赫夫曼树

3、赫夫曼树的代码实现

java

package work.rexhao.huffmantree;

import org.jetbrains.annotations.NotNull;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 哈夫曼树的生成
 *
 * @author 王铭颢
 * @Date 2022/7/6 12:49
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int num[] = {13, 7, 8, 3, 29, 6, 1};
        initHuffmanTree(num);

    }

    public static void initHuffmanTree(int[] num) {
        ArrayList<TreeNode> tnodes = new ArrayList<>();
        for (int i : num) {
            tnodes.add(new TreeNode(i));
        }
        while (tnodes.size() != 1) {
            Collections.sort(tnodes);
            TreeNode leftNode = tnodes.get(0);
            TreeNode rightNode = tnodes.get(1);
            tnodes.add(new TreeNode(leftNode.getData() + rightNode.getData(), leftNode, rightNode));
            tnodes.remove(leftNode);
            tnodes.remove(rightNode);
            Collections.sort(tnodes);
        }
        preOrder(tnodes.get(0));


    }

    /**
     * 先序遍历
     */
    public static void preOrder(TreeNode tn) {
        if (tn != null) {
            System.out.print(tn.getData() + " ");
            preOrder(tn.leftNode);
            preOrder(tn.rightNode);
        }
    }


}

/**
 * 二叉树的节点
 */
class TreeNode implements Comparable<TreeNode> {
    private int data;
    TreeNode leftNode;
    TreeNode rightNode;

    TreeNode(int data) {
        this.data = data;
    }

    public TreeNode(int data, TreeNode leftNode, TreeNode rightNode) {
        this.data = data;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    @Override
    public int compareTo(@NotNull TreeNode o) {
        return this.data - o.data;
    }
}

三、赫夫曼编码

1、赫夫曼编码的基本介绍

赫夫曼编码是赫哈大曼树在电讯通信中的经典的应用之一
赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%~-90%之间
赫夫曼码是可变字长编码(VLC)的一种
Huffman于1952年提出一种编码方法，称之为最佳编码
宇符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码，即不能匹配到重复的编码

2、赫夫曼编码的注意事项

赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl是一样的，都是最小的，最后生成的赫夫曼编码的长度是一样
如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化，比如视频、ppt 等等文件
赫夫曼编码是按字节来处理的，因此可以处理所有的文件（二进制文件、文本文件）
如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显

3、代码实现

未解决的Bug：
哈夫曼字节编码8个二进制数一组。对于最后一组，若0开头，转换后因为不去补零，丢失前面的0；如果补零，最后一组不一定是8位，不能补零。我的做法是：将最后一组后面补零至8位，但是会造成解码后产生多余字符。

java

package work.rexhao.huffmantree;

import org.jetbrains.annotations.NotNull;

import java.util.*;

/**
 * 哈夫曼编码与解码
 *
 * @author 王铭颢
 * @Date 2022/7/10 16:08
 */
public class HuffmanCode {
    // 存储哈夫曼编码表
    static Map<Byte, String> HuffmanCodes = new HashMap<>();

    public static void main(String[] args) {
        String str1 = "i like java java java do you like java?";
        System.out.println("str1:" + str1);
        byte[] huffmanBytes = huffmanZip(str1.getBytes());
        System.out.println("huffmanBytes:" + Arrays.toString(huffmanBytes));
        String str2 = huffmanUnzip(huffmanBytes);
        System.out.println("str2:" + str2);
    }

    /**
     * 哈夫曼解码
     *
     * @param huffmanBytes 哈夫曼编码
     * @return 解码后字符串
     */
    private static String huffmanUnzip(byte[] huffmanBytes) {
        StringBuilder code = new StringBuilder();
        for (byte b : huffmanBytes) {
            code.append(Integer.toBinaryString(b | 256).substring(
                    Integer.toBinaryString(b | 256).length() - 8));
        }
        Map<String, Byte> unzipCodes = new HashMap<>();
        for (Map.Entry<Byte, String> entry : HuffmanCodes.entrySet()) {
            unzipCodes.put(entry.getValue(), entry.getKey());
        }
        List<Byte> bytesList = new ArrayList<>();
        for (int i = 0; i < code.length(); ) {
            int count = 1;
            while (true) {
                if (i + count >= code.length()) {
                    i = code.length();
                    break;
                }
                String key = code.substring(i, i + count);
                Byte value = unzipCodes.get(key);
                if (value == null) {
                    count++;
                } else {
                    bytesList.add(value);
                    i += count;
                    break;
                }
            }
        }
        byte[] bytes = new byte[bytesList.size()];
        for (int i = 0; i < bytesList.size(); i++) {
            bytes[i] = bytesList.get(i);
        }
        return new String(bytes);
    }

    /**
     * 哈夫曼编码
     *
     * @param bytes 编码前
     * @return 编码后
     */
    public static byte[] huffmanZip(byte[] bytes) {
        // 1.创建哈夫曼树
        Map<Byte, Integer> huffmanMap = byteCounter(bytes);
        HuffmanCodeNode root = initHuffmanTree(huffmanMap);
        // 2.获得哈夫曼编码表
        toHuffmanCodes(root);
        // 3.进行转码
        return toHuffmanBytes(bytes, HuffmanCodes);
    }

    /**
     * 通过哈夫曼编码表转化成哈弗曼编码
     *
     * @param bytes        原字符数组
     * @param huffmanCodes 哈夫曼编码表
     * @return 编码后的哈夫曼编码
     */
    private static byte[] toHuffmanBytes(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(huffmanCodes.get(b));
        }
        byte[] code = new byte[(sb.length() + 7) / 8];
        int index = 0;
        for (int i = 0; i < sb.length(); i += 8) {
            if (i + 8 < sb.length()) {
                code[index++] = (byte) Integer.parseInt(sb.substring(i, i + 8), 2);
            } else {
                StringBuilder temp = new StringBuilder(sb.substring(i));
                for (int j = temp.length(); j < 8; j++) {
                    temp.append("0");
                }
                code[index++] = (byte) Integer.parseInt(temp.toString(), 2);
            }
        }
        return code;
    }

    /**
     * 将哈夫曼树转换为哈夫曼编码表（重载）
     *
     * @param root 根节点
     */
    private static void toHuffmanCodes(HuffmanCodeNode root) {
        toHuffmanCodes(root, "");
    }

    /**
     * 将哈夫曼树转换为哈夫曼编码表
     *
     * @param node 节点
     * @param s    代拼接编码
     */
    private static void toHuffmanCodes(HuffmanCodeNode node, String s) {
        if (node == null) {
            return;
        }
        // node有值的话 -> 将b放进去
        if (node.b != null) {
            HuffmanCodes.put(node.b, s);
        }
        toHuffmanCodes(node.leftNode, s + "0");
        toHuffmanCodes(node.rightNode, s + "1");
    }

    /**
     * 创建哈夫曼树
     *
     * @param huffmanMap 字符权重
     * @return 根节点
     */
    private static HuffmanCodeNode initHuffmanTree(Map<Byte, Integer> huffmanMap) {
        List<HuffmanCodeNode> list = new ArrayList<>();
        for (Byte b : huffmanMap.keySet()) {
            list.add(new HuffmanCodeNode(b, huffmanMap.get(b)));
        }
        while (list.size() != 1) {
            Collections.sort(list);
            HuffmanCodeNode hcn1 = list.get(0);
            HuffmanCodeNode hcn2 = list.get(1);
            list.remove(0);
            list.remove(0);
            list.add(new HuffmanCodeNode(null, hcn1.weight + hcn2.weight, hcn1, hcn2));
        }
        return list.get(0);
    }

    /**
     * 统计字符出现的次数
     *
     * @param bytes 待统计字符
     * @return 字符权重map
     */
    public static Map<Byte, Integer> byteCounter(byte[] bytes) {
        Map<Byte, Integer> map = new HashMap<>();
        for (byte b : bytes) {
            map.merge(b, 1, Integer::sum);
        }
        return map;
    }
}

/**
 * 哈夫曼编码的哈夫曼树节点
 */
class HuffmanCodeNode implements Comparable<HuffmanCodeNode> {
    Byte b;
    int weight;
    HuffmanCodeNode rightNode;
    HuffmanCodeNode leftNode;

    public HuffmanCodeNode(Byte b, int weight) {
        this.b = b;
        this.weight = weight;
    }

    public HuffmanCodeNode(Byte b, int weight, HuffmanCodeNode rightNode, HuffmanCodeNode leftNode) {
        this.b = b;
        this.weight = weight;
        this.rightNode = rightNode;
        this.leftNode = leftNode;
    }

    @Override
    public int compareTo(@NotNull HuffmanCodeNode o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "HuffmanCodeNode{" + "b=" + b + ", weight=" + weight + ", rightNode=" + rightNode + ", leftNode=" + leftNode + '}';
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

四、二叉排序树（BST）

1、二叉排序树概述

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

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

2、二叉排序树删除节点

1）叶子节点

找到该节点
找到该节点的父节点
判断该节点与其父节点的位置
1. 左子树：parentNode.left == null
2. 右子树：parentNode.right == null

2）度为一的节点

找到该节点
找到该节点的父节点
判断该节点与其父节点的位置
1. 该节点是父节点的左子树
  1. 该节点存在左子树：parentNode.left == node.left
  2. 该节点存在右子树：parentNode.left == node.right
2. 该节点是父节点的右子树
  1. 该节点存在左子树：parentNode.right == node.left
  2. 该节点存在右子树：parentNode.right == node.right

3）度为二的节点

找到该节点
找到该节点右子树的最小节点（递归其右子树的左节点的左节点...）
保存最小节点的值temp
删除最小节点（叶子结点）
将该节点的的值改为temp

3、二叉排序树代码实现

java

package work.rexhao.binarySortTree;

/**
 * 二叉排序树BST
 *
 * @author 王铭颢
 * @Date 2022/7/11 10:05
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        BinarySortTree bst = new BinarySortTree();
        int[] num = {7, 3, 10, 1, 6, 9, 12, 2};
        for (int i : num) {
            bst.add(new Node(i));
        }
        BinarySortTree.infixOrder(bst.root);
        System.out.println();

        bst.delete(10);
        BinarySortTree.infixOrder(bst.root);
        System.out.println();

    }
}

/**
 * 二叉排序树
 */
class BinarySortTree {
    Node root;

    /**
     * 添加节点
     *
     * @param next 待添加节点
     */
    public void add(Node next) {
        if (root == null) {
            root = next;
        } else {
            root.add(next);
        }
    }

    /**
     * 前序遍历
     *
     * @param node 根节点
     */
    public static void infixOrder(Node node) {
        if (node == null) {
            return;
        }
        infixOrder(node.left);
        System.out.print(node.data + " ");
        infixOrder(node.right);
    }

    /**
     * 删除节点
     *
     * @param target 待删除节点的值
     */
    public void delete(int target) {
        Node node = search(root, target);
        Node nodeParent = searchParent(root, node);
        // 经典判空
        if (node == null || nodeParent == null) {
            System.out.println("节点不存在或节点无父节点!");
            return;
        }
        // 判断待删除节点的形式
        if (node.left == null && node.right == null) {
            // 叶子节点
            if (nodeParent.right == node) {
                // 右节点
                nodeParent.right = null;
            } else {
                // 左节点
                nodeParent.left = null;
            }
        } else if (node.left != null && node.right != null) {
            // 两个子树的节点
            // 1. 找右子树的最小值(右子树的左子树的叶子结点)
            Node min = searchRightMinNode(node.right);
            // 2. 记录最小值
            int temp = min.data;
            // 3. 删除原来的最小值节点
            delete(min.data);
            // 4. 将最小值提到(覆盖)节点位置
            node.data = temp;
        } else {
            // 一个子树的节点
            if (node.left == null) {
                // 存在右子树
                if (nodeParent.right == node) {
                    // 右节点
                    nodeParent.right = node.right;
                } else {
                    // 左节点
                    nodeParent.left = node.right;
                }
            } else {
                // 存在左子树
                if (nodeParent.right == node) {
                    // 右节点
                    nodeParent.right = node.left;
                } else {
                    // 左节点
                    nodeParent.left = node.left;
                }
            }
        }


    }

    /**
     * 找 node 节点右子树的最小节点
     *
     * @param node 开始寻找的节点
     * @return 右子树的最小节点
     */
    private Node searchRightMinNode(Node node) {
        // 找到叶子结点(最小的点)
        return node.left == null ? node : searchRightMinNode(node.left);
    }

    /**
     * 找 data 为 i 的节点
     *
     * @param root 根节点
     * @param i    待查找数据
     * @return 查找到的节点，不存在返回null
     */
    public static Node search(Node root, int i) {
        // 1.经典判空
        if (root == null) {
            return null;
        }
        // 2.找节点
        if (i == root.data) {
            return root;
        } else if (i < root.data) {
            return search(root.left, i);
        } else {
            return search(root.right, i);
        }
    }

    /**
     * 找到 target 的父节点
     *
     * @param root   根节点
     * @param target 待寻找节点
     * @return 待寻找节点的父节点，不存在返回null
     */
    public static Node searchParent(Node root, Node target) {
        // 经典判空
        if (root == null || target == null) {
            return null;
        }
        // 判左右的节点
        if ((root.right != null && root.right.data == target.data) || (root.left != null && root.left.data == target.data)) {
            return root;
        }
        // 没找到 -> 递归往下找
        if (root.data > target.data) {
            return searchParent(root.left, target);
        } else {
            return searchParent(root.right, target);
        }
    }
}

/**
 * 节点
 */
class Node {
    int data;
    Node left;
    Node right;

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

    /**
     * 添加节点
     *
     * @param next 待添加节点
     */
    public void add(Node next) {
        if (next == null) {
            return;
        }
        if (this.data > next.data) {
            if (this.left == null) {
                this.left = next;
            } else {
                this.left.add(next);
            }
        } else {
            if (this.right == null) {
                this.right = next;
            } else {
                this.right.add(next);
            }
        }
    }

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

五、平衡二叉树（AVL树）

1、BST可能的问题

若BST左子树or右子树为空 -> 单链表

查询速度明显降低（因为需要依次比较），不能发挥BST的优势

2、平衡二叉树概述

定义：平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树（AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis）

特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

3、平衡二叉树的转换

1）左旋转

取右子节点
将根节点的值挂在 newRoot 上
将 root 的左子节点挂在 newRoot.left.left
将原 newRoot 的左子节点挂在 newRoot.left.right
将原 newRoot 的右子节点挂在 newRoot.right
用 newRoot 替换 root

2）右旋转

取左子节点
将根节点的值挂在 newRoot 上
将 root 的右子节点挂在 newRoot.right.right
将原 newRoot 的右子节点挂在 newRoot.right.left
将原 newRoot 的左子节点挂在 newRoot.left
用 newRoot 替换 root

3）双旋转

左子树 > 右子树：右旋转

左子树 < 右子树：左旋转

4、AVL树的代码实现

java

package work.rexhao.AVLTree;

import java.util.Arrays;

/**
 * 平衡二叉树
 */
public class AVLDemo {
    public static void main(String[] args) {
        // 案例1：左旋转
        int[] num0 = {4, 3, 6, 5, 7, 8};
        System.out.println(Arrays.toString(num0));
        AVLTree avl0 = new AVLTree();
        for (int i : num0) {
            avl0.add(new Node(i));
        }
        avl0.infixOrder();
        System.out.println("left = " + avl0.findLeftHeight());
        System.out.println("right = " + avl0.findRightHeight());
        System.out.println("是否为AVL树:" + avl0.isAVL());
        avl0.leftRotate();
        avl0.infixOrder();
        System.out.println("left = " + avl0.findLeftHeight());
        System.out.println("right = " + avl0.findRightHeight());
        System.out.println("是否为AVL树:" + avl0.isAVL());

        System.out.println("-------------");

        // 案例2：右旋转
        int[] num1 = {7, 5, 8, 4, 6, 3};
        System.out.println(Arrays.toString(num1));
        AVLTree avl1 = new AVLTree();
        for (int i : num1) {
            avl1.add(new Node(i));
        }
        avl1.infixOrder();
        System.out.println("left = " + avl1.findLeftHeight());
        System.out.println("right = " + avl1.findRightHeight());
        System.out.println("是否为AVL树:" + avl1.isAVL());
        avl1.rightRotate();
        avl1.infixOrder();
        System.out.println("left = " + avl1.findLeftHeight());
        System.out.println("right = " + avl1.findRightHeight());
        System.out.println("是否为AVL树:" + avl1.isAVL());

        System.out.println("-------------");

        // 案例3：双旋转
        int[] num2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(Arrays.toString(num2));
        AVLTree avl2 = new AVLTree();
        for (int i : num2) {
            avl2.add(new Node(i));
        }
        avl2.infixOrder();
        System.out.println("left = " + avl2.findLeftHeight());
        System.out.println("right = " + avl2.findRightHeight());
        System.out.println("是否为AVL树:" + avl2.isAVL());
        avl2.rotate();
        avl2.infixOrder();
        System.out.println("left = " + avl2.findLeftHeight());
        System.out.println("right = " + avl2.findRightHeight());
        System.out.println("是否为AVL树:" + avl2.isAVL());

        System.out.println("-------------");
    }
}

/**
 * 二叉排序树
 */
class AVLTree {
    Node root;

    /**
     * 双旋转
     */
    public void rotate() {
        while (true) {
            if (isAVL()) {
                break;
            } else {
                if (findLeftHeight() > findRightHeight()) {
                    rightRotate();
                } else {
                    leftRotate();
                }
            }
        }
    }

    /**
     * 左旋转
     */
    public void leftRotate() {
        // 0. 经典判空
        if (root == null) return;
        // 1. 取右子节点
        Node newRoot = new Node(root.right.data);
        // 2. 将根节点的值挂在 newRoot 上
        newRoot.left = new Node(root.data);
        // 3. 将 root 的左子节点挂在 newRoot.left.left
        newRoot.left.left = root.left;
        // 4. 将原 newRoot 的左子节点挂在 newRoot.left.right
        newRoot.left.right = root.right.left;
        // 5. 将原 newRoot 的右子节点挂在 newRoot.right
        newRoot.right = root.right.right;
        // 6. 用 newRoot 替换 root
        this.root = newRoot;
    }

    /**
     * 右旋转
     */
    public void rightRotate() {
        // 0. 经典判空
        if (root == null) return;
        // 1. 取左子节点
        Node newRoot = new Node(root.left.data);
        // 2. 将根节点的值挂在 newRoot 上
        newRoot.right = new Node(root.data);
        // 3. 将 root 的右子节点挂在 newRoot.right.right
        newRoot.right.right = root.right;
        // 4. 将原 newRoot 的右子节点挂在 newRoot.right.left
        newRoot.right.left = root.left.right;
        // 5. 将原 newRoot 的左子节点挂在 newRoot.left
        newRoot.left = root.left.left;
        // 6. 用 newRoot 替换 root
        this.root = newRoot;
    }

    /**
     * 判断是否为平衡二叉树
     */
    public boolean isAVL() {
        return Math.abs(findLeftHeight() - findRightHeight()) <= 1;
    }

    /**
     * 找右子树深度
     *
     * @return 右子树深度
     */
    public int findRightHeight() {
        if (root == null) {
            return 0;
        }
        int[] r = {1};
        int[] l = {1};
        findHeight(root.right, r, l);
        return Math.max(r[0], l[0]);
    }

    /**
     * 找左子树深度
     *
     * @return 左子树深度
     */
    public int findLeftHeight() {
        if (root == null) {
            return 0;
        }
        int[] r = {1};
        int[] l = {1};
        findHeight(root.left, r, l);
        return Math.max(r[0], l[0]);
    }

    /**
     * 求深度
     */
    private void findHeight(Node node, int[] r, int[] l) {
        // 经典判空
        if (node == null) {
            return;
        }
        // 判叶子节点
        if (node.left == null && node.right == null) {
            return;
        }
        if (node.left != null) {
            r[0]++;
            findHeight(node.left, r, l);
        }
        if (node.right != null) {
            l[0]++;
            findHeight(node.right, r, l);
        }
    }


    /**
     * 添加节点
     *
     * @param next 待添加节点
     */
    public void add(Node next) {
        if (root == null) {
            root = next;
        } else {
            root.add(next);
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        Node.infixOrder(root);
        System.out.println();
    }

}

/**
 * 节点
 */
class Node {
    int data;
    Node left;
    Node right;

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

    /**
     * 添加节点
     *
     * @param next 待添加节点
     */
    public void add(Node next) {
        if (next == null) {
            return;
        }
        if (this.data > next.data) {
            if (this.left == null) {
                this.left = next;
            } else {
                this.left.add(next);
            }
        } else {
            if (this.right == null) {
                this.right = next;
            } else {
                this.right.add(next);
            }
        }
    }

    /**
     * 中序遍历
     *
     * @param node 根节点
     */
    public static void infixOrder(Node node) {
        if (node == null) {
            return;
        }
        infixOrder(node.left);
        System.out.print(node.data + " ");
        infixOrder(node.right);
    }

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

树结构应用 ​

一、堆排序 ​

1、堆排序概述 ​

2、堆排序思路 ​

3、堆排序代码实现 ​

二、赫夫曼树 ​

1、赫夫曼树基本介绍 ​

2、赫夫曼树的概念 ​

1）路径和路径长度 ​

2）结点的权及带权路径长度 ​

3）树的带权路径长度 ​

4）WPL ​

3、赫夫曼树的代码实现 ​

三、赫夫曼编码 ​

1、赫夫曼编码的基本介绍 ​

2、赫夫曼编码的注意事项 ​

3、代码实现 ​

四、二叉排序树（BST） ​

1、二叉排序树概述 ​

2、二叉排序树删除节点 ​

1）叶子节点 ​

2）度为一的节点 ​

3）度为二的节点 ​

3、二叉排序树代码实现 ​

五、平衡二叉树（AVL树） ​

1、BST可能的问题 ​

2、平衡二叉树概述 ​

3、平衡二叉树的转换 ​

1）左旋转 ​

2）右旋转 ​

3）双旋转 ​

4、AVL树的代码实现 ​

树结构应用

一、堆排序

1、堆排序概述

2、堆排序思路

3、堆排序代码实现

二、赫夫曼树

1、赫夫曼树基本介绍

2、赫夫曼树的概念

1）路径和路径长度

2）结点的权及带权路径长度

3）树的带权路径长度

4）WPL

3、赫夫曼树的代码实现

三、赫夫曼编码

1、赫夫曼编码的基本介绍

2、赫夫曼编码的注意事项

3、代码实现

四、二叉排序树（BST）

1、二叉排序树概述

2、二叉排序树删除节点

1）叶子节点

2）度为一的节点

3）度为二的节点

3、二叉排序树代码实现

五、平衡二叉树（AVL树）

1、BST可能的问题

2、平衡二叉树概述

3、平衡二叉树的转换

1）左旋转

2）右旋转

3）双旋转

4、AVL树的代码实现