6.6哈夫曼编码.ppt

先介绍二叉树的典型应用 平衡树 排序树 字典树 带权树 最优树 由字符串构成的二叉排序树特点 路径带权值 例如长度 是带权路径长度最短的树 又称Huffman树 用途之一是通信中的压缩编码 特点 所有结点左右子树深度差 1 特点 所有结点 左小右大 什么是平衡二叉树 又称AVL树 性质 所有结点左 右子树深度之差的绝对值 1若定义结点的 平衡因子 BF 左子树深度 右子树深度则 平衡二叉树中所有结点的BF 1 0 1 a 平衡树 b 不平衡树 例 判断下列二叉树是否AVL树 1 1 1 1 2 1 1 什么是二叉排序树 a b 例 下列2种图形中 哪个不是二叉排序树 或是一棵空树 或者是具有如下性质的非空二叉树 1 左子树的所有结点均小于根的值 2 右子树的所有结点均大于根的值 3 它的左右子树也分别为二叉排序树 想一想 对它中序遍历之后是什么效果 什么是带权树 即路径带有权值 例如 6 5Huffman树及其应用 一 Huffman树二 Huffman编码 最优二叉树 Huffman树 Huffman编码 带权路径长度最短的树 不等长编码 是通信中最经典的压缩编码 一 Huffman树 最优二叉树 路径 路径长度 树的路径长度 带权路径长度 树的带权路径长度 Huffman树 由一结点到另一结点间的分支所构成 路径上的分支数目 从树根到每一结点的路径长度之和 结点到根的路径长度与结点上权的乘积 WPL 若干术语 即树中所有叶子结点的带权路径长度之和 带权路径长度最小的树 例如 a e的路径长度 树长度 2 10 Huffman常译为赫夫曼 霍夫曼 哈夫曼等 WeightedPathLength 树的带权路径长度如何计算 经典之例 WPL WPL WPL Huffman树是WPL最小的树 树中所有叶子结点的带权路径长度之和 36 46 35 2 构造Huffman树的步骤 即Huffman算法 1 由给定的n个权值 w1 w2 wn 构成n棵二叉树的集合F T1 T2 Tn 即森林 其中每棵二叉树Ti中只有一个带权为wi的根结点 其左右子树均空 2 在F中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树 且让新二叉树根结点的权值等于其左右子树的根结点权值之和 3 在F中删去这两棵树 同时将新得到的二叉树加入F中 4 重复 2 和 3 直到F只含一棵树为止 这棵树便是Huffman树 1 构造Huffman树的基本思想 权值大的结点用短路径 权值小的结点用长路径 WPL最小的树 举例 对权值进行合并 删除与替换 在权值集合 7 5 2 4 中 总是合并当前值最小的两个权 a 初始 方框表示外结点 叶子 字符 圆框表示内结点 合并后的权值 b 合并 2 4 c 合并 5 6 d 合并 7 11 Huffman树的特点 没有度为1的结点 二 Huffman编码 假设我们发送的电文为 ABACCD 它只有四个字符 只需要2位二进制编码A 00B 01C 10D 11发送电文的序列为000100101011在传送电文时 希望总长度尽量短 因此出现次数多的字符适用短的编码 A 0B 00C 1D 11发送电文的序列为00001111可以解释为AAAACCCC AABDD BBCCCC 我们必须使用前缀编码 PrefixCode PrefixCode前缀码 任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀 如ABCD四个字符的前缀编码分别为A 0B 10C 110D 111 可以利用二叉树来设计前缀编码 假设每种字符在电文中出现的次数为wi 其编码长度为li 电文中只有n种字符 则电文总长为 若置wi为叶子结点的权 li恰为从根到叶子的路径长度 则恰为二叉树上带权路径长度 如何得到使电文总长最短的前缀编码 利用赫夫曼树可以构造一种不等长的二进制编码 并且构造所得的赫夫曼编码是一种最优前缀编码 即使所传电文的总长度最短 按左 0 右 1 对Huffman树的所有分支编号 Huffman编码结果 d 0 i 10 a 110 n 111WPL 1bit 7 2bit 5 3bit 2 4 35 小于等长码的WPL 36 特征 每一码不会是另一码的前缀 译码时可惟一复原 Huffman编码也称为前缀码 将Huffman树与Huffman编码挂钩 例 设有4个字符d i a n 出现的频度分别为7 5 2 4 怎样编码才能使它们组成的报文在网络中传得最快 法1 等长编码 如二进制编码 令d 00 i 01 a 10 n 11 则 WPL1 2bit 7 5 2 4 36法2 不等长编码 如Huffman编码 令d 0 i 10 a 110 n 111 则 明确 要实现Huffman编码 就要先构造Huffman树 讨论 Huffman树有什么用 频度高的信息用短码 反之用长码 传输效率肯定高 WPL2 1bit 7 2bit 5 3bit 2 4 35 最小冗余编码 信息高效传输 A 1B 00C 011D 0101E 0100 例 假设字符A B C D E的出现概率为42 28 15 10 5 求电文的总长度最短的一种编码 首先构建赫夫曼树 根据概率 1 由于Huffman树的WPL最小 说明编码所需要的比特数最少 4 Huffman编码时是从叶子走到根 而译码时又要从根走到叶子 因此每个结点需要增开双亲指针分量 连同结点权值共要开5个分量 5 用计算机实现时 顺序和链式两种存储结构都要用到 分析Huffman树和编码的特点 霍夫曼编码的基本思想是 出现概率大的信息用短码 概率小的用长码 最小冗余 这种编码已广泛应用于网络通信中 2 Huffman树肯定没有度为1的结点 3 一棵有n0个叶子结点的Huffman树 共有2n0 1个结点 因为n n0 n1 n2 2n0 1 如何编程实现Huffman编码 建议1 Huffman树中结点的结构可设计成5分量形式 将整个Huffman树的结点存储在一个数组HT 1 n m 中 各叶子结点的编码存储在另一 复合 数组HC 1 n 中 建议2 Huffman树的存储结构可采用顺序存储结构 typedefstruct unsignedintweight 权值分量 可放大取整 unsignedintparent lchild rchild 双亲和孩子分量 HTNode HuffmanTree 用动态数组存储Huffman树typedefchar HuffmanCode 动态数组存储Huffman编码表 Huffman树和Huffman树编码的存储表示 双亲 HuffmanTree或HT向量 HT 3 parent 9 指针型指针 如何编程实现Huffman编码 参见教材P147 先构造Huffman树HT 再求出N个字符的Huffman编码HC VoidHuffmanCoding HuffmanTree HT HuffmanCode HC int w intn if n 1 return m 2 n 1 n0个叶子的HuffmanTree共有2n0 1个结点 HT HuffmanTree malloc m 1 sizeof HTNode 0单元未用 w存放n个字符的权值 for p HT i 1 i n i p w p w 0 0 0 给前n0个单元初始化for i m i p p 0 0 0 0 对叶子之后的存储单元清零for i n 1 i m i 建Huffman树 从叶子后开始存内结点 Select HT i 1 s1 s2 在HT 1 i 1 选择parent为0且weight最小的两个结点 其序号分别为S1和s2 教材未给出此函数源码 HT s1 parent i HT s2 parent i HT i lchild s1 HT i rchild s2 HT i weight HT s1 weight HT s2 weight 续前 再求出n个字符的Huffman编码HC HC HuffmanCode malloc n 1 sizeof char 分配n个字符编码的头指针向量 一维数组 cd char malloc n sizeof char 分配求编码的工作空间 n cd n 1 0 编码结束符 从cd 0 cd n 1 为合法空间 for i 1 i n i 逐个字符求Huffman编码start n 1 编码结束符位置for c i f HT i parent f 0 c f f HT f parent 从叶子到根逆向求编码if HT f lchild c cd start 0 elsecd start 1 HC i char malloc n start sizeof char 为第i个字符编码分配空间strcpy HC i 释放工作空间 HuffmanCoding Huffman编码举例 解 先将概率放大100倍 以方便构造哈夫曼树 放大后的权值集合w 7 19 2 6 32 3 21 10 按哈夫曼树构造规则 合并 删除 替换 可得到哈夫曼树 例1 严题集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的二进制编码方案又如何 类同P148例2 b c a d e g f h 5 11 17 28 40 60 100 1415 w 7 19 2 6 32 3 21 10 请注意 哈夫曼树样式不惟一 w 7 19 2 6 32 3 21 10 在机内存储形式为 b a d e g f h 5 11 17 28 40 60 100 0 1415 如何形成编码 例如 c的编码 从叶结点开始 找到其双亲 判定是双亲的左孩子或右孩子 确定编码 直到根结束 0 0 1 1 1 c 对应的哈夫曼编码 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 3 0 19 0 32 0 21 0 07 0 06 0 10 0 02 0 03 3 二进制等长码的WPL c 按左0右1标注 另一种表示 小结 哈夫曼树及其应用 1 Huffman算法的思路 权值大的结点用短路径 权值小的结点用长路径 2 构造Huffman树的步骤 对权值的合并 删除与替换 3 Huffman编码规则 左 0 右 1 又称为前缀码 最小冗余编码 紧致码等等 它是数据压缩学的基础 上机实验说明 设字符集为26个英文字母 其出现频度如下表所示 注 若在规定时间内圆满实现 平时成绩将以满分计 要求 先建Huffman树 再利用此树对任一字符串文件进行编码和译码 即设计一个Huffman编 译码器 本章小结 1 定义和性质 2 存储结构 3 遍历 4 线索化 1 2 性质有3 2条 孩子 兄弟 线索树 第6章结束 1 熟练掌握二叉树的结构特性 了解相应的证明方法 2 熟悉二叉树的各种存储结构的特点及适用范围 3 遍历二叉树是二叉树各种操作的基础 实现二叉树遍历的具体算法与所采用的存储结构有关 掌握各种遍历策略的递归算法 灵活运用遍历算法实现二叉树的其它操作 层次遍历是按另一种搜索策略进行的遍历 本章重点 4 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系 熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法 二叉树的线索化过程是基于对二叉树进行遍历 而线索二叉树上的线索又为相应的遍历提供了方便 5 熟悉树的各种存储结构及其特点 掌握树和森林与二叉树的转换方法 建立存储结构是进行其它操作的前提 因此应掌握1至2种建立二叉树和树的存储结构的方法 6 学会编写实现树的各种操作的算法 7 了解最优树的特性 掌握建立最优树和哈夫曼编码的方法 判定一个结构是否为二叉树给出二叉树的遍历序列画出某树的线索二叉树树 二叉树 森林的相互转换 并由一个结构的特点推到出其余结构的特点由已知的某个权值序列求出Huffman树并计算其带权路径长度由已知的某个权值序列求其Huffman编码相关算法的编写 2 如何按层次输出二叉树中所有结点 算法思路 既然要求从上到下 从左到右 则利用队列存放各子树结点的指针是个好办法 此时绝不能用递归算法 技巧 当根结点入队后 令其左 右孩子结点入队 而左孩子出队时又令它的左右孩子结点入队 由此便可产生按层次输出的效果 附 二叉树若干典型算法 习题课 1 如何求二叉树的深度 或从某个结点开始的子树深度 算法思路 只查各结点后继链表指针 若左 右 孩子的左 右 指针非空 则层次数加1 否则函数返回 算法见附1 算法见附2 算法思路 若不用递归 则要实现二叉树遍历的 嵌套 规则 必用堆栈 迭代方式 可直接用while语句和push pop操作 参见教材P130 131程序 4中序遍历的非递归算法如何实现 3 如何判别给定二叉树是否为完全二叉树 算法思路 完全二叉树的特点是 没有左子树空而右子树单独存在的情况 前k 1层都是满的 且第k层左边也满 技巧 按层次遍历方式 先把所有结点 不管当前结点是否有左右孩子 都入队列 若为完全二叉树 则层次遍历时得到的肯定是一个连续的不包含空指针的序列 如果序列中出现了空指针 则说明不是完全二叉树 算法见附3 算法见附4 VoidABC Bitreep intl int 法1 从根开始向下计算层次 比从叶子往上计算更简单 l h分别表示二叉树的层次数和深度 想一想 l和h的初始值应设为多少 开始调用时 应当用ABC p 0 0 若去掉h形参中的 号 则h不变化 算出的更深层数不能正确返回 h将永远为0 附1 求二叉树的深度的算法严题集6 44 intBTreeDepth Btree BT BT为二叉树某结点的指针 intleftdep rightdep 设左右两个深度 层次计数器if BT NULL return 0 当前结点指针为空则立即返回else leftdep BTreeDepth BT left 遍历当前结点左子树rightdep BTreeDepth BT right 遍历当前结点右子树if leftdep rightdep return leftdep 1 从叶子起计数elsereturn rightdep 1 BTreeDepth 法2 递归时从叶子开始向上计数 层深者保留 voidLayerOrder BitreeT 层序遍历二叉树 InitQueue Q 建一个空队 初始化队列 EnQueue Q T 将一个结点插入队尾的函数while QueueEmpty Q DeQueue Q p的右孩子入队 LayerOrder 附2 层次遍历算法 需要利用队列 严题集6 47 当孩子为空时不要将空指针入队 附3 判别给定二叉树是否为完全二叉树严题集6 49 intIsFull Bitree BitreeT 是完全二叉树返回1 否则返0 InitQueue Q 建队 初始化队列 flag 0 标志初始化EnQueue Q T 结点T入队 空指针也要入队 while QueueEmpty Q DeQueue Q 执行至此必为队空且中间无空指针 完全二叉 IsFull Bitree StatusInOrderTrav BiTreeT Status Visit TElemTypee 此处Visit意思是对元素e的一种操作InitStack S p T 初始化栈while p StackEmpty S 树不空或栈不空则开始遍历 if p Push S p p p lchild 根指针进栈 遍历左子树else Pop S p 根指针退栈if Visit p data returnERROR 访问根结点p p rchild 遍历右子树 else whilereturnOK InOrderTrav 附4 中序遍历的非递归算法 或称迭代算法 见教材P131 1 设高度为h的二叉树上只有度为0的结点和度为2的结点 则此类二叉树所包含的结点数至少为 至多为 2h 1 2h 1 2 如图所示的二叉树的中序遍历序列是 dfebagc 3 已知某二叉树的后序遍历序列是dabec 中序遍历序列是debac 则它的前序遍历序列是 cedba 4 已知某二叉树的前序遍历序列是abdgcefh 中序遍历序列是dgbaechf 则其后序遍历序列是 gdbehfca 5 某二叉树的前序序列为stuwv 中序序列为uwtvs 则其后序序列为 wuvts 6 任何一棵二叉树的叶结点在先序 中序和后序遍历序列中的相对次序 A不发生改变B发生改变C不能确定 A 7 实现任意二叉树的后序遍历的非递归算法而不使用栈结构 最佳方案是二叉树采用 存储结构A二叉链表B广义表C三叉链表D顺序存储 C 8 线索二叉树是一种 结构A逻辑B逻辑和存储C物理D线性 C 9 一棵二叉树的结点的数据结构采用顺序存储 见数组t 则其二叉链表表示形式为 10 按自上而下 从左到右的次序给深度为k的完全二叉树的结点编号 根结点编号为1 则编号最小的叶子结点的编号为 2k 2 1 11 一棵有n个结点的满二叉树总共有 个叶子 有 个非终端结点 2h 1 其中 n 2h 1 2h 1 1 12 现有某二叉树的中序遍历序列为abc 问可以有 种不