第8章数据结构树和二叉树(k).ppt

* 赫夫曼编码 设给出一段报文： CAST CAST SAT AT A TASA 字符集合是{ C, A, S, T }，各个字符出现的频度(次数)是W={2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为(2+7+4+5)*2=36 * 7 2 5 4 0 1 0 0 1 1 A C T S 等长编码 按字符出现的概率不同给予不等长编码，减少总编码长度。 各字符出现概率为 { 2/18, 7/18, 4/18, 5/18 }， 化整为 { 2, 7, 4, 5 }。 以它们为各叶结点上 的权值，建立赫夫曼树。 左分支赋0，右分支赋1， 给出赫夫曼编码。 * 0 0 0 1 1 1 2 4 5 7 赫夫曼编码树 A: 0 T: 10 C: 110 S: 111 它的总编码长度7*1+5*2+(2+4)*3=35 比等长编码的情形要短。 总编码长度正好等于赫夫曼树的带权路径长度WPL。 赫夫曼编码是一种前缀编码。解码时不会混淆。 * 大家来思考 问题 问题： 在什么样的情况下，等长编码是最优的前缀码？ 回答： 当字符集中的各字符使用频率均匀时。 * 大家来思考 问题 问题： 相同一组电文，里面的字符的哈夫曼编码只有一种吗？编码后电文总长一样吗？ 回答： 不是的，因为哈夫曼树的形态可能有多种，所以编码也会有多种，wpl的值是相同的，所以不会影响电文总长 * 练 习 1.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 2．有数据W={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_(1)__，带权路径长度WPL为_(2)__。 3．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。 * 练 习 1．在某一通讯电文中出现以下8种字符A、B、C、D、E、F、G、H，其中他们出现的次数分别为10、16、14、20、8、9、13、17，请完成以下题目： （1）使用哈夫曼算法写出这8种字符的哈夫曼编码（注意：要求完整画出所构造的哈夫曼树）。 （2）计算以哈夫曼编码传输这段电文时电文总长。 * 小结 了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。这也是本章的一个难点内容。 * 本章总结： 1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 2. 熟悉二叉树的各种存储结构的特点及适用范围。 3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种有哪些信誉好的足球投注网站策略进行的遍历。 4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。 5.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。这也是本章的一个难点内容。 * 作 业 1.前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G 画出此二叉树。 2. C语言函数： void example(b) btree *b; { btree *stack[20], *p； int top; if (b!=null) { top=1; stack[top]=b;while (top0) { p=stack[top]; top--;printf(“%d”,p-data);if (p-rchild!=null){(1)___; (2)___;}if (p-lchild!=null)(3)___; (4)__;}}}} * 作 业 3.设有正文MNOPPPOPMMPOPOPPOPNP，字符集为M，N，O，P，设计一套二进制编码，使得上述正文的编码最短。 * 1. B 2. 5 3. 16 4.A 5. 4 3 2 2 * 5. 4 3 2 2 6. A * 假设：T是要遍历树的根指针，若T?!=?NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。问题：如何用栈来保存信息，使