【数据结构】哈夫曼树
一、基本概念
-
路径：从一个结点到另一个结点之间的分支序列
-
路径长度：从一个结点到另一个结点所经过的分支数量
-
结点的权：有某种现实含义的数值（如：表示结点的重要性等）
-
结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
- 例如叶子结点中权为3的带权路径长度就是 3*3 = 9
-
树的带权路径长度：树中所有叶子结点的带权路径长度之和（WPL）
- 例如
这颗树的带权路径长度为：
21 + 23 + 24 +25 = 26
- 例如
这颗树的带权路径长度为：
13 + 33 + 24 + 51 = 25
这颗树的带权路径长度为：
15 + 33 + 31 + 24 = 25
这颗树的带权路径长度为：
11 + 23 + 3 5 + 34 = 34
- 在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树
二、 哈夫曼树的构造
另一种构造方法：
三、 哈夫曼树的性质
- 每个初始结点最终都成为叶结点，且权值越小的结点的到根结点的路径长度越大
- 哈夫曼树的结点总数为 2n – 1 (n为叶子结点数量)
- 哈夫曼树中不存在度为 1 的结点
- 哈夫曼树并不唯一，但WPL必然相同且为最优
四、 哈夫曼编码
- 规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符编码。这样的编码称为哈夫曼编码。
- 哈夫曼编码的特点：权值越大的字符编码越短，反之越长
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/204349.html
