Java数据结构与算法（十）：树结构实际应用

谁践踏了优雅 2022-12-21 09:27 255阅读 0赞

## 1. 堆排序 ##

### 1.1. 基本介绍 ###

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 1]

### 1.2 基本思想 ###

堆排序的基本思想是：

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

### 1.3 堆排序步骤图解 ###

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

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

*  假设给定无序序列结构如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 2]
 *  此时我们从最后一个非叶子结点开始（叶子结点自然不用调整，第一个非叶子节点 arr.length/2-1=5/2-1=1，也就是下面的6结点）， 从左至右，从下至上进行调整。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 3]
 *  找到第二个非叶子节点4，由于\[4,9,8\]中9元素最大，4和9交换。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 4]
 *  这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 5]  
    此时，我们就将一个无序序列构造成了一个大顶堆。

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

*  将堆顶元素9和末尾元素4进行交换  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 6]
 *  重新调整结构，使其继续满足堆定义  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 7]
 *  再将堆顶元素8与末尾元素5进行交换，得到第二大元素8。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 8]
 *  后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 9]

### 1.4 代码实现 ###

package com.lele.tree;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    /**
     * author: hwl
     * date: 2020/11/12 7:29
     * version: 1.0.0
     * modified by:
     * description:
     */
    public class HeapSort {
        
    
        public static void main(String[] args) {
        
            // 升序排序
    //        int arr[] = {4,6,8,5,9,90,-1,0,45,100};
    
            int[] arr = new int [8000000];
            for (int i = 0; i < 8000000; i++) {
        
                arr[i] = (int)(Math.random() * 8000000);// 生成一个[0,8000000)的数
            }
            System.out.println("排序前");
            Date date1 = new Date();
            SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
            String date1Str = simpleDateFormat.format(date1);
            System.out.println("排序前的时间是：" + date1Str);
    
            heapSort(arr);
    
            Date date2 = new Date();
            String date2Str = simpleDateFormat.format(date2);
            System.out.println("排序后的时间是：" + date2Str);
        }
    
        public static void heapSort(int arr[]) {
        
            int temp = 0;
            System.out.println("堆排序！");
    
            // 分步完成
    //        adjustHeap(arr, 1, arr.length);
    //        System.out.println("第一次" + Arrays.toString(arr));// 4,9,8,5,6
    //
    //        adjustHeap(arr, 0, arr.length);
    //        System.out.println("第二次" + Arrays.toString(arr)); //9,6,8,5,4
    
            // 完成最终代码
            // 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
            for (int i = arr.length/2 - 1; i >= 0; i--) {
        
                adjustHeap(arr, i, arr.length);
            }
    
            /**
             * 2.将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端；
             * 3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复进行调整+交换步骤，直到整个序列有序。
             */
            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 => 得到{4,9,,8,5,6} => {9,6,8,5,4}
         * @param arr 待调整的数组
         * @param i
         * @param length
         */
        public static void adjustHeap(int arr[], int i, int length) {
        
            int temp = arr[i];// 先取出当前元素的值，保存在临时变量
            // 开始调整
            // 说明
            // 1. k=1*2 + 1  k是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值放到调整后的位置
        }
    }

## 2. 哈夫曼树 ##

### 2.1 基本介绍 ###

1.  给定 n 个权值作为 n 个叶子结点，构造一颗二叉树，**若该树的带权路径长度（wpl）达到最小**，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffman Tree)。
2.  哈夫曼树是带权路径长度最短的树，权值较大的结点离跟较近。

### 2.2 哈夫曼树几个重要概念和举例说明 ###

1.  **路径和路径长度**：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到L层结点的路径长度为 L-1.
2.  **结点的权及带权路径长度**：若树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。**结点的带权路径长度为**：从根结点到该结点之间的路径长度与该结点的权的乘积。
3.  树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL（weighted path length），权值越大的结点离根结点越近的二叉树才是最有二叉树。
4.  WPL最小的就是哈夫曼树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 10]

### 2.3 哈夫曼树创建思路图解 ###

给你一个数列 \{13,7,8,3,29,6,1\} 要求转成一棵哈夫曼树。

**构成哈夫曼树的步骤：**

1.  从小到大进行排序，将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树。
2.  取出根节点权值最小的两颗二叉树；
3.  组成一颗新的二叉树，该新的二叉树的根结点的权值是前面两颗二叉树根结点权值的和。
4.  再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗哈夫曼树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 11]

