最优二叉树(哈夫曼树)
(1)树的路径长度: 指从树根到树中每一个结点的路径长度之和。
(2)在结点数目相同的二叉树中,路径长度最短的是: 完全二叉树。
(3)结点的权: 在一些应用中,赋予树中结点的一个有某种意义的实数。
(4)带权路径长度(树的代价):结点到树根的路径 乘以 该结点上的权,
通常记为:
注:完全二叉树:除最后一层可能不满以外,其他各层都达到该层节点的最大数,最后一层如果不满,该层所有节点都全部靠左排;
满二叉树:所有层的节点数都达到最大。
(5)哈夫曼树的原理:
在构造哈夫曼树的过程中,每次都是选取两棵最小权值的二叉树进行合并,因此使用的是贪心算法。
(6)给定结点序列<ci,pi>(ci为编码字符,pi为ci的频度),哈夫曼编码的过程如下:
.用字符ci作为叶子,pi作为ci的权,构造一棵哈夫曼树,并将树中的左分支和右分支分别标记为0和1;
.将从根到叶子的路径上的标号依次相连,作为该叶子所表示字符的编码。该编码为最优前缀码。
.求哈夫曼编码的具体实现过程是依次以叶子结点c[i]为出发点,向上回溯至根为止。
.由于生成的编码与要求的编码反序,将生成的编码先从后往前依次存放在一个临时串中,并设一个指针start指示编码在该串中的首位置。
.当某字符编码完成时,从临时串的start处将编码复制到该字符相应的位串bits中即可。
.因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符“\0“,bits的大小应为n+1。
(7)前缀码:(不存在一个序列是另一个序列的前缀的情况的)一个序列的集合。
(8)最优的前缀码:平均码长或文件总长最小的前缀码。
(9)对文件的压缩效果最佳的编码:最优的前缀码。
(10)哈夫曼树的应用:可以优化通信管道的利用率。