09级第6章树D(习题课).pptVIP

附：二叉树若干典型算法（习题课）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要求，或参见自测卷 下周一晚 第二次上机内容预告： （三个方案由易到难，可自选，参见自测题集实验二资料） 上机实验说明：设字符集为26个英文字母，其出现频度如下表所示。 51 48 1 15 63 57 20 32 5 1 频度 z y x w v u t 字符 1 16 1 18 8 23 80 频度 p 21 f q 15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符 要求：先建Huffman树，再利用此树对任一字符串文件进行编码和译码——即设计一个Huffman编/译码器 * 实验报告要求 实验报告格式要求：见《数据结构》题集（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 赫夫曼树及其应用 回顾：如何编程实现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 2. 如何按层次输出二叉树中所有结点？ 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，此时绝不能用递归算法。 技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。 1. 如何求二叉树的深度，或从某个结点开始的子树深度？ 算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。 A B C D E 算法见附1 算法见附2 * 算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈(迭代方式) 。可直接用while语句和push/pop操作。参见教材P130-131程序。 4 中序遍历的非递归算法如何实现？ 3.如何判别给定二叉树是否为完全二叉树？ 算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。 技巧:按层次遍历方式，先把所有结点（不管当前结点是否有左右孩子）都入队列.若为完全二叉树,则层次遍历时得到的肯定是一个连续的不包含空指针的序列。如果序列中出现了空指针，则说明不是完全二叉树。 算法见附3 算法见附4 * Void ABC(Bitree p, int l, int h) { if p≠NIL then { l=l+1; if lh then h=l; ABC(p-Lchild, l, h); ABC(p-Rchild, l, h); } } 法1：从根开始向下计算层次(比从叶子往上计算更简单) l、h分别表示二叉树的层次数和深度。 想一想，l和h的初始值应设为多少？ 开始调用时，应当用ABC（p, 0, 0） 若去掉h形参中的“”号，则h不变化，算出的更深层数不能