### 2.4 代码实现 ###

package com.lele.huffmantree;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    /**
     * author: hwl
     * date: 2020/11/16 7:24
     * version: 1.0.0
     * modified by:
     * description:
     */
    public class HuffmanTree {
        
        public static void main(String[] args) {
        
            int arr[] = {
        13,7,8,3,29,6,1};
    
            Node root = createHuffmanTree(arr);
            preOrder(root);
        }
    
        public static void preOrder(Node root) {
        
            if (root != null) {
        
                root.preOrder();
            } else {
        
                System.out.println("是空树，不能遍历~");
            }
        }
    
        /**
         * 创建哈夫曼树的方法
         * @param arr 需要创建成哈夫曼树的数组
         * @return  创建好后的哈夫曼树的 root 节点
         */
        public static Node createHuffmanTree(int[] arr) {
        
            // 第一步为了操作方便
            // 1.遍历 arr 数组
            // 2.将arr的每个元素构成一个Node
            // 3.将Node放入到ArrayList中
            List<Node> nodes = new ArrayList<>();
            for (int value : arr) {
        
                nodes.add(new Node(value));
            }
    
            while (nodes.size() > 1) {
        
                // 排序 从小到大
                Collections.sort(nodes);
    
                System.out.println("nodes=" + 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);
            }
    
            // 返回哈夫曼树的root结点
            return nodes.get(0);
        }
    }
    
    // 创建结点类
    // 为了让 Node 对象持续排序Collections集合排序
    // 让Node实现Comparable接口
    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;
        }
    }

## 3. 哈夫曼编码 ##

### 3.1 基本介绍 ###

1.  哈夫曼编码是一种编码方式，属于一种程序算法；
2.  哈夫曼编码是哈夫曼树在电讯通信中的经典的应用之一；
3.  哈夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%~90%之间；
4.  哈夫曼编码是可变长编码（VLC）的一种。

### 3.2 原理剖析 ###

*  通信邻域中信息的处理方式1-定长编码。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 12]
 *  通信领域中信息的处理方式2-变长编码  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 13]
 *  通信领域中信息的处理方式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 的步骤，直到数列中，所有的数据都被处理，就得到一颗哈夫曼树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 14]  
根据哈夫曼树，给各个字符，规定编码（前缀编码），向左的路径为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

按照上面的哈夫曼编码，我们的 “i like like like java do you like a java" 字符串对应的编码为（注意这里我们使用的无损压缩）  
![在这里插入图片描述][20201121100035441.png_pic_center]  
通过哈夫曼编码处理 长度为 133。  
原来长度 359，压缩了 （359-133）/359 = 62.9%.。

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

**注意事项**  
注意，这个哈夫曼树根据排序方法不同，也可能不太一样，这样对应的哈夫曼编码也不完全一样但是wpl是一样的，都是最小的，最后生成的哈夫曼编码的长度是一样，比如：如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 15]

### 3.3 最佳实践-数据压缩（创建哈夫曼树） ###

将给出一段文本，比如 “i like like like java do you like a java"，采用哈夫曼编码进行数据压缩。  
**代码实现**

package com.lele.huffmancode;
    
    import java.util.*;
    
    /**
     * author: hwl
     * date: 2020/11/20 21:56
     * version: 1.0.0
     * modified by:
     * description:
     */
    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);// 40
    
            List<Node> nodes = getNodes(contentBytes);
            System.out.println("nodes=" + 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("哈夫曼树为空");
            }
        }
    
        /**
         *
         * @param bytes  接收字节数组
         * @return 返回的就是List形式
         */
        private static List<Node> getNodes(byte[] bytes) {
        
            // 1. 创建一个ArrayList
            ArrayList<Node> nodes = new ArrayList<>();
    
            // 遍历bytes，统计每个byte出现的次数 -> map
            HashMap<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;
        }
    
        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最后的节点，就是哈夫曼树的根节点
            return nodes.get(0);
        }
    }
    
    // 创建Node，待数据和权值
    class Node implements Comparable<Node> {
        
        Byte data; // 存放数据本身，比如 'a' => 97  ' ' => 32
        int weight;// 权值，表示字符出现的次数
        Node left;
        Node right;
    
        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();
            }
        }
    }

### 3.4 最佳实践-数据压缩（生成哈夫曼编码和哈夫曼编码后的数据） ###

