chapter树和叉树.ppt

假设用于通讯的电文仅有8个字母组成，字母在电文中出现的频率分别是： （0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,） 请为这8个字母设计哈夫曼编码，同时画出相对应的哈夫曼树； 计算出这颗哈夫曼树的带权路径WPL。 【试题】（北京邮电大学）假设用于通信的电文由字符集{a, b, c, d, e, f, g}中的字母构成。它们在电文中出现的幅度分别为{0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04}。（1）为这7个字母设计哈夫曼编码。（2）为这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？ 带权路径长度：在树形结构中，我们把从树根到某一结点的路径长度与该结点权的乘积，称做该结点的带权路径长度。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，称为树的带权路径长度，通常记为WPL： WPL=?wi×li i=1 n 其中：n为叶子结点的个数；wi为第i个叶子的权值； li为第i个叶子结点的路径长度。 结点的权：给树中每个结点赋予一个具有实际意义的数值，我们称该数值为这个结点的权。 * 例如下图所示的三棵二叉树 WPL(a)=7×2＋5×2＋2×2＋4×2＝36 其带权路径长度分别为： 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(b)=4×2＋7×3＋5×3＋2×1＝46 WPL(c)=7×1＋5×2＋2×3＋4×3＝35 * 什么样的树的带权路径长度WPL最小？ 例如：给定一个权值序列{2, 4, 5, 7}，可构造多种二叉树的形态: 问题： 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(a) ＝ 36 WPL(b) ＝ 46 WPL(c)＝35 其带权路径长度分别为： * 在各种形态的含有 n个叶子结点的 二 叉树中, 必存在一棵(几棵)其带权路径长度值WPL 最小的树，被称为“最优二叉树” 。 特征：在最优二叉树中没有度数为 1 的结点(可用反证法证明); 含 n个叶子结点的最优二叉树的总结点数为 2*n-1 (依据二叉树性质三)。 最优二叉树的构造方法最早由哈夫曼研究，所以又称为“哈夫曼树”。 * 二、如何构造最优树（哈夫曼算法） Step 1: 根据给定的 n 个权值 {w1, w2, …, wn}， 构造 一个具有n 棵二叉树的森林F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树； Step 2:在 F 中选取其根结点的权值为最小和次小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和； Step 3: 从F中删去这两棵树,同时加入刚生成的新树； Step 4: 重复 2 和 3 两步,直至 F 中只含一棵树为止。 * 例如: 已知权值 W={ 5, 6, 2, 9, 7 } 9 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 构造哈夫曼树如下： 9 5 2 7 16 6 7 13 29 数 据 结 构 6.4 树和森林 第 6 章 树 树与森林的遍历 ①树的遍历 void RootFirst(CSTree root) { if(root!=NULL) { Visit(root-data); RootFirst(root-FirstChild); RootFirst(root-NextSibling); } } 方法1： 先根遍历算法 数 据 结 构 6.4 树和森林 第 6 章 树 树与森林的遍历 ①树的遍历 void RootFirst(CSTree root) { if(root!=NULL) { Visit(root-data); p=root-FirstChild; while(p!=NULL) { RootFirst(p); p=p-NextSibling; } } } 方法2： 先根遍历算法 数 据 结 构 6.4 树和森林 第 6 章 树 树与森林的遍历 ②森林的遍历 若森林不空，则 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中(除第一棵树之外)其余树构成的森林。 先序遍历： G H I J A B C D E F