Java数据结构与算法-java数据结构与算法（五）-阿里云开发者社区

Java数据结构与算法-java数据结构与算法（四）https://developer.aliyun.com/article/1469492

树结构实际应用

堆排序

堆排序基本介绍

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

大顶堆

小顶堆

堆排序基本思想

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

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

堆排序步骤图解说明

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

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

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

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换.

得到第二大元素。如此反复进行交换、重建、交换。

.将堆顶元素 9 和末尾元素 4 进行交换
重新调整结构，使其继续满足堆定义
再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

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

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序.

代码实现

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

堆排序不是很好理解，老师通过 Debug 帮助大家理解堆排序
堆排序的速度非常快，在我的机器上 8 百万数据 3 秒左右。O(nlogn)

package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: HeapSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/6 23:52
 * @version: 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] test = new int[8000000];
        //测试数据
        for (int i = 0; i < 8000000; i++) {
            test[i] = (int) (Math.random() * 800000);
        }
        long time = System.currentTimeMillis();
        heapsort(test);
        long end = System.currentTimeMillis();
        long t = ((end - time) / 1000);
        System.out.println("一共用时 " + t + "秒");
        int arr[] = {4, 6, 8, 5, 9};
    }
    public static void heapsort(int[] arr) {
        int temp = 0;
        //按照 大顶堆的方式调整堆
        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));
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 大顶堆交换思路， 判断左右节点大小，之后判断左右节点的比对结果，与父节点判断，将最大值交还给父节点
     * @date: 2022/2/6 23:54
     * @param arr 存放需要将交换节点的数组
     * @param i   需要做调整的父节点索引
     * @param length 有多少节点需要调整
     * @return: void
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //   开始调整
        /* 说明
         * k =i*2+1按照之前线索查找树的公式，找出左子树的节点位置
         * */
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //判断条件 k（节点索引）首先不能大于我们要遍历的结点索引总数，之后判断左右节点的大小，交换
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            //找出最大的子节点，与父节点的值比对，
            if (arr[k] > temp) {
                //将较大的值放入到父节点
                arr[i] = arr[k];
                i = k; //i指向k ， 继续循环比较
            } else {
                break;
            }
        }
        //    for 循环结束之后 我们i已经是父节点以及最大值的索引了
        // 将 temp 调整到最后免得位置
        arr[i] = temp;
    }
}

赫夫曼树

基本介绍

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

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

路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1
结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL(weighted path
length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
WPL 最小的就是赫夫曼树

赫夫曼树创建思路图解

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

构成赫夫曼树的步骤：

从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
取出根节点权值最小的两颗二叉树
组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数
据都被处理，就得到一颗赫夫曼树

赫夫曼树的代码实现

package com.hyc.DataStructure.HuffmanTree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.HuffmanTreeDemo
 * @className: HuffmanTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/8 0:21
 * @version: 1.0
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node manTree = createHuffManTree(arr);
        //    测试
        preOrder(manTree);
    }
    //编写一个前序遍历的方法
    public static void preOrder(Node root) {
        if (root != null) {
            root.PreOrder();
        } else {
            System.out.println("空树无法遍历");
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * @date: 2022/2/8 0:42
     * @param arr 需要创建赫夫曼树的数组
     * @return: com.hyc.DataStructure.HuffmanTree.Node 返回已经创建好的赫夫曼树的根节点
     */
    public static Node createHuffManTree(int[] arr) {
        List<Node> nodes = new ArrayList<>();
        //（1）为了方便操作 我们先遍历数组生成对应节点 放入 arrayList
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        //循环处理
        while (nodes.size() > 1) {
            //    先用接口的sort 排序
            Collections.sort(nodes);
            System.out.println("nodes = " + nodes);
            //   （2） 取出根节点权值最小的两颗二叉树
            //    取出权值最小的结点
            Node leftnode = nodes.get(0);
            //取出根节点第二最小的二叉树
            Node rightnode = nodes.get(1);
            // （3） 构建出一颗新的二叉树
            Node parent = new Node(leftnode.value + rightnode.value);
            parent.left = leftnode;
            parent.right = rightnode;
            //    (4)从 ArrayList删除处理过的二叉树
            nodes.remove(leftnode);
            nodes.remove(rightnode);
            //    (5)将parent加入到 nodes
            nodes.add(parent);
        }
        //    返回赫夫曼树的root节点
        return nodes.get(0);
    }
}
/* 为了Node对象排序，我们实现collections集合排序
 * 这里我们实现 compareble
 * */
class Node implements Comparable<Node> {
    //赫夫曼树 权重值
    int value;
    Node left;
    Node right;
    //    构造方法 创建节点的时候只需要有权重值就可以了
    public Node(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        //这里我们按照权重从小到大排序
        //从大到小只需要置负 -(this.value - o.value)
        return this.value - o.value;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.PreOrder();
        }
        if (this.right != null) {
            this.right.PreOrder();
        }
    }
}