*  生成哈夫曼树对应的哈夫曼编码：

=01  a=100  d=11001 u=11001  e=1110    v=11011  i=101  y=11010  j=0010  k=1111   l=000  o=0011

*  使用哈夫曼编码来生成哈夫曼编码数据，即按照上面的哈夫曼编码，将"i like like like java do you like a java" 字符串生成对应的编码数据，形式如下：  
    10101000…

// 生成哈夫曼树对应的哈夫曼编码
        // 思路：
        // 1. 将哈夫曼编码存放在 Map<Byte, String> 形式
        // 生成的哈夫曼编码表{32=01,97=100,100=11000,117=11001,101=1110,118=11011, 105=101, 121=11010, 106=0010}
        static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
        // 2. 定义一个StringBuilder 存储某个叶子结点的路径
        static StringBuilder stringBuilder = new StringBuilder();
    
        // 为了调用方便，重载getCodes
        private static Map<Byte, String> getCodes(Node root) {
        
            if (root == null) {
        
                return null;
            }
            // 处理 root 的左子树
            getCodes(root.left, "0", stringBuilder);
            // 处理root 的右子树
            getCodes(root.right, "1", stringBuilder);
            return huffmanCodes;
        }
    
        /**
         * 功能：将传入的Node结点的所有叶子节点的哈夫曼编码得到，并放入到huffmanCodes集合
         * @param node  传入节点
         * @param code  路径：左子节点是 0，右子节点 1
         * @param stringBuilder  用于拼接路径
         */
        private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        
            StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
            // 将code加入到stringBuilder2
            stringBuilder2.append(code);
            if (node != null) {
        
                // 判断当前 node 是叶子节点还是非叶子节点
                if (node.data == null) {
         // 非叶子节点
                    // 递归处理
                    // 向左递归
                    getCodes(node.left, "0", stringBuilder2);
                    // 向右递归
                    getCodes(node.right, "1", stringBuilder2);
                } else {
        
                    // 表示找到某个叶子节点的最后
                    huffmanCodes.put(node.data, stringBuilder2.toString());
                }
            }
        }

### 3.5 最佳实践-数据解压（使用哈夫曼编码解码） ###

/**
         * 将一个byte 转成一个二进制的字符串
         * @param flag  标志是否需要补高位，如果是true，需要补高位，false表示不补
         * @param b 传入的byte
         * @return b 对应的二进制字符串（注意是按补码返回）
         */
        private static String byteToBitString(boolean flag, byte b) {
        
            // 使用变量保存 b
            int temp = b; // 将b转成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<String, Byte>();
            for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
        
                map.put(entry.getValue(), entry.getKey());
            }
            List<Byte> list = new ArrayList<>();
            for (int i = 0; i < stringBuilder.length();) {
        
                int count = 1;
                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中存放了所有的字符 "i like like like java do you like a java"
            // 把list中的数据放入到byte[] 并返回
            byte[] b = new byte[list.size()];
            for (int i = 0; i < b.length; i++) {
        
                b[i] = list.get(i);
            }
            return b;
        }

### 3.6 最佳实践-文件压缩 ###

*  思路： 读取文件=>得到哈夫曼编码表=> 完成压缩

/**
         * 将文件进行压缩
         * @param srcFile 需要压缩的文件的全路径
         * @param dstFile 压缩文件的存放目录
         */
        public static void zipFile(String srcFile, String dstFile) {
        
    
            // 创建输出流
            OutputStream os = null;
            ObjectOutputStream oos = null;
            // 创建文件输入流
            FileInputStream is = null;
            try {
        
                // 创建文件输入流
                is = new FileInputStream(srcFile);
                // 创建一个和源文件大小一样的byte[]
                byte[] b = new byte[is.available()];
                // 读取文件
                is.read(b);
                // 直接对源文件压缩
                byte[] huffmanBytes = huffmanZip(b);
                // 创建文件的输出流，存放压缩文件
                os = new FileOutputStream(dstFile);
                // 创建一个和文件输出流关联的ObjectOutputStream
                oos = new ObjectOutputStream(os);
                // 将哈夫曼编码后的字节数组写入压缩文件
                oos.writeObject(huffmanBytes);//
    
                // 以对象流的方式写入 哈夫曼编码，是为了以后恢复源文件时使用
                // 注意一定要把哈夫曼编码写入压缩文件
                oos.writeObject(huffmanCodes);
            } catch (Exception e) {
        
                System.out.println(e.getMessage());
            } finally {
        
                try {
        
                    is.close();
                    oos.close();
                    os.close();
                } catch (Exception e) {
        
                    System.out.println(e.getMessage());
                }
            }
        }

