数据结构哈夫曼树和哈夫曼编码ppt课件.ppt

6 8哈夫曼树与哈夫曼编码 1 哈夫曼树与哈夫曼编码2 回溯策略3 4 例题讲解5 课堂练习6 作业 6 8哈夫曼树与哈夫曼编码 1 最优二叉树的定义2 如何构造最优二叉树3 前缀编码 树的路径长度定义为 最优二叉树的定义 从根结点到该结点的路径上分支的数目 结点的路径长度定义为 树中每个结点的路径长度之和 树的路径长度为5 最优二叉树的定义 树的带权路径长度定义为 7 5 2 4 9 WPL T 7 2 5 2 2 3 4 3 9 2 60 最优二叉树的定义 7 4 9 5 2 WPL T 7 4 9 4 5 3 4 2 2 1 89 最优二叉树的定义 最优二叉树定义为 带权路径长度WPL最小的二叉树 又称为哈夫曼树 例如 已知权值W 5 6 2 9 7 9 5 6 2 7 7 6 9 7 13 9 5 2 7 6 1 2 3 5 2 7 哈夫曼树 WPL 2 3 5 3 6 2 7 2 9 2 65 哈夫曼树 7 13 9 5 2 7 6 4 16 7 13 9 5 2 7 6 5 16 29 练习 已知权值W 5 6 2 9 8 9 5 6 2 8 7 6 8 6 5 2 7 1 2 3 5 2 9 哈夫曼树 8 9 13 4 5 WPL 2 3 5 3 6 2 8 2 9 2 67 哈夫曼树 6 5 2 7 8 9 13 17 6 5 2 7 8 9 13 17 30 哈夫曼树 哈夫曼算法 以二叉树为例 1 根据给定的n个权值 w1 w2 wn 构造n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树中均只含一个带权值为wi的根结点 其左 右子树为空树 2 在F中选取其根结点的权值为最小的两棵二叉树 分别作为左 右子树构造一棵新的二叉树 并置这棵新的二叉树根结点的权值为其左 右子树根结点的权值之和 哈夫曼树 3 从F中删去这两棵树 同时将刚生成的新树加入到F中 4 重复 2 和 3 两步 直至F中只含一棵树为止 哈夫曼树 哈夫曼树 特点 1 有n个叶子结点2 没有度为1的结点3 总的结点数为2n 14 深度 n 15 形态不唯一 编码 编码 用二进制数表示字符 例如 ASCII码 扩展的ASCII码 特点 等长编码 编码 假设有8个符号 a0a1a2a3a4a5a6a7 000001010011100101110111 0001 前缀编码 有时候 每个字符出现的频率不一样 采用变长编码 使得出现频率多的编码短 频率低的编码长 假设A0 4B0 3C0 2D0 1 ABCD 010001 0001011 前缀编码 任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀 利用哈夫曼树可以构造一种不等长的二进制编码 并且构造所得的哈夫曼编码是一种最优前缀编码 即 所传电文的总长度最短 前缀编码 ABCDE 67259 假设有5个符号以及它们的频率 求前缀编码 0 1 0 1 0 0 1 1 00 01 100 101 11 前缀编码 1 建立哈夫曼树 2 对边编号 3 求出叶子结点的路径 4 得到字符编码 ABCDE 67259 000110010111 前缀编码 如何译码 1 ADECB ABCDE 000110010111 回朔策略 假设问题的解为n元组 x1 x2 xn 其中xi取值于集合Si n元组的子组 x1 x2 xi i n 称为部分解 应满足一定的约束条件 对于已求得的部分解 x1 x2 xi 若在添加xi 1 Si 1之后仍然满足约束条件 则得到一个新的部分解 x1 x2 xi 1 之后继续添加xi 2 Si 2并检查之 回朔策略 若对于所有取值于集合Si 1的xi 1都不能得到新的满足约束条件的部分解 x1 x2 xi 1 则从当前自组中删去xi 回溯到前一个部分解 x1 x2 xi 1 重新添加那些值集Si中尚未考察过的xi 看是否满足约束条件 如此反复进行 直到求得满足约束条件的问题的解 或者证明问题无解 回朔策略 皇后问题求解 设四皇后问题的解为 x1 x2 x3 x4 其中 xi i 1 2 3 4 Si 1 2 3 4 约束条件为 其中任意两个xi和xj不能位于棋盘的同行 同列及同对角线 回朔策略 皇后问题求解 按回溯法的定义 皇后问题求解过程为 解的初始值为空 首先添加x1 1 之后添加满足条件的x2 3 由于对所有的x3 1 2 3 4 都不能找到满足约束条件的部分解 x1 x2 x3 则回溯到部分解 x1 重新添加满足约束条件的x2 4 依次类推 回朔策略 皇后问题求解 voidTrial inti intn 进入本函数时 在n n棋盘前i 1行已放置了互不攻击的i 1个棋子 现从第i行起继续为后续棋子选择满足约束条件的位置 当求得 i n 的一个合法布局时 输出之 if i n 输出棋盘的当前布局 elsefor j 1 j n j 在第i行第j列放置一个棋子 if 当前布局合法 Trial i 1 n 移去第i行第j列的棋子 trial 回朔策略 回溯法求解的算法一般形式 voidB inti intn 假设已求得满足约束条件的部分解 x1 xi 1 本函 数从xi起继续搜索 直到求得整个解 x1 x2 xn if i n elsewhile Empty Si 从Si中取xi的一个值vi Si if x1 x2 xi 满足约束条件B i 1 n 继续求下一个部分解从Si中删除值vi B 回朔策略 求幂集 A B C AB AC BC ABC 回朔策略 求幂集 000 100 000 010 100 110 000 001 010 011 100 101 110 111 000 回朔策略 求幂集 voidpowerSet intnum if num len 1 for inti 0 i 2 i if i 0 mask num 1 elsemask num 0 powerSet num 1 else for intj 0 j len j if mask j 1 printf c set j printf n 回朔策略 求幂集 intlen 3 intmask 0 0 0 charset A B C intmain intargc char argv powerSet 0 return0 章末复习 1 熟练掌握二叉树的结构特性 了解相应的证明方法 2 熟悉二叉树的各种存储结构的特点及适用范围 3 遍历二叉树是二叉树各种操作的基础 实现二叉树遍历的具体算法与所采用的存储结构有关 掌握各种遍历策略的递归算法 灵活运用遍历算法实现二叉树的其它操作 层次遍历是按另一种搜索策略进行的遍历 章末复习 4 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系 熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法 二叉树的线索化过程是基于对二叉树进行遍历 而线索二叉树上的线索又为相应的遍历提供了方便 章末复习 5 熟悉树的各种存储结构及其特点 掌握树和森林与二叉树的转换方法 建立存储结构是进行其它操作的前提 因此应掌握1至2种建立二叉树和树的存储结构的方法 6 学会编写实现树的各种操作的算法 7 了解最优树的特性 掌握建立最优树和哈夫曼编码的方法 例题讲解 1 在结点个数为n n 1 的各棵树中 1 高度最小的树的高度是多少 它有多少个叶结点 多少个分支结点 2 高度最大的树的高度是多少 它有多少个叶结点 多少个分支结点 答案 1 结点个数为n时 高度最小的树的高度为2 有2层 它有n 1个叶结点 1个分支结点 2 高度最大的树的高度为n 有n层 它有1个叶结点 n 1个分支结点 例题讲解 2 试分别找出满足以下条件的所有二叉树 1 二叉树的前序序列与中序序列相同 2 二叉树的中序序列与后序序列相同 3 二叉树的前序序列与后序序列相同 解答 1 二叉树的前序序列与中序序列相同 空树或缺左子树的单支树 2 二叉树的中序序列与后序序列相同 空树或缺右子树的单支树 3 二叉树的前序序列与后序序列相同 空树或只有根结点的二叉树 例题讲解 3 深度为k 根的层次为1 的完全二叉树至少有多少个结点 至多有多少个结点 k与结点数目n之间的关系是什么 分析 由完全二叉树的定义可知 对于k层的完全二叉树 其上的k 1层是一棵深度为k 1的满二叉树 所以对于所有深度为k的完全二叉树 它们之间的结点数目之差等于各树最后一层的结点数目之差 例题讲解 3 深度为k 根的层次为1 的完全二叉树至少有多少个结点 至多有多少个结点 k与结点数目n之间的关系是什么 解答 深度为k的完全二叉树 其最少的结点数 深度为k 1的满二叉树的结点数 1 其最多的结点数 深度为k的满二叉树的结点数 k与结点数目n之间的关系可以根据二叉树的性质4得出 例题讲解 4 对于深度为h 且只有度为0或2的结点的二叉树 结点数至少有多少 至多有多少 分析 分析 对于结点数至多为多少的问题比较好回答 我们知道满二叉树中只有度为0或2的结点 所以结点数至多为同等深度的满二叉树的结点数 对于结点数至少为多少的问题 由于树中只存在度为0或2的结点 即对一个结点而言 要么它没有子结点 要么就有两个子结点 所以在这样的树中 除第一层 根所在的层 外 每一层至少有两个结点 例题讲解 5 已知一棵二叉树的中序序列为BDCEAFHG 后序序列为DECBHGFA 求对应的二叉树 分析 分析 根据各种遍历方法的定义 可知 二叉树先序序列 根 左子树先序序列 右子树先序列 二叉树中序序列 左子树中序序列 根 右子树中序列 二叉树后序序列 左子树后序序列 右子树后序序列根 例题讲解 5 已知一棵二叉树的中序序列为BDCEAFHG 后序序列为DECBHGFA 求对应的二叉树 分析 分析 从先序和后序序列中可以很容易的知道那一个结点是根 而在中序序列中 可以根据根得到左 右子树的中序序列 相应的也就知道左 右子树的结点集合了 可以根据集合中的结点划分先序或后序序列中除根以外的结点序列 从而得到左 右子树的先序或后序序列 依次类推 便可以递归得到整棵二叉树 例题讲解 5 已知一棵二叉树的中序序列为BDCEAFHG 后序序列为DECBHGFA 求对应的二叉树 分析 解答 构造这棵二叉树的过程如下所示 可以画出这棵二叉树为 例题讲解 例题讲解 1 二叉树的先序遍历和中序遍历为 先序遍历 EFHIGJK 中序遍历 HFIEJKG 该二叉树根的右子树的根是 A EB FC GD H 答案 1 C2 B3 D 2 某二叉树结点的对称序 中序 序列为ABCDEFG 后序序列为BDCAFGE 该二叉树结点的前序序列为 A EGFACDBB EACBDGFC EAGCFBDD EGACDFB 3 如果一棵二叉树结点的前序序列是ABC 后序序列是CBA 则该二叉树结点的对称序序列A 必为ABCB 必为ACBC 必为BCAD 不能确定 6 分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态 并判断下列论述是否正确 为什么 1 二叉树是一种特殊的树 2 度为2的树是一棵二叉树 3 度为2的有序树是一棵二叉树 解答 具有3个结点的树有两种形态 如图1所示 而具有3个结点的二叉树有5种形态 如图2所示 例题讲解 6 分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态 并判断下列论述是否正确 为什么 1 二叉树是一种特殊的树 2 度为2的树是一棵二叉树 3 度为2的有序树是一棵二叉树 答案 1 错误 例题讲解 2 错误 3 错误 7 在二叉树结点的先序序列 中序序列和后序序列中 所有叶子结点的先后顺序A 都不相同B 先序和中序相同 而与后序不同C 完全相同D 中序和后序相同 而与先序不同8 在完全二叉树中 若一个结点只有一个子结点 则它没A 左子结点B 左子结点和右子结点C 右子结点D 左子结点 右子结点和兄弟结点9 在下列存储形式中 哪一个不是树的存储形式A 双亲表示法B 孩子链表表示法B 孩子兄弟表示法D 顺序存储表示法 答案 课堂练习 7 C 8 C 9 D 10 在树中 一个结点的直接子结点的个数称为该结点的 11 如果对于给定的一组权值 所构造出的二叉树的带权路径长度最小 则该树称为 12 用数组A 1 n 顺序存储完全二叉树的各结点 则当i n 1 2时 结点A i 的右孩子是结点 13 完全二叉树中某结点无左子树 则它必是 课堂练习 度 哈夫曼树 Huffman A 2i 1 叶子 14 对于如图所示的森林 1 将其转换为相应的二叉树 2 写出该森林的先序遍历序列和中序遍历序列 课堂练习 答案 先序序列为 ABDEFCGHIJKL中序序列为 DEFBCAHIJGLK 课堂练习 15 已知一棵树的先根遍历序列为ABCED 后根遍历序列为BECDA 求对应的树 分析 分析 根据树与二叉树之间的转换关系 可知 树的先序序列 对应二叉树先序序列树的后跟序列 对应二叉树中序序列因此 可以先这两个序列构造对应的二叉树 再将二叉树转换为树 课堂练习 15 已知一棵树的先根遍历序列为ABCED 后根遍历序列为BECDA 求对应的树 分析 答案 课堂练习 16 设电文中出现的字母为A B C D和E 每个字母在电文中出现的次数分