数据结构中的赫夫曼树

定义

赫夫曼编码为字符提供代码，代码长度取决于相应字符的相对频率或权重。赫夫曼编码采用可变长度，且无任何前缀（即任何代码都不是其他代码的前缀）。任何无前缀的二进制代码都可以表示为二叉树，其中编码的字符存储在叶节点。

赫夫曼树或赫夫曼编码树定义为一棵满二叉树，其中树的每个叶节点对应于给定字母表中的一个字母。

赫夫曼树被视为具有最小外部路径权重的二叉树，即它与给定叶节点集的加权路径长度总和最小。因此，目标是构建一棵具有最小外部路径权重的树。

举例说明：

字母频率表

赫夫曼编码

霍夫曼树（对于上述示例）如下所述 -

Arnab Chakraborty

更新于：2020 年 1 月 16 日

1.2 万+ 浏览次数

开启你的 职业生涯

通过完成课程获得认证

开始