### 3.7 文件解压（文件恢复） ###

*  思路：读取压缩文件（数据和哈夫曼编码表）=> 完成解压（文件恢复）

/**
         * 将文件解压
         * @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 (Exception ex) {
        
                    System.out.println(ex.getMessage());
                }
            }
        }

### 3.8 完整代码 ###

package com.lele.huffmancode;
    
    import java.io.*;
    import java.util.*;
    
    /**
     * author: hwl
     * date: 2020/11/20 21:56
     * version: 1.0.0
     * modified by:
     * description:
     */
    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);// 40
    //
    //        byte[] huffmanCodesBytes = huffmanZip(contentBytes);
    //        System.out.println("压缩后的结果为：" + Arrays.toString(huffmanCodesBytes));
    //
    //        byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
    //        System.out.println("原来的字符串:" + new String(sourceBytes));//i like like like java do you like a java
    
    //        // 测试压缩文件
    //        String srcFile = "E:\\IdeaProjects\\project\\DataStructure\\data\\test.bmp";
    //        String dstFile = "E:\\IdeaProjects\\project\\DataStructure\\data\\test.zip";
    //
    //        zipFile(srcFile,dstFile);
    //        System.out.println("压缩文件成功");
    
            // 测试解压文件
            String zipFile = "E:\\IdeaProjects\\project\\DataStructure\\data\\test.zip";
            String dstFile = "E:\\IdeaProjects\\project\\DataStructure\\data\\test1.bmp";
            unZipFile(zipFile, dstFile);
            System.out.println("解压成功~~");
    
    //        List<Node> nodes = getNodes(contentBytes);
    //        System.out.println("nodes=" + nodes);
    //
    //        // 测试，创建二叉树
    //        System.out.println("哈夫曼树");
    //        Node huffmanTreeRoot = createHuffmanTree(nodes);
    //        System.out.println("前序遍历");
    //        huffmanTreeRoot.preOrder();
    //
    //        // 测试，生成对应的哈夫曼编码
    //        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    //        System.out.println("生成的哈夫曼编码表" + huffmanCodes);
    //
    //        byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
    //        System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));
        }
    
        /**
         * 将文件解压
         * @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 (Exception ex) {
        
                    System.out.println(ex.getMessage());
                }
            }
        }
    
        /**
         * 将文件进行压缩
         * @param srcFile 需要压缩的文件的全路径
         * @param dstFile 压缩文件的存放目录
         */
        public static void zipFile(String srcFile, String dstFile) {
        
    
            // 创建输出流
            OutputStream os = null;
            ObjectOutputStream oos = null;
            // 创建文件输入流
            FileInputStream is = null;
            try {
        
                // 创建文件输入流
                is = new FileInputStream(srcFile);
                // 创建一个和源文件大小一样的byte[]
                byte[] b = new byte[is.available()];
                // 读取文件
                is.read(b);
                // 直接对源文件压缩
                byte[] huffmanBytes = huffmanZip(b);
                // 创建文件的输出流，存放压缩文件
                os = new FileOutputStream(dstFile);
                // 创建一个和文件输出流关联的ObjectOutputStream
                oos = new ObjectOutputStream(os);
                // 将哈夫曼编码后的字节数组写入压缩文件
                oos.writeObject(huffmanBytes);//
    
                // 以对象流的方式写入 哈夫曼编码，是为了以后恢复源文件时使用
                // 注意一定要把哈夫曼编码写入压缩文件
                oos.writeObject(huffmanCodes);
            } catch (Exception e) {
        
                System.out.println(e.getMessage());
            } finally {
        
                try {
        
                    is.close();
                    oos.close();
                    os.close();
                } catch (Exception e) {
        
                    System.out.println(e.getMessage());
                }
            }
        }
    
        /**
         * 完成数据的解压
         * 1. 将huffmanCodeBytes [-88,-65,-56,-65,-65,-55 ...],先转成 哈夫曼编码对应的二进制的字符串 "1010100010111..."
         * 2. 哈夫曼编码对应的二进制的字符串 "1010100010111..." => 对照 哈夫曼编码 => "i like like like java do you like a java"
         */
    
        /**
         * 完成对 压缩数据的解码
         * @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<String, Byte>();
            for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
        
                map.put(entry.getValue(), entry.getKey());
            }
            List<Byte> list = new ArrayList<>();
            for (int i = 0; i < stringBuilder.length();) {
        
                int count = 1;
                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中存放了所有的字符 "i like like like java do you like a java"
            // 把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 flag  标志是否需要补高位，如果是true，需要补高位，false表示不补
         * @param b 传入的byte
         * @return b 对应的二进制字符串（注意是按补码返回）
         */
        private static String byteToBitString(boolean flag, byte b) {
        
            // 使用变量保存 b
            int temp = b; // 将b转成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) {
        
            List<Node> nodes = getNodes(bytes);
            // 根据 nodes 创建的哈夫曼树
            Node huffmanTreeRoot = createHuffmanTree(nodes);
            // 生成对应的哈夫曼编码（根据哈夫曼树）
            Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
            // 根据生成的哈夫曼编码压缩，得到压缩后的哈夫曼编码字节数组
            byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
            return huffmanCodeBytes;
    
        }
    
        /**
         * 将字符串对应的byte[]数组，通过生成的哈夫曼编码表，返回一个哈夫曼编码 压缩后的byte[]
         * @param bytes 这是原始字符串对应的 byte[]
         * @param huffmanCodes 返回哈夫曼处理后的 byte[]
         * @return
         */
        private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        
            // 1.利用 huffmanCodes 将 bytes 转成 哈夫曼编码对应的字符串
            StringBuilder stringBuilder = new StringBuilder();
            // 遍历bytes数组
            for (byte b : bytes) {
        
                stringBuilder.append(huffmanCodes.get(b));
            }
    
            // 统计返回 byte[] huffmanCodeBytes 长度
            // 一行代码 int len = (stringBuilder.length() + 7)/8
            int len;
            if (stringBuilder.length() % 8 == 0) {
        
                len = stringBuilder.length() / 8;
            } else {
        
                len = stringBuilder.length() / 8 + 1;
            }
            // 创建 存储压缩后的 byte 数组
            byte[] huffmanCodeBytes = new byte[len];
            int index = 0;// 记录是第几个byte
            for (int i = 0; i < stringBuilder.length(); i += 8) {
         // 每8位对应一个byte
                String strByte;
                if (i + 8 > stringBuilder.length()) {
        
                    strByte = stringBuilder.substring(i);
                } else {
        
                    strByte = stringBuilder.substring(i, i + 8);
                }
    
                // 将strByte 转成一个byte，放入到 huffmanCodeBytes
                huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
                index++;
            }
            return huffmanCodeBytes;
        }
    
        // 生成哈夫曼树对应的哈夫曼编码
        // 思路：
        // 1. 将哈夫曼编码存放在 Map<Byte, String> 形式
        // 生成的哈夫曼编码表{32=01,97=100,100=11000,117=11001,101=1110,118=11011, 105=101, 121=11010, 106=0010}
        static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
        // 2. 定义一个StringBuilder 存储某个叶子结点的路径
        static StringBuilder stringBuilder = new StringBuilder();
    
        // 为了调用方便，重载getCodes
        private static Map<Byte, String> getCodes(Node root) {
        
            if (root == null) {
        
                return null;
            }
            // 处理 root 的左子树
            getCodes(root.left, "0", stringBuilder);
            // 处理root 的右子树
            getCodes(root.right, "1", stringBuilder);
            return huffmanCodes;
        }
    
        /**
         * 功能：将传入的Node结点的所有叶子节点的哈夫曼编码得到，并放入到huffmanCodes集合
         * @param node  传入节点
         * @param code  路径：左子节点是 0，右子节点 1
         * @param stringBuilder  用于拼接路径
         */
        private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        
            StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
            // 将code加入到stringBuilder2
            stringBuilder2.append(code);
            if (node != null) {
        
                // 判断当前 node 是叶子节点还是非叶子节点
                if (node.data == null) {
         // 非叶子节点
                    // 递归处理
                    // 向左递归
                    getCodes(node.left, "0", stringBuilder2);
                    // 向右递归
                    getCodes(node.right, "1", stringBuilder2);
                } else {
        
                    // 表示找到某个叶子节点的最后
                    huffmanCodes.put(node.data, stringBuilder2.toString());
                }
            }
        }
    
        private static void preOrder(Node root) {
        
            if (root != null) {
        
                root.preOrder();
            } else {
        
                System.out.println("哈夫曼树为空");
            }
        }
    
        /**
         *
         * @param bytes  接收字节数组
         * @return 返回的就是List形式
         */
        private static List<Node> getNodes(byte[] bytes) {
        
            // 1. 创建一个ArrayList
            ArrayList<Node> nodes = new ArrayList<>();
    
            // 遍历bytes，统计每个byte出现的次数 -> map
            HashMap<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;
        }
    
        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最后的节点，就是哈夫曼树的根节点
            return nodes.get(0);
        }
    }
    
    // 创建Node，待数据和权值
    class Node implements Comparable<Node> {
        
        Byte data; // 存放数据本身，比如 'a' => 97  ' ' => 32
        int weight;// 权值，表示字符出现的次数
        Node left;
        Node right;
    
        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();
            }
        }
    }

