数据结构 6树与二叉树D.ppt

第6章 树和二叉树（ Tree Binary Tree ）;6.5 Huffman树及其应用;Huffman树：;路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： 霍 夫 曼 树：;(1) 由给定的 n 个权值{w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二叉树的森林F = { T0, T1, T2, …, Tn-1 }，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。;操作要点1：对权值的合并、删除与替换 ——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权;操作要点2：按左0右1对Huffman树的所有分支编号！;例2（严题集6.26③）：假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？;w4={19, 21, 28, 32};;对应的哈夫曼编码（左0右1）：;另一种结果表示：;二叉树的应用;例3（实验三，可选）：设字符集为26个英文字母，其出现频度如下表所示。;提示1：霍夫曼树中各结点的结构可以定义为如下5个分量：