从树中一个节点到另一个节点之间的分支构成两个节点之间的「路径」。
路径上的分支数目称为「路径长度」。如图所示，根节点到节点D的路径长度为4。
树的路径长度就是从树根到每一个节点的路径长度之和
树的路径长度
设二叉树具有n个带权值的叶子节点，那么从根节点到各个叶子节点的路径长度l与相应节点权值的w乘积的和，叫做二叉树的「带权路径长度」
其中，将具有最小带权路径长度的二叉树称为「哈夫曼树」，也称最优树
构造哈夫曼树构造原则
权值越大的叶子节点越要靠近根节点权值越小的叶子节点越要远离根节点现有序列{A5,B15,C40,D30,E10}，字母后的数字为权重，构造哈夫曼树
以权值递增顺序重新排列A5，E10，B15，D30，C40
取序列中前两个权值最小的节点作为新节点N1的两个孩子节点，权值小的是左孩子，权值大的是右孩子
新节点N1的权值是两个孩子节点的权值之和，即5+10=15。用(N1)15替换A5和E10，插入到有序序列中，保持从小到大排列(N1)15，B15，D30，C40
取前两个权值最小的节点(N1)15，B15用(N2)30替换(N1)15和B15，插入到有序序列中(N2)30，D30，C40
取前两个权值最小的节点(N2)30，D30
用(N3)60替换(N2)30和D30，插入到有序序列中，注意保持从小到大的排列C40，(N3)60
取前两个权值最小的节点C40，(N3)60替换完成后序列只有N4一个节点，哈夫曼树构造完成哈夫曼树的特点哈夫曼树没有单分支节点，即度为1的节点n1的数目等于0
所以
哈夫曼编码
哈夫曼树的目的是解决电报数据传输的最优化问题
现有序列DBACADFEED采用二进制来传输信息
ABCDEF得到新序列111
采用哈夫曼编码的方法，先分析字符在字符串中的权重
占比放大倍的权值A0.B0.1C0.1D0.E0.F0.1构造哈夫曼树规定哈夫曼树中的左分支为0，右分支为1从根节点到每个叶子节点所经过的分支对应的0和1组成的序列便为该节点对应字符的编码。这样的编码称为「哈夫曼编码」。
A00B1C1D11E01F得到哈夫曼编码1111111
可以看出比原来少了5个字符，节约了约17%的存储或传输成本。
前缀编码在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀。上面的表格就不存在容易与1混淆的
没有两个字符的编码相同没有两个字符编码的前缀相同相关习题例15个字符有如下4种编码方法，其中不是前缀编码的是
A.01，0，1，，1
B.，，，，1
C.，，，，
D.0，，，1，1
D选项中和1前缀重复，不是前缀编码
例2对n(n≥2)个权值均不同的字符构成哈夫曼树，关于该树的叙述中，错误的是
A.该树一定是一棵完全二叉树
B.该树中一定没有度为1的节点
C.树中两个权值最小的节点一定是兄弟节点
D.树中任一非叶子节点的权值一定不小于下一层任一节点的权值
选A
例3如果一棵哈夫曼树T中共有个节点，那么该树用于对几个字符进行哈夫曼编码？
解：哈夫曼树没有度为1的节点
n=2n0-1推出n0=
按照哈夫曼树的定义，叶子节点即为字符，所以该树用于对个字符进行哈夫曼编码。
预览时标签不可点收录于话题#个上一篇下一篇