### 3.9 哈夫曼编码压缩文件注意事项 ###

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

## 4. 二叉排序树 ##

### 4.1 二叉排序树基本介绍 ###

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

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

例：\{7,3,10,12,5,1,9\} 对应的二叉排序树为：  
![在这里插入图片描述][20201127072915995.png_pic_center]

### 4.2 二叉排序树创建和遍历 ###

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如：数组为Array(7,3,10,12,5,1,9),创建成对应的二叉排序树为：  
![在这里插入图片描述][20201128195521759.png_pic_center]

### 4.3 二叉排序树的删除 ###

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

1.  删除叶子节点（比如：2,5,9,12）
2.  删除只有一颗子树的节点（比如：1）
3.  删除有两颗子树的节点；

#### 4.3.1 删除叶子节点 ####

思路：

*  需要先去找到要删除的结点 targetNode；
 *  找到targetNode 的父结点 parent；
 *  确定 targetNode 是 parent 的左子结点还是右子结点；
 *  根据前面的情况来对应删除
    
     *  左子结点 parent.left = null；
     *  右子结点 parent.left = null；

#### 4.3.2 删除只有一颗子树的结点 ####

思路：

*  需要先找到要删除的结点 targetNode；
 *  找到targetNode的父结点 parent；
 *  确定 targetNode 的子结点是左子结点还是右子结点；
 *  targetNode 是 parent 的左子结点还是右子结点；
 *  如果targetNode有左子结点
    
     *  如果 targetNode 是 parent 的左子结点（parent.left = targetNode.left;)
     *  如果 targetNode 是 parent 的右子结点（parent.right = targetNode.left;)
 *  如果 targetNode 有 右子结点
    
     *  如果 targetNode 是 parent 的左子节点（parent.left = targetNode.right）
     *  如果 targetNode 是 parent 的右子结点（parent.right = targetNode.right)

