数据结构课件ppt第06章04.ppt

6 8哈夫曼树与哈夫曼编码 最优树的定义如何构造最优树前缀编码赫夫曼编码 一 最优树的定义 树的路径长度定义为 树中每个结点的路径长度之和 结点的路径长度定义为 从根结点到该结点的路径上分支的数目 树的带权路径长度定义为 树中所有叶子结点的带权路径长度之和WPL T wklk 对所有叶子结点 假设有n个权值 w1 w2 wn 构造一棵有n个叶子结点的二叉树 每个叶子结点带权为Wi 则其中带权路径长度取最小值的二叉树称为 最优树 例如 2 79 7 5 4 9 2 WPL T 7 2 5 2 2 3 4 3 9 2 60 WPL T 7 4 9 4 5 3 4 2 2 1 89 5 4 根据给定的n个权值 w1 w2 wn 构造n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树中均只含一个带权值为wi的根结点 其左 右子树为空树 二 如何构造最优树 1 赫夫曼算法 以二叉树为例 在F中选取其根结点的权值为最小的两棵二叉树 分别作为左 右子树构造一棵新的二叉树 并置这棵新的二叉树根结点的权值为其左 右子树根结点的权值之和 2 从F中删去这两棵树 同时加入刚生成的新树 重复 2 和 3 两步 直至F中只含一棵树为止 3 4 9 例如 已知权值W 5 6 2 9 7 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 01 10 110 111 从根结点到叶子结点的路径上分支字符组成的字符串 可以作为每个叶子结点编码 约定左分支表示字符 0 右分支表示字符 1 若要设计不等长的编码 则必须任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀 这种编码称为前缀编码 三 前缀编码 以传送的电文为例比较等长编码和不等长编码方法 一 等长编码 电文中所需传送的字符有A B C D 编码分别为00 01 10 11 若要发送 ABACCDA 电文 则以字符串 00010010101100 发送 根据字符对应的编码 在接收端能知道发送的电文为 ABACCDA 二 不等长编码 当A B C D的编码分别为0 00 1 10 要发送上述电文以电文 ABACCDA 相应的字符串为 000011100 在接收端 对于子串 0000 的译法就有多种 可以是 AAAA BB ABA BAA 等等 四 赫夫曼编码 如何得到使电文总长最短的二进制前缀编码呢 假设每种字符在电文中出现的次数为wi 其编码长度为li 电文中只有n种字符 则电文总长为 wili 对应到二叉树上 置wi为叶子结点的权 li为根到叶子的路径长度 则 wili恰为二叉树上带权路径长度 设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权 设计一棵赫夫曼树的问题 由此得到的二进制前缀编码称为赫夫曼编码 利用赫夫曼树可以构造一种不等长的二进制编码 并且构造所得的赫夫曼编码是一种最优前缀编码 即使所传电文的总长度最短 例6 2 1 熟练掌握二叉树的结构特性 了解相应的证明方法 2 熟悉二叉树的各种存储结构的特点及适用范围 3 遍历二叉树是二叉树各种操作的基础 实现二叉树遍历的具体算法与所采用的存储结构有关 掌握各种遍历策略的递归算法 灵活运用遍历算法实现二叉树的其它操作 层次遍历是按另一种搜索策略进行的遍历 4 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系 熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法 二叉树的线索化过程是基于对二叉树进行遍历 而线索二叉树上的线索又为相应的遍历提供了方便 5 熟悉树的各种存储结构及其特点 掌握树和森林与二叉树的转换方法 建立存储结构是进行其它操作的前提 因此读者应掌握1至2种建立二叉树和树的存储结构的方法 6 学会编写实现树的各种操作的算法 7 了解最优树的特性 掌握建立最优树和哈夫曼编码的方法 复习题 一棵完全二叉树上有1001个结点 其中叶子结点的个数是 250500254505以上答案都不是答案 E 以下说法错误的是 存在这样的二叉树 对它采用任何次序遍历其结点访问序列均相同 二叉树是树的特殊情形 由树转换成二叉树 其根结点的右子树总是空的 在二叉树只有一棵子树的情况下 也要明确指出该子树是左子树还是右子树 答案 B 树的基本遍历策略可分为先根遍历和后根遍历 二叉树的基本遍历策略分为先序 中序和后序三种遍历 我们把由树转化得到的二叉树称该树对应的二叉树 则下面 是正确的 树的先根遍历序列与其对应的二叉树先序遍历序列相同 树的后根遍历序列与其对应的二叉树后序遍历序列相同 树的先根遍历序列与其对应的二叉树中序遍历序列相同 以上均不对 答案 A 下面几个符号串编码集合中 不是前缀编码的是 0 10 110 1111 11 10 001 101 0001 00 010 0110 1000 b c aa ac aba abb abc 答案 B 对于前序遍历与中序遍历结果相同的二叉树为 对于前序遍历和后序遍历结果相同的二叉树为 一般二叉树只有根结点的二叉树根结点无左孩子的二叉树根结点无右孩子的