赫夫曼编码

基本介绍

赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间
赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码

原理剖析

定长编码

变长编码

赫夫曼编码

传输的字符串 ,按照字符的出险次数出现权重

i like like like java do you like a java
d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

步骤：

从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
取出根节点权值最小的两颗二叉树
组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

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

如下:

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

10101001101111011110100110111101111010011011110111101000011000011100110011110000110  
01111000100100100110111101111011100100001100001110

长度为：133

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

此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性

赫夫曼编码是无损处理方案

注意事项

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

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

1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110

步骤 1：

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

思路：前面已经分析过了，而且我们已然讲过了构建赫夫曼树的具体实现。

public static Node createHuffManTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //首先从小到大排序 list
            Collections.sort(nodes);
            //    找到list中最小的子树
            Node leftnode = nodes.get(0);
            //找到倒数第二小的
            Node rightnode = nodes.get(1);
            Node parent = new Node(null, leftnode.wight + rightnode.wight);
            parent.left = leftnode;
            parent.right = rightnode;
            //    删除两个被处理过的子树
            nodes.remove(leftnode);
            nodes.remove(rightnode);
            //    之后将parent 加入到list
            //   这样遍历到最后只剩下一个节点 就是我们需要的赫夫曼树
            nodes.add(parent);
        }
        return nodes.get(0);
    }

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

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

生成赫夫曼树对应的赫夫曼编码 , 如下表:

=01  a=100 d=11000 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"

字符串生成对应的编码数据, 形式如下:

1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

思路：前面已经分析过了，而且我们讲过了生成赫夫曼编码的具体实现。

/* 生成赫夫曼树对应的赫夫曼编码
     * 思路 ：
     * 1. 将赫夫曼编码存放在map<byte,string>的形式的map里
     * 2。在生成赫夫曼编码表示，需要去拼接一些路径  定一个一个 stringbuilder 存放叶子节点的路径
     * */
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //存放叶子节点的路径的 stringbuilder
    static StringBuilder stringBuilder = new StringBuilder();
    //为了调用方便 重载getcode
    public static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //  处理左子树
        getCodes(root.left, "0", stringBuilder);
        //处理右子树
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将传入的node节点的所有子节点的赫夫曼编码得到，并且放入huffmanCodes集合中
     * @date: 2022/2/12 15:07
     * @return: void
     * @param node          传入的节点
     * @param code          路径，左子节点是 0 右子节点事 1
     * @param stringBuilder 用于拼接路径
     */
    public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        //将code 加入到 string builder1
        stringBuilder1.append(code);
        if (node != null) {
            //    如果为null 不处理
            //判断是否为叶子结点
            if (node.data == null) {
                //如果data不为空那么代表非叶子节点
                //   向左继续递归
                getCodes(node.left, "0", stringBuilder1);
                //    向右边递归
                getCodes(node.right, "1", stringBuilder1);
            } else {
                //如果进入到这里说明是一个叶子结点
                //    存入到 huffmanCodes这个集合中
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }
    }

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

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

前面我们得到了赫夫曼编码和对应的编码 byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77 , -57, 6, -24, -14, -117, -4, -60, -90, 28]
现在要求使用赫夫曼编码，进行解码，又重新得到原来的字符串"i like like like java do you like a java"
思路：解码过程，就是编码的一个逆向操作。

