哈夫曼编码的算法 1.将n个频率为{p1,p2,…,pn}的字符表示为n个 结点,将每个结点看成二叉树T频率p为其 权值w,组成集合F={T,T2 ns ■2.在F中选取两棵权值最小的树作为左、右子 树构造一棵新二叉树,令新二叉树的的权值为 其左、右子树的权值之和 3.在F中删除这两棵树,并加入新的二叉树。 4.重复2和3,直到F中只有一棵树为止 5.约定左、右分支分别为0和1。从根到叶子的 路径的0和1的序列,即该字符的哈夫曼编码 2021/22 计算机算法设计与分析2021/2/21 计算机算法设计与分析 8 哈夫曼编码的算法 ◼ 1. 将n个频率为{p1 , p2 , …, pn}的字符表示为n个 结点，将每个结点看成二叉树Ti，频率pi为其 权值wi，组成集合F = {T1 , T2 , …, Tn}。 ◼ 2. 在F中选取两棵权值最小的树作为左、右子 树构造一棵新二叉树，令新二叉树的的权值为 其左、右子树的权值之和。 ◼ 3. 在F中删除这两棵树，并加入新的二叉树。 ◼ 4. 重复2和3，直到F中只有一棵树为止。 ◼ 5. 约定左、右分支分别为0和1。从根到叶子的 路径的0和1的序列，即该字符的哈夫曼编码