【专题】哈夫曼树、带权路径、哈夫曼编码

目录

• 一、哈夫曼树

• • 1. 研究目的
  • 2. 相关定义

• 二、构造哈夫曼树

• • 1. 构造步骤
  • 2. 例题

• 二、求带权路径长度

• • 1. 计算公式
  • 2. 例题

• 三、哈夫曼编码

• • 1. 编码规则
  • 2. 例题

• 四、练习题

• • 1. 练习题一
  • 2. 练习题二
  • 3. 练习题三
  • 4. 练习题四

一、哈夫曼树

1. 研究目的

• 霍夫曼树也被称为最优二叉树，并属于一类带权路径长度最小 的数据结构。
• 最优二叉树：给定n个权重{w₁,w₂,…,wₙ}时，在构造一棵具有n个外部节点（叶子）的二叉_tree中，并使第i个外部节点对应的权重为wᵢ，则称其具有最小带权路径长度的那个_binary tree即为最优_binary tree。

2. 相关定义

• 两节点之间的路径：树中任意两节点之间的分支集合；
  • 两节点之间的距离：分支数量作为度量标准；
  • 权值：赋予不同节点的重要程度数值；
  • 树的距离：从根节点到各节点的所有距离之和；
  • 结点带权距离：该结点至根节点的距离乘以相应权值；
    叶子结点i的带权距离=wi*li

树的加权路径总长：对于每一个叶子节点而言其加权路径总长等于各权重与其相应深度乘积之和。
最优二叉树的加权路径总长等于\sum_{i=1}^{n}w_i*l_i

二、构造哈夫曼树

1. 构造步骤

• 第一步：基于给定的n个权重值，在系统中创建一个包含n棵独立二叉树的数据集合F = {T₁, T₂, …, Tₙ}；
• 第二步：从集合F中筛选出具有最小权重及次小权重的两棵独立二叉树作为左右子树，并构建一个新的合并后的二叉树；该新生成的二叉树其根节点权重等于左右子树根节点权重之和；
• 第三步：从集合F中删除这两棵被选中的独立二叉树，并将生成的新合并后的二叉树重新加入到数据集合F中；
• 第四步：循环执行上述第二至第三步直至数据集合F中只剩下一棵独立最优结构的二叉树为止。

2. 例题

W＝{2，4，5，3} 赫夫曼树的构造过程

【注意事项】

由具有相同权重的叶子节点构建的不同赫夫曼树可能结构各异（即不唯一），然而这些不同构造出的所有赫夫曼树其总路径长度保持一致；
当选择两棵根节点权重最低与次低时（即两棵根节点权重相同的多棵树），若遇到权重相同的多棵树，则可以选择其中任意一棵作为后续构建的基础；
最优二叉树结构中不存在度数为一（即度为一）的情况（即度为一的情况不存在），它仅包含n片叶节点以及n−1个内部节点（也即非终端节点），总计有2n−1个节点；

二、求带权路径长度

1. 计算公式

在任意一棵树中，在该结构下各叶子节点与其至根节点的距离乘积之总和即被称作该树的带权路径长度，并简称为WPL。 最优二叉树构造的带权路径长度被定义为\sum_{i=1}^{n}wi*li

2. 例题

WPL=4*2+5*2+2*2+3*2=28

WPL=2*4+3*4+4*3+9*2+7*2+8*2=80

三、哈夫曼编码

1. 编码规则

• 字符由叶子节点表示；
  • 左边分支代表0码单位；
  • 右边分支代表1码单位；
  • 通过从根节点到特定叶节点路径上的各条边所对应的二进制位序列构成该叶节点对应字符的编码。

2. 例题

【编码】：A 0；B 110；C 10；D 111

【编码】：3（0111） 5（0110） 7（1110） 8（1111）
11（010） 14（110） 23（00） 29（10）

四、练习题

1. 练习题一

（1）利用给定的{2,5,7,9,13}作为二叉树中叶子结点所具有的权值信息来构建一棵哈夫曼编码树。
（2）求取上述构建好的哈夫曼编码树所具有的带权路径长度总和。
（3）生成该哈夫曼编码树对应的哈夫曼编码规则。

2. 练习题二

（1）基于集合{5,6,7,8,15}构建一棵哈夫曼树用于表示叶子结点权值。
（2）求解上述赫夫曼树的路径代价参数。
（3）生成该赫夫曼树对应的Aloha协议编码方案。

3. 练习题三

用于通信的电文中包含8个不同字母c₁至c₈，在电文中这些字符分别出现了5次、25次、3次、6次、10次、11次、36次以及4次。请设计相应的不等长Huffman编码方案，并计算该电文使用此编码后的总码数。

4. 练习题四

已知某系统在通信联络中只可能出现8种字符，其概率为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,设计赫夫曼编码。