chapter_tree/summary/

[giscus[bot]]

chapter_tree/summary/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_tree/summary/

[yuqiaoqiao]

什么时候可以继续讲一下红黑树、哈夫曼树、B树、B+树、B-树等~

[krahets]

近期不会了，任务队列已爆..

[bukexiusi]

希望提高红黑树的优先级

[krahets]

收到🫡

[08822407d]

今年内核把红黑树全换成枫树了，惨 红黑树 惨

[zhuasdfg]

小结太好了

[WhiteRhinos]

哈夫曼树进行编码

     //根节点
     public HuffmanNode root;
     //编码表
     public HashMap<Byte, String> codingForm;

 /**
     * 根据key-value创建huffman编码树
     * 和之前的一样不过加入的data
     *
     * @param counter 节点信息
     */
    public void createCodingTree(HashMap<Byte, Integer> counter)
    {
        // 管理节点
        ArrayList<HuffmanNode> huffmanNodes = new ArrayList<>();
        // 创建节点
        for (Byte key : counter.keySet())
        {
            huffmanNodes.add(new HuffmanNode(key, counter.get(key)));
        }

        // 最后会剩下一个根节点
        while (huffmanNodes.size() > 1)
        {
            // 1.按照权值对节点排序
            huffmanNodes.sort(new Comparator<HuffmanNode>()
            {
                @Override
                public int compare(HuffmanNode o1, HuffmanNode o2)
                {
                    return o1.weight - o2.weight;
                }
            });

            // 2.构建二叉树
            // 2.1.获取权值最小的两个节点
            HuffmanNode first = huffmanNodes.get(0);
            HuffmanNode second = huffmanNodes.get(1);
            // 2.2.创建父节点
            HuffmanNode parent = new HuffmanNode(first.weight + second.weight);
            // 2.3.构建二叉树
            parent.left = first;
            parent.right = second;

            // 3.删除两个节点并将父节点加入
            huffmanNodes.remove(0);
            huffmanNodes.remove(0);
            huffmanNodes.add(parent);
        }

        this.root = huffmanNodes.get(0);
    }

    /**
     * 建立编码表
     * 编码为向左为0向右为1
     */
    public void createCodingForm(String code, HuffmanNode node)
    {
        // 叶节点
        if (node.data != null)
        {
            // 添加
            codingForm.put(node.data.byteValue(), code);
            return;
        }

        StringBuilder codeTemp = new StringBuilder(code);
        // 记录左编码
        codeTemp.append(0);
        createCodingForm(codeTemp.toString(), node.left);
        // 删除左编码添加右编码
        codeTemp.delete(codeTemp.length() - 1, codeTemp.length());
        codeTemp.append(1);
        createCodingForm(codeTemp.toString(), node.right);
    }