/**
     * @author 冷环渊 Doomwatcher
     * @context: 将一个byte 转成 一个二进制的字符串
     * @date: 2022/2/12 23:14
     * @param flag 标志是否需要不高位，如果是ture 表示需要补高位，如果是false表示不需要
     * @param b 传入的 byte
     * @return: java.lang.String 返回的b 对应的二进制的字符串（注意事按照补码返回）
     */
    public static String byteToBitString(boolean flag, byte b) {
        //使用变量保存 b
        int temp = b;
        //如果是正数我们还需要补高位
        if (flag) {
            //按位与 256 1 0000 0000| 00000 0001 => 1 0000 0001
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }
  /**
     * @author 冷环渊 Doomwatcher
     * @context: 完成对数据的解压
     * 思路：
     * 1. 其实这就是我们之前压缩思路的逆向，
     * 2.我们先需要将 byte数组形式的转成二进制的心态，
     * 3. 之后转成赫夫曼编码，之后转换成字符
     * @date: 2022/2/12 21:49
     * @param huffmanBytes 赫夫曼编码对应的byte数组
     * @param huffmanCodes 赫夫曼编码表
     * @return: void
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        //1. 先得到huffmancodebytes 对应的 二进制字符串，如 1010100010111
        StringBuilder stringBuilder = new StringBuilder();
        //将byte 数组转成二进制字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        //System.out.println("赫夫曼字节数组解码二进制=>" + stringBuilder.toString());
        //    按照置顶的赫夫曼编码把字符串进行解码
        //    把赫夫曼编码进行转换 a ->100 100->a
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> stringByteEntry : huffmanCodes.entrySet()) {
            map.put(stringByteEntry.getValue(), stringByteEntry.getKey());
        }
        //创建一个集合 里面存放byte
        List<Byte> list = new ArrayList<>();
        //    i可以理解成为索引，扫描stringbuilder
        for (int i = 0; i < stringBuilder.length(); ) {
            //得到编码的计数器
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag) {
                //取出一个 ‘1’或者‘0’,i不动 让 count移动直到匹配到一个字符,递增取出
                String key = stringBuilder.substring(i, 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;
    }

最佳实践-文件压缩

我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压，具体要求：

给你一个图片文件，要求对其进行无损压缩, 看看压缩效果如何。

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

/**
     * @author 冷环渊 Doomwatcher
     * @context: 编写方法 完成对压缩文件的解压
     * @date: 2022/2/13 0:33
     * @param zipFile 准备解压的文件路径
     * @param dstFile 将文件解压到什么路径
     * @return: void
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义对象输入流
        ObjectInputStream ois = null;
        //输出流
        OutputStream os = null;
        try {
            //    创建文件输入流
            is = new FileInputStream(zipFile);
            //    创建对象输入流
            ois = new ObjectInputStream(is);
            byte[] huffmanbytes = (byte[]) ois.readObject();
            //    读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //    解码
            byte[] bytes = decode(huffmanCodes, huffmanbytes);
            //将byte 数组写入目标文件
            os = new FileOutputStream(dstFile);
            //    写数据到fstFile文件
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

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

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

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

/**
     * @author 冷环渊 Doomwatcher
     * @context: 编写方法 完成对压缩文件的解压
     * @date: 2022/2/13 0:33
     * @param zipFile 准备解压的文件路径
     * @param dstFile 将文件解压到什么路径
     * @return: void
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义对象输入流
        ObjectInputStream ois = null;
        //输出流
        OutputStream os = null;
        try {
            //    创建文件输入流
            is = new FileInputStream(zipFile);
            //    创建对象输入流
            ois = new ObjectInputStream(is);
            byte[] huffmanbytes = (byte[]) ois.readObject();
            //    读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //    解码
            byte[] bytes = decode(huffmanCodes, huffmanbytes);
            //将byte 数组写入目标文件
            os = new FileOutputStream(dstFile);
            //    写数据到fstFile文件
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

代码汇总

package com.hyc.DataStructure.huffmanCode;
import java.io.*;
import java.util.*;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.huffmanCode
 * @className: huffmanCodeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/9 19:06
 * @version: 1.0
 */
public class huffmanCodeDemo {
    public static void main(String[] args) {
//        压缩文件测试
//        String srcfile = "D:\\JavaEngineer\\algorithm\\code\\DataStructure\\src.bmp";
//        String dstfile = "D:\\JavaEngineer\\algorithm\\code\\DataStructure\\srcdst.zip";
//        zipFile(srcfile, dstfile);
//        解压文件测试
        String zipfile = "D:\\\\JavaEngineer\\\\algorithm\\\\code\\\\DataStructure\\\\srcdst.zip";
        String dstFile = "D:\\\\JavaEngineer\\\\algorithm\\\\code\\\\DataStructure\\\\src1.bmp";
        unZipFile(zipfile, dstFile);
/*        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("压缩之后的长度 =>" + huffmanCodesBytes.length);
        byte[] decode = decode(huffmanCodes, huffmanCodesBytes);
        System.out.println("输出解码之后的字符串" + new String(decode));*/
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 编写方法 完成对压缩文件的解压
     * @date: 2022/2/13 0:33
     * @param zipFile 准备解压的文件路径
     * @param dstFile 将文件解压到什么路径
     * @return: void
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义对象输入流
        ObjectInputStream ois = null;
        //输出流
        OutputStream os = null;
        try {
            //    创建文件输入流
            is = new FileInputStream(zipFile);
            //    创建对象输入流
            ois = new ObjectInputStream(is);
            byte[] huffmanbytes = (byte[]) ois.readObject();
            //    读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //    解码
            byte[] bytes = decode(huffmanCodes, huffmanbytes);
            //将byte 数组写入目标文件
            os = new FileOutputStream(dstFile);
            //    写数据到fstFile文件
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 文件压缩
     * @date: 2022/2/13 0:17
     * @param srcFile 传入的希望压缩的文件的全路径
     * @param dstFile 压缩之后需要输出的文件路径
     * @return: void
     */
    public static void zipFile(String srcFile, String dstFile) {
        //    创建文件输出流
        //    创建文件输入流
        FileInputStream is = null;
        FileOutputStream os = null;
        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(dstFile);
            //    创建一个和文件输出流关联的objoutputstream
            oos = new ObjectOutputStream(os);
            //把赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //这里我们用对象流的方式写入赫夫曼编码，目的是为了回复文件的时候使用
            oos.writeObject(huffmanCodes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                is.close();
                os.close();
                oos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 完成对数据的解压
     * 思路：
     * 1. 其实这就是我们之前压缩思路的逆向，
     * 2.我们先需要将 byte数组形式的转成二进制的心态，
     * 3. 之后转成赫夫曼编码，之后转换成字符
     * @date: 2022/2/12 21:49
     * @param huffmanBytes 赫夫曼编码对应的byte数组
     * @param huffmanCodes 赫夫曼编码表
     * @return: void
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        //1. 先得到huffmancodebytes 对应的 二进制字符串，如 1010100010111
        StringBuilder stringBuilder = new StringBuilder();
        //将byte 数组转成二进制字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        //System.out.println("赫夫曼字节数组解码二进制=>" + stringBuilder.toString());
        //    按照置顶的赫夫曼编码把字符串进行解码
        //    把赫夫曼编码进行转换 a ->100 100->a
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> stringByteEntry : huffmanCodes.entrySet()) {
            map.put(stringByteEntry.getValue(), stringByteEntry.getKey());
        }
        //创建一个集合 里面存放byte
        List<Byte> list = new ArrayList<>();
        //    i可以理解成为索引，扫描stringbuilder
        for (int i = 0; i < stringBuilder.length(); ) {
            //得到编码的计数器
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag) {
                //取出一个 ‘1’或者‘0’,i不动 让 count移动直到匹配到一个字符,递增取出
                String key = stringBuilder.substring(i, 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;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将一个byte 转成 一个二进制的字符串
     * @date: 2022/2/12 23:14
     * @param flag 标志是否需要不高位，如果是ture 表示需要补高位，如果是false表示不需要
     * @param b 传入的 byte
     * @return: java.lang.String 返回的b 对应的二进制的字符串（注意事按照补码返回）
     */
    public static String byteToBitString(boolean flag, byte b) {
        //使用变量保存 b
        int temp = b;
        //如果是正数我们还需要补高位
        if (flag) {
            //按位与 256 1 0000 0000| 00000 0001 => 1 0000 0001
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }
    /**
     *
     * @author 冷环渊 Doomwatcher
     * @context: 封装 赫夫曼编码压缩
     * @date: 2022/2/12 20:12
     * @param bytes
     * @return: byte[]
     */
    public static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        Node huffManTreeroot = createHuffManTree(nodes);
        Map<Byte, String> codes = getCodes(huffManTreeroot);
        byte[] huffmanCodeBytes = zip(bytes, codes);
        return huffmanCodeBytes;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 编写一个方法，将字符串转成对应的 Byte[] 数组，通过生成的哈夫曼编码表，返回一个赫夫曼编码压缩后的Byte[]
     * 举例子： string content = i like like like java do you like java
     * 返回的字符串应该是一大串 八位的byte
     * 比如 huffmanCodeBytes[0] = 10101000(补码) => byte[推导 推成反码 10101000 -1 => 10100111（反码）] 原码就是符号位不变，其他取反 [11011000]
     * @date: 2022/2/12 15:35
     * @param bytes        原始字符串对应的byte
     * @param huffmanCodes 生成赫夫曼编码的map
     * @return: java.lang.Byte[]
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //  首先利用 huffmanCode是将 bytes 转成赫夫曼编码的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        //System.out.println(stringBuilder);
        //    将对应的字符串 转成 byte[]数组
        //    返回 数组 huffmancodeBytes的长度
        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;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            if (i + 8 > stringBuilder.length()) {
                //   进入这里代表后面的最后一位数 不够八位了
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }
    /* 生成赫夫曼树对应的赫夫曼编码
     * 思路 ：
     * 1. 将赫夫曼编码存放在map<byte,string>的形式的map里
     * 2。在生成赫夫曼编码表示，需要去拼接一些路径  定一个一个 stringbuilder 存放叶子节点的路径
     * */
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    //存放叶子节点的路径的 stringbuilder
    static StringBuilder stringBuilder = new StringBuilder();
    //为了调用方便 重载getcode
    public static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //  处理左子树
        getCodes(root.left, "0", stringBuilder);
        //处理右子树
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 将传入的node节点的所有子节点的赫夫曼编码得到，并且放入huffmanCodes集合中
     * @date: 2022/2/12 15:07
     * @return: void
     * @param node          传入的节点
     * @param code          路径，左子节点是 0 右子节点事 1
     * @param stringBuilder 用于拼接路径
     */
    public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        //将code 加入到 string builder1
        stringBuilder1.append(code);
        if (node != null) {
            //    如果为null 不处理
            //判断是否为叶子结点
            if (node.data == null) {
                //如果data不为空那么代表非叶子节点
                //   向左继续递归
                getCodes(node.left, "0", stringBuilder1);
                //    向右边递归
                getCodes(node.right, "1", stringBuilder1);
            } else {
                //如果进入到这里说明是一个叶子结点
                //    存入到 huffmanCodes这个集合中
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }
    }
    //前序遍历
    public static void PreOrder(Node node) {
        if (node != null) {
            node.PreOrder();
        } else {
            System.out.println("空树无法遍历");
        }
    }
    /**
     *
     * @author 冷环渊 Doomwatcher
     * @context: 用来生成每一个节点的出现次数的list集合
     * @date: 2022/2/10 2:40
     * @param bytes 存放每一个字母的数组
     * @return: java.util.List<com.hyc.DataStructure.huffmanCode.Node>  返回一个带着字母出现权重的list
     */
    public static List<Node> getNodes(byte[] bytes) {
        //    创建一个 arraylist
        ArrayList<Node> nodes = new ArrayList<>();
        //    遍历bytes 统计每一个bytes 出现的次数 用 map 来统计
        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集合
        //遍历map
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }
    public static Node createHuffManTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //首先从小到大排序 list
            Collections.sort(nodes);
            //    找到list中最小的子树
            Node leftnode = nodes.get(0);
            //找到倒数第二小的
            Node rightnode = nodes.get(1);
            Node parent = new Node(null, leftnode.wight + rightnode.wight);
            parent.left = leftnode;
            parent.right = rightnode;
            //    删除两个被处理过的子树
            nodes.remove(leftnode);
            nodes.remove(rightnode);
            //    之后将parent 加入到list
            //   这样遍历到最后只剩下一个节点 就是我们需要的赫夫曼树
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}
class Node implements Comparable<Node> {
    //用于存放字符的ascll值
    Byte data;
    //出现的次数 权重
    int wight;
    Node left;
    Node right;
    public Node(Byte data, int wight) {
        this.data = data;
        this.wight = wight;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", wight=" + wight +
                '}';
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.PreOrder();
        }
        if (this.right != null) {
            this.right.PreOrder();
        }
    }
    @Override
    public int compareTo(Node o) {
        return this.wight - o.wight;
    }
}

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

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

二叉排序树

先看一个需求:

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

使用数组

数组未排序，优点：直接在数组尾添加，速度快。缺点：查找速度慢.

数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位

置后，后面的数据需整体移动，速度慢。

链式存储-链表

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

二叉排序树介绍

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

特别声明

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

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

二叉排序树创建和遍历

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

建成对应的二叉排序树为 :

二叉排序树的删除

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

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

对删除结点的各种情况的思路分析:

第一种情况: 删除叶子节点 (比如：2, 5, 9, 12)

思路：

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

左子结点 parent.left = null

右子结点 parent.right = null;

第二种情况: 删除只有一颗子树的节点比如 1

思路 :

需求先去找到要删除的结点 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

情况三：删除有两颗子树的节点. (比如：7, 3，10 )

思路 :

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

二叉排序树代码实现

package com.hyc.DataStructure.binarysorttree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.binarysorttree
 * @className: BinarySortDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/15 16:33
 * @version: 1.0
 */
public class BinarySortDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        //    中序要遍历
        binarySortTree.infixOrder();
        //    测试删除节点
        binarySortTree.delNode(2);
        binarySortTree.delNode(7);
        binarySortTree.delNode(3);
        binarySortTree.delNode(12);
        binarySortTree.delNode(5);
        binarySortTree.delNode(1);
        binarySortTree.delNode(9);
        binarySortTree.delNode(10);
        System.out.println("删除节点后");
        //    中序要遍历
        binarySortTree.infixOrder();
    }
}
class BinarySortTree {
    private Node root;
    //查找要删除的节点
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }
    //查找父节点·
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(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;
                }
            } else if (targetNode.left != null && targetNode.right != null) {
                //    删除有两颗子树的节点
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else {
                //    删除有一颗子树
                //    如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    //判断 parent 的非空判断
                    if (parent != null) {
                        //    如果targetNode是Parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            //targentNode 是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 {
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
 
            }
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 返回的以node为根节点的二叉树的最小节点值
     * 删除node 为根节点的二叉排序树的最小节点
     * @date: 2022/2/17 22:19
     * @param node 传入的节点 （当前二叉排序树树的根节点）
     * @return: int 返回的以node为根节点的二叉排序树的最小节点值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //    循环查找左节点 就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这个target就指向了最小的节点
        //删除最小节点
        delNode(target.value);
        return target.value;
    }
    //    添加节点的方法
    public void add(Node node) {
        //如果能空的话
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("空树 无法遍历");
        }
    }
}
class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 找到想要查到要删除的节点
     * @date: 2022/2/17 14:15
     * @param value 想要删除的节点的值
     * @return: com.hyc.DataStructure.binarysorttree.Node 如果找到了就返回节点，如果没找到那就返回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);
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 查找要删除节点的父节点
     * @date: 2022/2/17 14:23
     * @param value value 要找的节点值
     * @return: com.hyc.DataStructure.binarysorttree.Node 返回的事要删除的节点
     */
    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 +
                '}';
    }
    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();
        }
    }
}

