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

1 第6章树和二叉树 Tree BinaryTree 6 1树的基本概念6 2二叉树6 3遍历二叉树和线索二叉树6 4树和森林6 5赫夫曼树及其应用 2 6 5Huffman树及其应用 例1 设有4个字符d i a n 出现的频度分别为7 5 2 4 怎样编码才能使它们组成的报文在网络通信中处理最快 法1 等长编码 例如用二进制编码来实现 取d 00 i 01 a 10 n 11 3 Huffman树 树的带权路径长度如何计算 设有4个字符d i a n 出现的频度分别为7 5 2 4 WPL 36 WPL 46 WPL 35 Huffman树 法2 不等长编码 例如用哈夫曼编码来实现 取d 0 i 10 a 110 n 111 4 路径 路径长度 树的路径长度 带权路径长度 树的带权路径长度 霍夫曼树 6 5Huffman树及其应用 一 最优二叉树 霍夫曼树 由一结点到另一结点间的分支所构成 路径上的分支数目 从树根到每一结点的路径长度之和 结点到根的路径长度与结点上权的乘积 树中所有叶子结点的带权路径长度之和 带权路径长度WPL最小的树 a e的路径长度 树长度 2 10 怎样实现Huffman编码 先要构造Huffman树 5 1 由给定的n个权值 w0 w1 w2 wn 1 构造具有n棵扩充二叉树的森林F T0 T1 T2 Tn 1 其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点 其左 右子树均为空 2 重复以下步骤 直到F中仅剩下一棵树为止 在F中选取两棵根结点的权值最小的扩充二叉树 做为左 右子树构造一棵新的二叉树 置新的二叉树的根结点的权值为其左 右子树上根结点的权值之和 在F中删去这两棵二叉树 把新的二叉树加入F 构造霍夫曼树的基本思想 构造Huffman树的步骤 即Huffman算法 权值大的结点用短路径 权值小的结点用长路径 6 操作要点1 对权值的合并 删除与替换 在权值集合 7 5 2 4 中 总是合并当前值最小的两个权 构造Huffman树的步骤 注 方框表示外结点 叶子 字符对应的权值 圆框表示内结点 合并后的权值 7 操作要点2 按左0右1对Huffman树的所有分支编号 Huffman编码结果 d 0 i 10 a 110 n 111WPL 1bit 7 2bit 5 3bit 2 4 35 特点2 每一码都不是另一码的前缀 绝不会错译 称为前缀码 将Huffman树与Huffman编码挂钩 特点1 不存在度为1的结点 8 例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的二进制编码方案又如何 霍夫曼编码的基本思想是 概率大的字符用短码 概率小的用长码 由于霍夫曼树的WPL最小 说明编码所需要的比特数最少 这种编码已广泛应用于网络通信中 解 先将概率放大100倍 以方便构造哈夫曼树 权值集合w 7 19 2 6 32 3 21 10 按哈夫曼树构造规则 合并 删除 替换 可得到哈夫曼树 9 w4 19 21 28 32 为清晰起见 重新排序为 w 2 3 6 7 10 19 21 32 5 6 w1 5 6 7 10 19 21 32 w2 7 10 11 19 21 32 w3 11 17 19 21 32 11 17 28 w5 28 32 40 w6 40 60 w7 100 哈夫曼树 a7 b19 c2 d6 e32 f3 g21 h10 10 L1 7 L8 14 32 63 L8 14 46 95 11 对应的哈夫曼编码 左0右1 Huffman码的WPL 2 0 19 0 32 0 21 4 0 07 0 06 0 10 5 0 02 0 03 1 44 0 92 0 25 2 61 WPL 3 0 19 0 32 0 21 0 07 0 06 0 10 0 02 0 03 3 二进制码 12 另一种结果表示 13 二叉树的应用 平衡树 排序树 判定树 字典树 带权树 最优树 左右子树深度差 1 左小右大 查找判断由字符串构成的二叉树排序树路径长度带权值带权路径长度最短的树 又称Huffman树 用途之一是通信中的压缩编码 14 例3 实验三 可选 设字符集为26个英文字母 其出现频度如下表所示 注 若圆满实现了此方案 平时成绩将以满分计 先建哈夫曼树 再利用此树对报文 Thisprogramismyfavorite 进行编码和译码 要求编程实现 15 提示1 霍夫曼树中各结点的结构可以定义为如下5个分量 将整个霍夫曼树的结