算法中-哈夫曼树（树的带权路径长度（wpl））

这里写目录标题

• 哈夫曼树
• • 基本介绍
  • 赫夫曼树几个重要概念
  • • 权值
    • 路径长度
    • 带权路径长度
    • wpl
    • 根据频率构建赫夫曼树的步骤如下/分析过程：
    • 代码实现
    • 运行���果

      哈夫曼树

      基本介绍

      • 哈夫曼树是一种带权路径长度最短的树，也称为最优二叉树。它是由美国数学家哈夫曼（David A. Huffman）于1952年提出的，在数据压缩、编码和密码学等领域得到了广泛应用。

      • 哈夫曼树的构造过程是将一组权值作为叶子节点，通过不断合并两个权值最小的节点生成新的父节点，直到最终只剩下一个根节点为止。合并的过程中，新的父节点的权值等于其左右子节点权值之和。构造完成后，从根节点到每个叶子节点的路径都对应着该叶子节点的编码，路径上左转表示编码0，右转表示编码1。

      • 通过哈夫曼树的编码方式，可以实现对文本等数据的高效压缩和解压缩，同时保证信息的完整性和准确性。

        赫夫曼树几个重要概念

        在理解赫夫曼树时，有几个重要概念需要掌握：

        权值

        • 权值（Weight）：指的是赫夫曼树中每个节点所携带的权重，通常表示节点代表的字符在文本中出现的频率或者其他权重信息。

          路径长度

          • 路径长度（Path Length）：指的是从根节点到某个节点之间所经过的边的数量。对于赫夫曼树而言，通常使用节点的权值乘以路径长度来衡量节点的贡献。

            带权路径长度

            • 带权路径长度（Weighted Path Length）：指的是某个节点的路径长度与其权值的乘积，用来衡量整棵赫夫曼树的压缩效率。带权路径长度越小，则压缩效率越高。

              wpl

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

                根据频率构建赫夫曼树的步骤如下/分析过程：

                举例说明：

                假设有如下字符集合及其频率：

                字符：A B C D E F

                频率：5 9 12 13 16 45

                将所有节点按照频率从小到大排序。5 9 12 13 16 45

                • 选取频率最小的两个节点（A和B），合并生成新节点AB，其权值为5+9=14。
                • 将节点AB插入到节点集合中，并重新按照权值排序。
                • 重复以上步骤，直至所有节点合并为一棵赫夫曼树。
                • 最终得到的赫夫曼树如下所示：

                  在这棵赫夫曼树中，各节点的权值即为其代表的字符在文本中的频率，通过路径上的编码可以实现对字符的编码和解码，从而实现数据的高效压缩和解压缩。

                  代码实现

                  package com.atguigus.huffmantree;import java.util.ArrayList;import java.util.Collections;public class HuffmanTree {    public static void main(String[] args) {        int arr[] = {13,7,8,3,29,6,1};        Node node = createHuffmanTree(arr);        //前序排序        node.preOrder();    }    public static void preOrder(Node root){        if (root != null) {            root.preOrder();        }else {            System.out.println("树是空树");        }    }    public static Node createHuffmanTree(int[] arr){        //把数组中的每一个元素都存放到ArrayList中        ArrayList nodes = new ArrayList();        for (int value : arr) {            nodes.add(new Node(value));        }        //处理的是一个循环的过程        while (nodes.size() > 1) {            //排序从小到大            Collections.sort(nodes);//            System.out.println(String.format("nodes=%s", 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;            //删除原本的值            nodes.remove(leftNode);            nodes.remove(rightNode);            //添加和            nodes.add(parent);        }        //这个时候只有一个值了        return nodes.get(0);    }}class Node implements Comparable{    int value ;    Node left;    Node right;    //写一个前序遍历    public void preOrder(){        System.out.println(this);        if (this.left != null) {            this.left.preOrder();        }        if (this.right != null) {            this.right.preOrder();        }    }    public Node(int value) {        this.value = value;    }    @Override    public String toString() {        return "Node{" +                "value=" + value +                '}';    }    @Override    public int compareTo(Node o) {        //小到大排序        return this.value - o.value;    }}

                  运行结果

                  E:\jdk\jdk1.8.0_161\bin\java.exe "-javaagent:D:\IDEA\IntelliJ IDEA 2022.2.1\lib\idea_rt.jar=55423:D:\IDEA\IntelliJ IDEA 2022.2.1\bin" -Dfile.encoding=UTF-8 -classpath E:\jdk\jdk1.8.0_161\jre\lib\charsets.jar;E:\jdk\jdk1.8.0_161\jre\lib\deploy.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\access-bridge-64.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\cldrdata.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\dnsns.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\jaccess.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\jfxrt.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\localedata.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\nashorn.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunec.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunjce_provider.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunmscapi.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunpkcs11.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\zipfs.jar;E:\jdk\jdk1.8.0_161\jre\lib\javaws.jar;E:\jdk\jdk1.8.0_161\jre\lib\jce.jar;E:\jdk\jdk1.8.0_161\jre\lib\jfr.jar;E:\jdk\jdk1.8.0_161\jre\lib\jfxswt.jar;E:\jdk\jdk1.8.0_161\jre\lib\jsse.jar;E:\jdk\jdk1.8.0_161\jre\lib\management-agent.jar;E:\jdk\jdk1.8.0_161\jre\lib\plugin.jar;E:\jdk\jdk1.8.0_161\jre\lib\resources.jar;E:\jdk\jdk1.8.0_161\jre\lib\rt.jar;D:\课程\java课程\guiGu_suanFa\out\production\guiGu_suanFa com.atguigus.huffmantree.HuffmanTreeNode{value=67}Node{value=29}Node{value=38}Node{value=15}Node{value=7}Node{value=8}Node{value=23}Node{value=10}Node{value=4}Node{value=1}Node{value=3}Node{value=6}Node{value=13}Process finished with exit code 0