#### 4.3.3 删除有两颗子树的结点 ####

思路

*  需要先去找到要删除的结点 targetNode
 *  找到 targetNode 的父结点 parent
 *  从 targetNode 的右子树找到最小的结点
 *  用一个临时变量，将最小结点的值保存 temp = 11
 *  删除最小结点
 *  targetNode.value = temp

### 4.4 代码实现 ###

package com.lele.binarysorttree;
    
    /**
     * author: hwl
     * date: 2020/11/23 21:51
     * version: 1.0.0
     * modified by:
     * description: 二叉排序树
     */
    public class BinarySortTreeDemo {
        
    
        public static void main(String[] args) {
        
            int[] arr = {
        7,3,10,12,5,1,9,0};
            BinarySortTree binarySortTree = new BinarySortTree();
            for (int i = 0; i < arr.length; i++) {
        
                binarySortTree.add(new Node(arr[i]));
            }
    
            // 中序遍历二叉排序树
            System.out.println("中序遍历二叉排序树~~~");
            binarySortTree.infixOrder();// 1,3,5,7,9,10,12
    
            // 测试 删除叶子结点
    //        binarySortTree.delNode(2);
    //        binarySortTree.delNode(5);
    //        binarySortTree.delNode(9);
    //        binarySortTree.delNode(12);
            binarySortTree.delNode(10);
            System.out.println("删除结点后");
            binarySortTree.infixOrder();
        }
    }
    
    // 创建二叉排序树
    class BinarySortTree {
        
        private Node root;
    
        /**
         * 查找要删除的结点
         * @param value
         * @return
         */
        public Node search(int value) {
        
            if (root == null) {
        
                return null;
            } else {
        
                return root.search(value);
            }
        }
    
        /**
         * 查找父结点
         * @param value
         * @return
         */
        public Node searchParent(int value) {
        
            if (root == null) {
        
                return null;
            } else {
        
                return root.searchParent(value);
            }
        }
    
        /**
         * 1.返回以node为根节点的二叉排序树的最小结点的值
         * 2.删除以node为根节点的二叉排序树的最小结点
         * @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 {
        
                // 1.需要先找到要删除的结点 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;
                    }
                } else if (targetNode.left != null && targetNode.right != null) {
          // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {
          // 删除只有一颗子树的结点
                    // 如果要删除的结点有左子结点
                    if (targetNode.left != null) {
        
                        // 如果targetNode 是 parent 的左子结点
                        if (parent.left.value == value) {
        
                            parent.left = targetNode.left;
                        } else {
        // targetNode 是parent的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
         // 如果要删除的结点有右子结点
                        // 如果 targetNode 是parent 的左子结点
                        if (parent.left.value == value) {
        
                            parent.left = targetNode.right;
                        } else {
         // 如果targetNode是parent的右子结点
                            parent.right = targetNode.right;
                        }
                    }
                }
    
            }
        }
    
        //添加结点的方法
        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("二叉排序树为空，不能遍历");
            }
        }
    }
    
    // 创建Node结点
    class Node {
        
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
        
            this.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;// 没有找到父结点
                }
            }
        }
    
        @Override
        public String toString() {
        
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        /**
         * 添加结点的方法
         * 递归的形式添加结点，注意需要满足二叉排序树的要求
         * @param node
         */
        public void add(Node node) {
        
            if (node == null) {
        
                return;
            }
    
            // 判断传入的结点的值，和当前字数的根结点的值关系
            if (node.value < this.value) {
        
                // 如果当前结点的左子结点为null
                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();
            }
        }
    }

