哈夫曼树的构造与编码
    哈夫曼树的构造与编码
    哈夫曼树（Huffman Tree），又称最优二叉树，是一种常用的用于编码的统计学方法，是一类带权路径长度最短的树，也是一种最佳编码树，它结合了熵的概念和二叉树的特性，以此来将一系列的无序字母进行高效的编码。
    哈夫曼树的构造
    哈夫曼树是根据每个字符出现的概率建立的最佳编码树，最后生成的编码满足最短编码原理。
    建立哈夫曼树的步骤如下：
    1）根据给定的数据，统计每个字符出现的频率，将频率作为权值；
    2）把每个字符都转换成一个结点，然后放到一个集合中；哈夫曼编码树的带权路径长度
    3）从集合中取出权值最小的两个结点，作为父节点，然后将这两个结点从集合中删除；
    4）创建一个新的结点，将这两个节点作为新结点的左右孩子，新结点的权值为两个孩子的权值之和；
    5）重复步骤3和4，直到集合中只有一个结点，最后这一个结点就是哈夫曼树的根结点。
    哈夫曼编码
    哈夫曼编码（Huffman Coding）是一种用来实现最优编码的数据结构，它的编码满足最短编码原则，在哈夫曼树中，采用“左孩子0，右孩子1”的方式来编码，比如有字符A、B、C，且有相应的结点，经过构建哈夫曼树的过程后，可以得到如下的编码结果：
    字符  编码
    A  0
    B  10
    C  11
    由此可见，可以根据哈夫曼树的构建，编码字符串，来达到减少消息传递时所耗费的空间。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。