平衡二叉树(AVL 树)

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

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

解决方案-平衡二叉树(AVL)

基本介绍

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树，可以保证查询效率较高。
具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
举例说明, 看看下面哪些 AVL 树, 为什么?

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

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

左旋转代码

//左旋转方法
    public void leftRotate() {
        // 创建新节点 以当前节点的值
        Node newnode = new Node(value);
        //    把新节点的左子树这只成当前节点的左子树
        newnode.left = left;
        //    把新节点的右子树设置成当前节点的右子树的左子树
        newnode.right = right.left;
        //把当前节点的值 替换成右子节点的值
        value = right.value;
        //    把当前节点右子树设置成下一个节点的右子树
        right = right.right;
        //    把当前节点的左子树设置成新的节点
        left = newnode;
    }

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

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

右旋转代码

//右旋转方法
    public void rightRotate() {
        Node newnode = new Node(value);
        newnode.right = right;
        newnode.left = left.right;
        value = left.value;
        left = left.left;
        right = newnode;
    }

应用案例-双旋转

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列

int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL 树.

int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL 树

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

代码汇总

package com.hyc.DataStructure.AVL;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.AVL
 * @className: avlTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/18 23:30
 * @version: 1.0
 */
public class avlTreeDemo {
    public static void main(String[] args) {
        //左旋转demo实例
        //int[] arr = {4, 3, 6, 5, 7, 8};
        //右旋转demo实例
        int[] arr = {10, 12, 8, 9, 7, 6};
        //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()); //3
        System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
        System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
        System.out.println("当前的根结点=" + avlTree.getRoot());//8
    }
}
class AVLTree {
    private Node root;
    public Node getRoot() {
        return root;
    }
    public void setRoot(Node root) {
        this.root = root;
    }
    //查找要删除的节点
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }
    //查找父节点·
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(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;
                }
            } else if (targetNode.left != null && targetNode.right != null) {
                //    删除有两颗子树的节点
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else {
                //    删除有一颗子树
                //    如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    //判断 parent 的非空判断
                    if (parent != null) {
                        //    如果targetNode是Parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            //targentNode 是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 {
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 返回的以node为根节点的二叉树的最小节点值
     * 删除node 为根节点的二叉排序树的最小节点
     * @date: 2022/2/17 22:19
     * @param node 传入的节点 （当前二叉排序树树的根节点）
     * @return: int 返回的以node为根节点的二叉排序树的最小节点值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //    循环查找左节点 就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这个target就指向了最小的节点
        //删除最小节点
        delNode(target.value);
        return target.value;
    }
    //    添加节点的方法
    public void add(Node node) {
        //如果能空的话
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("空树 无法遍历");
        }
    }
}
class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
    //左旋转方法
    public void leftRotate() {
        // 创建新节点 以当前节点的值
        Node newnode = new Node(value);
        //    把新节点的左子树这只成当前节点的左子树
        newnode.left = left;
        //    把新节点的右子树设置成当前节点的右子树的左子树
        newnode.right = right.left;
        //把当前节点的值 替换成右子节点的值
        value = right.value;
        //    把当前节点右子树设置成下一个节点的右子树
        right = right.right;
        //    把当前节点的左子树设置成新的节点
        left = newnode;
    }
    //右旋转方法
    public void rightRotate() {
        Node newnode = new Node(value);
        newnode.right = right;
        newnode.left = left.right;
        value = left.value;
        left = left.left;
        right = newnode;
    }
    //返回左子树的高度
    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;
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 找到想要查到要删除的节点
     * @date: 2022/2/17 14:15
     * @param value 想要删除的节点的值
     * @return: Node 如果找到了就返回节点，如果没找到那就返回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);
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context: 查找要删除节点的父节点
     * @date: 2022/2/17 14:23
     * @param value value 要找的节点值
     * @return: Node 返回的事要删除的节点
     */
    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 +
                '}';
    }
    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.leftHeight()) {
                //    先对右子节点，进行右旋转
                right.rightRotate();
                leftHeight();
            } 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();
        }
    }
}

Java数据结构与算法-java数据结构与算法（六）https://developer.aliyun.com/article/1469494

Java数据结构与算法-java数据结构与算法（五）

树结构实际应用

堆排序

堆排序基本介绍

大顶堆

小顶堆

堆排序基本思想

堆排序步骤图解说明

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

代码实现

赫夫曼树

基本介绍

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

赫夫曼树创建思路图解

赫夫曼树的代码实现

赫夫曼编码

基本介绍

原理剖析

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

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

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

最佳实践-文件压缩

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

代码汇总

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

二叉排序树

二叉排序树介绍

二叉排序树创建和遍历

二叉排序树的删除

二叉排序树代码实现

平衡二叉树(AVL 树)

基本介绍

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

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

应用案例-双旋转

代码汇总

热门文章

最新文章

相关课程

相关电子书

相关实验场景