## 5. 平衡二叉树（AVL树） ##

### 5.1 基本介绍 ###

1.  平衡二叉树也叫平衡二叉搜索树又被称为AVL树，可以保证查询效率较高。
2.  具有以下特点：它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

### 5.2 左旋转（单旋转） ###

*  要求：给你一个数列，创建出对应的平衡二叉树，数列\{4,3,6,5,7,8\}
 *  思路分析（示意图）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 16]

### 5.3 右旋转（单旋转） ###

*  要求：给你一个数列，创建出对应的平衡二叉树，数列 \{10,12,8,9,7,6\}
 *  思路分析（示意图）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 17]

### 5.4 双旋转 ###

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

*  问题分析  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 18]
 *  解决思路
    
     *  当符合右旋转的条件时
     *  如果它的左子树的右子树高度大于它的左子树的高度
     *  先对当前这个结点的左节点进行左旋转
     *  再对当前结点进行右旋转的操作即可

### 5.5 完整代码 ###

package com.lele.avl;
    
    /**
     * author: hwl
     * date: 2020/11/30 21:59
     * version: 1.0.0
     * modified by:
     * description: 平衡二叉树
     */
    public class AVLTreeDemo {
        
    
        public static void main(String[] args) {
        
    //        int[] arr = {4,3,6,5,7,8};  // 测试左旋转
    
    //        int[] arr = {10,12,8,9,7,6}; // 测试右旋转
    
            int[] arr = {
        10,11,7,6,8,9};
    
            // 创建一个AVTree对象
            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());// 4
            System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight());// 1
            System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight());// 3
            System.out.println("当前根结点=" + avlTree.getRoot());// 3
    
    
        }
    }
    
    // 创建AVLTree
    class AVLTree {
        
        private Node root;
    
        public Node getRoot() {
        
            return root;
        }
    
        /**
         * 查找要删除的结点
         * @param value
         * @return
         */
        public Node search(int value) {
        
            if (root == null) {
        
                return null;
            } else {
        
                return root.search(value);
            }
        }
    
        /**
         * 查找父结点
         * @param value
         * @return
         */
        public Node searchParent(int value) {
        
            if (root == null) {
        
                return null;
            } else {
        
                return root.searchParent(value);
            }
        }
    
        /**
         * 1.返回以node为根节点的二叉排序树的最小结点的值
         * 2.删除以node为根节点的二叉排序树的最小结点
         * @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 {
        
                // 1.需要先找到要删除的结点 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;
                    }
                } else if (targetNode.left != null && targetNode.right != null) {
          // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {
          // 删除只有一颗子树的结点
                    // 如果要删除的结点有左子结点
                    if (targetNode.left != null) {
        
                        // 如果targetNode 是 parent 的左子结点
                        if (parent.left.value == value) {
        
                            parent.left = targetNode.left;
                        } else {
        // targetNode 是parent的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
         // 如果要删除的结点有右子结点
                        // 如果 targetNode 是parent 的左子结点
                        if (parent.left.value == value) {
        
                            parent.left = targetNode.right;
                        } else {
         // 如果targetNode是parent的右子结点
                            parent.right = targetNode.right;
                        }
                    }
                }
    
            }
        }
    
        //添加结点的方法
        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("二叉排序树为空，不能遍历");
            }
        }
    }
    
    // 创建Node结点
    class Node {
        
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
        
            this.value = value;
        }
    
        /**
         * 返回左子树的高度
         * @return
         */
        public int leftHeight() {
        
            if (left == null) {
        
                return 0;
            }
            return left.height();
        }
    
        /**
         * 返回右子树的高度
         * @return
         */
        public int rightHeight(){
        
            if (right == null) {
        
                return 0;
            }
            return right.height();
        }
    
        /**
         * 返回当前结点的高度，以该结点为根结点的树的高度
         * @return
         */
        public int height() {
        
            return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
        }
    
        /**
         * 左旋转方法
         */
        private void leftRotate(){
        
            // 创建新的结点，以当前根结点的值
            Node newNode = new Node(value);
            // 把新的结点的左子树设置成当前结点的左子树
            newNode.left = left;
            // 把新的结点的右子树设置成当前节点的右子树的左子树
            newNode.right = right.left;
            // 把当前结点的值替换成右子结点的值
            value = right.value;
            // 把当前结点的右子树设置成当前结点的右子树的右子树
            right = right.right;
            // 把当前结点的左子树（左子结点）设置成新的结点
            left = newNode;
        }
    
        /**
         * 右旋转
         */
        private void rightRotate() {
        
            Node newNode = new Node(value);
            newNode.right = right;
            newNode.left = left.right;
            value = left.value;
            left = left.left;
            right = newNode;
        }
    
    
        /**
         * 查找要删除的结点
         * @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;// 没有找到父结点
                }
            }
        }
    
        @Override
        public String toString() {
        
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        /**
         * 添加结点的方法
         * 递归的形式添加结点，注意需要满足二叉排序树的要求
         * @param node
         */
        public void add(Node node) {
        
            if (node == null) {
        
                return;
            }
    
            // 判断传入的结点的值，和当前字数的根结点的值关系
            if (node.value < this.value) {
        
                // 如果当前结点的左子结点为null
                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();
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/3599666d2db94b72b3270bc924015486.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/01b5571f13934d6e8f3778220b73d579.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/c0df6c85b4c74b6da7d8ead27b929625.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/5b50ac69a7c549f4952ad2d841017816.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/9912b107b0d84fb7af1b2b20a5fae2e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/6b7611c078ff47c6b589ab23377d3744.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/fe6fc43933444e789760575683058558.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/e7f345143e444866985899d65ab056e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221120/3966c566081944eeadf5cc757fa65dcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221120/e5234cb00b0d4fe488ff6b59304eb139.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221120/f464e494787e4e49baea25ea366e13a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221120/07e50e634c314b74a828b79fb3cd2e24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221120/a13c7120eb874c0eb41ea8fd5a05da3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221120/0c4c320277d14e4e981e43b5b44aea72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221120/27c779ab180b4a6787b63c3798b6bacf.png
[20201121100035441.png_pic_center]: /images/20221120/c4858108cc14495ca838dd040169e3cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221120/9f890f6c62f843a2b2f68ef822acd138.png
[20201127072915995.png_pic_center]: /images/20221120/d6c09b37d63641cc9bed7e7010812c7c.png
[20201128195521759.png_pic_center]: /images/20221120/d2acf174db3146879992c49213f95db4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221120/53e4761920704a0a908f945708609f91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221120/2c41ba8d352a4e34b6efcc8a14760f71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 18]: /images/20221120/76b76d7ff7344ff2acbb404412f0493f.png