精品计算机课件《C语言数据结构》第章树和二叉树.pptVIP

6.2.2　二叉树的性质 (3+2) 6.3.2 线索二叉树 为识别复用的两种不同信息，特增加两个标志域： 1. 有关线索二叉树的几个术语： 例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。 例1：画出以下二叉树对应的中序线索二叉树。 例2：【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 线索二叉树的生成算法（递归算法见教材P134-135） 3. 线索二叉树的遍历（无需堆栈） 附：中序线索二叉树遍历步骤 （算法6.5）： 算法流程： 什么是带权树？ a b d c 7 5 2 4 即叶子带有权值。例如： 最优二叉树(哈夫曼树) 如果是带权路径长度最短的树 * 6.6 Huffman树及其应用 一、Huffman树 二、Huffman编码 最优二叉树 Huffman树 Huffman编码 带权路径长度最短的树 不等长编码 是通信中最经典的压缩编码 * 树的带权路径长度如何计算？ WPL = ?wklk k=1 n a b d c 7 5 2 4 (a) c d a b 2 4 5 7 (b) b d a c 7 5 2 4 (c) 经典之例： WPL= WPL= WPL= Huffman树是WPL 最小的树 树中所有叶子结点的带权路径长度之和 36 46 35 * 一、 Huffman树（最优二叉树） 路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： Huffman树： 由一结点到另一结点间的分支所构成。 路径上的分支数目。 从树根到每一结点的路径长度之和。 结点到根的路径长度与结点上权的乘积（WPL） 若干术语： d e b a c f g 即树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。 例如：a→e的路径长度＝ 树长度＝ 2 10 Huffman常译为赫夫曼、霍夫曼、哈夫曼、胡夫曼等 Weighted Path Length * 1. 构造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树有什么用？ 权值大的结点用短路径，权值小的结点用长路径。 WPL最小的树 频度高的信息用短码，低的用长码，传输效率肯定高！ WPL2=1bit×7＋2bit×5+3bit×(2+4)=35 最小冗余编码、信息高效传输 * step1：对权值进行合并、删除与替换 ——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权 先介绍Huffman树的具体构造步骤： a. 初始 方框表示外结点（叶子，字符） 圆框表示内结点（合并后的权值） b. 合并{2} {4} c. 合并{5} {6} d. 合并{7} {11} 谁左谁右？若不规定就会不惟一 * step2：按左“0”右“1” 对Huffman树的所有分支编号 d a i n 1 1 1 0 0 0 Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1bit×7＋2bit×5+3bit(2+4)=35（小于等长码的WPL=36） 特征：每一码不会是另一码的前缀，译码时可惟一复原 Huffman编码也称为前缀码 ——将 Huffman树 与 Huffman编码 挂钩 * 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树。 怎样证明它就是WPL最小的最优二叉树？参考《信源编码》 总之，每次合并当前值最小的两个权。 (此树特征：没有度为1的结点) * 思考：若权值相同，先合并哪个？ 思考：Huffman编码举例 解：先将概率放大100倍，以方便构造哈夫曼树。 放大后的权值集合 w={ 7, 19, 2, 6, 32, 3, 21, 10 }，