08级第06章树和二叉树D.pptVIP

调课通知 因同学们下周（12周）星期二晚有物理实验考试，故下周二晚《数据结构》课程推迟一天，改动如下： 时间：12周周三下午7-8节 地点：东九楼D107 注： 下周四下午5-6节课程照常进行。 请互相转告！ 附：二叉树若干典型算法（习题课）4例 * 第6章?? 树和二叉树 作业（共11题） 6.5 6.8 6.17 6.25 6.26 6.29 （今晚交） 6.42 6.43 6.47 6.49 6.65 （下周二交） 方案一：二叉树的建立和遍历 具体内容：先生成一棵二叉树，再用中序遍历方式打印每个结点值，并统计其叶子结点的个数。 方案二：哈夫曼树的建立和编码器的实现 具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫曼编码。 方案三：哈夫曼编/译码器的设计与实现 具体内容：参见严题集P149 实习5.2要求，或参见自测卷 本周四晚 第二次上机内容预告： （三个方案由易到难，可自选，参见自测题集实验二资料） 实验报告要求 实验报告格式要求：见《数据结构》题集（C语言版）P75 ?三、实习报告规范 除题目、班级、姓名、学号、完成日期外，还要有7项内容： 1、 需求分析 2、 概要设计 3、 详细设计 4、 调试分析 5、 用户使用说明 6、 测试结果 7、 附录（带注释的源程序） 实验报告按百分制打分： 程序正常跑通： 40分 界面友好及健壮性：20分 源码有30%注释： 20分 有实验报告格式： 20分 * * 第6章 树和二叉树（Tree Binary Tree） 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 6.5 Huffman树及其应用 一、Huffman树 最优二叉树 Huffman树 带权路径长度(WPL)最短的树 树的带权路径长度如何计算？ WPL = ?wklk k=1 n 树中所有叶子结点的带权路径长度之和 * 回顾： 2.Huffman算法的思路： ——权值大的结点用短路径，权值小的结点用长路径。 3.构造Huffman树的步骤： ——对权值的合并(叶子靠左） 、删除与替换 4. Huffman编码规则： 左“0” 右“1” ——又称为前缀码、最小冗余编码、紧致码等等，它是数据压缩学的基础。 * 1.Huffman编码的基本思想： 出现概率大的信息用短码，概率小的用长码,达到最小冗余 今日重点：如何编程实现Huffman编码？ 建议1：Huffman树中结点的结构可设计成4或5分量形式： char weight parent lchild rchild 将整个Huffman树的结点存储在一个数组HT[1..n..m]中; （Huffman树内外结点总数m=2n-1） 各叶子结点的编码存储在另一“复合”数组HC[1..n]中。 (n个权值/叶子将对应n个不同长度的码串) 建议2： Huffman树的存储结构大胆采用顺序存储结构： 即：先构造Huffman树HT 再求出n个权值/字符的Huffman编码HC 参见教材P147 * m=n0+n2=n+(n-1)=2n-1 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】 * 10 7 17 0 0 0 — 0 0 0 — 0 0 0 — 0 0 0 — 0 0 0 —- 0 0 0 0 0 0 0 0 r 0 0 10 0 0 21 0 0 3 0 0 32 0 0 6 0 0 2 0 0 19 0 0 7 l p w 13 12 10 11 9 8 7 6 5 4 3 2 1 w={ 7, 19, 2, 6, 32, 3, 21, 10 }在机内存储形式为: 2 3 5 28 21 19 40 100 b c a 11 6 d 60 32 e g f h 请注意：哈夫曼树样式不惟一，编程时应该有约定，“先来先挂接” √ √ 5 9 9 √ √ 11 10 10 4 9 17 28 √ √ √ √ √