哈夫曼树（赫夫曼树、最优树）及C语言实现.docx
90 浏览量
2023-11-10
09:40:47
上传
评论
收藏 114KB DOCX 举报
哈夫曼树（赫夫曼树、最优树）及 C 语言实现
赫夫曼树，别名“哈夫曼树”、“最优树”以及“最优二叉树”。学习哈夫曼树之前，首
先要了解几个名词。
哈夫曼树相关的几个名词
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到
结点 a 之间的通路就是一条路径。
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规
定根结点所在层数为 1 层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从
根结点到结点 c 的路径长度为 3。
结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点
a 的权为 7，结点 b 的权为 5。
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例
如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如
图 1 中所示的这颗树的带权路径长度为：
WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3
剩余15页未读，继续阅读
资源评论