[WhiteRhinos]

    /**
     * huffman编码
     */
    public static void test2()
    {
        // 1.获取构建节点的信息(weight是出现次数和data是字符的ascii)
        String content = "Truly reliable code doesn't depend on human nature";
        // content = "压缩数据和解压数据";
        // content = "a bbcccddddeeeee";
        byte[] bytes = content.getBytes();
        // 节点信息
        HashMap<Byte, Integer> counter = new HashMap<>();
        for (byte aByte : bytes)
        {
            // key不存在就添加,存在value就++
            counter.merge(aByte, 1, Integer::sum);
        }

        HuffmanTree huffmanTree = new HuffmanTree();
        // 2.创建huffman树
        huffmanTree.createCodingTree(counter);
        // huffmanTree.levelOrder(huffmanTree.root);
        // 3.获取huffman编码
        huffmanTree.createCodingForm("", huffmanTree.root);
        System.out.println("数据编码表为:" + huffmanTree.codingForm);

        // 4.压缩数据
        byte[] zByte = zip(bytes, huffmanTree.codingForm);
        System.out.println("压缩后的数据:" + Arrays.toString(zByte));
        //数据中重复元素越多压缩后长度越短
        System.out.println("原长度:"+bytes.length);
        System.out.println("压缩后长度:"+zByte.length);
        // 5.解压数据
        String zipContnet = unzip(zByte, huffmanTree.codingForm);
        System.out.println(zipContnet);
    }

    /**
     * 压缩数据
     *
     * @param bytes      数据
     * @param codingForm 编码表
     * @return 压缩完毕数据
     */
    public static byte[] zip(byte[] bytes, HashMap<Byte, String> codingForm)
    {
        System.out.println("--------压缩开始--------");
        StringBuilder zContent = new StringBuilder();
        for (byte aByte : bytes)
        {
            zContent.append(codingForm.get(aByte));
        }
        System.out.println("压缩数据编码:" + zContent.toString());
        // 将zContent每8位转换为一个byte存入
        int len = zContent.length() % 8 == 0 ? zContent.length() / 8 : zContent.length() / 8 + 1;
        byte[] zBytes = new byte[len + 1];
        int time = 0;
        while (zContent.length() >= 8)
        {
            // 截取8位
            String substring = zContent.substring(0, 8);
            zContent.delete(0, 8);
            // 转byte
            zBytes[time++] = (byte) Integer.parseUnsignedInt(substring, 2);
        }
        if (zContent.length() > 0)
        {
            zBytes[time] = (byte) Integer.parseUnsignedInt(zContent.substring(0), 2);
            // 最后一位存放剩余长度,用于还原编码的时候处理最后一位
            zBytes[time + 1] = (byte) zContent.length();
        }
        System.out.println("--------压缩结束--------");
        return zBytes;
    }

    /**
     * 解压数据
     *
     * @param zBytes     压缩数据
     * @param codingForm 编码表
     * @return 解压数据
     */
    public static String unzip(byte[] zBytes, HashMap<Byte, String> codingForm)
    {
        System.out.println("--------开始解压--------");
        // 1.获取数据编码
        StringBuilder codes = new StringBuilder();
        for (int i = 0; i < zBytes.length - 1; i++)
        {
            String code;
            // 判断最后一位是否需要化为8位
            if (zBytes[zBytes.length - 1] != 0 && i == zBytes.length - 2)
            {
                code = Integer.toBinaryString(zBytes[i]);
            }
            else
            {
                // 截取8位(与256做与运算得到9位,后8位为原值)
                code = Integer.toBinaryString(zBytes[i] | 256);
                code = code.substring(code.length() - 8);
            }
            codes.append(code);
        }
        System.out.println("解压数据编码:" + codes);
        // 2.根据数据表解压数据
        // 2.1翻转编码表,后面要根据编码获取值(因为key和value都是唯一的所以可以)
        HashMap<String, Byte> map = new HashMap<>();
        codingForm.forEach((key, value) ->
                           {
                               map.put(value, key);
                           });
        // 2.2获取对应的byte,存入队列
        Queue<Byte> queue = new LinkedList<>();
        int len = 0;
        String s = "";
        while (len < codes.length())
        {
            // 截取一个字符
            s += codes.substring(len, len + 1);
            Byte aByte = map.get(s);
            if (aByte != null)
            {
                queue.offer(aByte);
                s = "";
            }
            len++;
        }
        // 2.3.获取结果
        byte[] contentBytes = new byte[queue.size()];
        for (int i = 0; i < contentBytes.length; i++)
        {
            contentBytes[i] = queue.poll();
        }
        String content = new String(contentBytes);

        System.out.println("--------解压结束--------");
        return content;
    }

[WhiteRhinos]

原来的还有瑕疵,在解压的时候还原编码有bug

[WhiteRhinos]

for (int i = 0; i < zBytes.length - 1; i++)
        {
            String code;
            // 判断最后一位是否需要化为8位
            if (zBytes[zBytes.length - 1] != 0 && i == zBytes.length - 2)
            {
                // 根据zBytes还原最后一位的位数
                int bit = 2 << zBytes[zBytes.length - 1] - 1;
                code = Integer.toBinaryString(zBytes[i] | bit);
                code = code.substring(code.length() - zBytes[zBytes.length - 1]);
            }
            else
            {
                // 截取8位(与256做与运算得到9位,后8位为原值)
                code = Integer.toBinaryString(zBytes[i] | 256);
                code = code.substring(code.length() - 8);
            }
            // System.out.println(code);
            codes.append(code);
        }

[Chenyuyang7]

没有B树和B+树吗？

[krahets]

暂时没有

[ItsFated]

有没有三叉树和四叉树，多叉树？

[hpstory]

Hi @ItsFated , 多叉树与二叉树的实现比较类似，可以参考二叉树修改节点的类，或者创建有向图的方式实现。

[1435646097]

有的，这都属于N叉树了，比如B树，B+树

[Jinjin680]

K神，催更红黑树、B+树等

[HuaWang135608]

Over

[daiDai-study]

打卡

[Dannytaotao]

2024.5.17 finish.