[其它技巧]第6章 树.ppt

4、已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。 5、找出所有满足下列条件的二叉树： （a）它们在先序遍历和中序遍历时，得到的结点访问序列相同； （b）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （c）它们在先序遍历和后序遍历时，得到的结点访问序列相同； 6、分别画出和下列树对应的各个二叉树： (a) (b) (c) (d) A C B A K J I H G F E C D B A C B A 7、假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。 8、假设在二叉链表中增加两个域：双亲域（parent)以指示其双亲结点；标志域（mark取值0..2）以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。 9、编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边。输出形式为（k1,k2)…(ki,kj)…,其中ki,kj树结点中结点的标识。(提示：修改二叉树遍历的递归算法，使其参数表增加参数father,指向被访问的当前结点的双亲结点。) 10、将下列二叉链表改为先序线索链表（不画出树的形态）。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Info A B C D E F G H I J K L M N Ltag Lchild 2 4 6 0 7 0 10 0 12 13 0 0 0 0 Rtag Rchild 3 5 0 0 8 9 11 0 0 0 14 0 0 0 11、假设用于通信的电文仅由八个字母组成，字母在电文中的出现频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制是另一种编码方案。对于上述实例，比较两种方案的优缺点。 32 2 3 5 6 11 7 10 17 28 19 21 40 32 40 32 19 21 40 72 2 3 5 6 11 7 10 17 28 32 19 21 40 72 28 72 100 a b c d e 3 7 5 9 6 小练习: 注意： ①初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子。②n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点，结点的度要么为0，要么为2。 2n0-1=n n0+n1+n2=n n0=n2+1 n1=0 * ③哈夫曼树是严格的(strict，或正则的)二叉树，没有度数为1的分支结点。 §6.7 霍夫曼编码 主要用途是实现数据压缩。 (1)等长编码方案 【例】设待压缩的数据文件共有100个字符，这些字符均取自字符集C={a，b，c，d，e，f }，等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为300位。 * C ={a，b，c，d，e，f } 则字符串efbacd可译为 100101001000010011 对方接受时，可按三位一分进行译码，即 e f b a c d 100，101，001，000，010，011 a 000 b 001 c 010 d 011 e 100 f 101 * 当然，在进行电文传送时，希望电文总长尽可能短，即传送时间尽可能短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送长度便可减少。 (2)变长编码方案 变长编码方案将频度高的字符编码设置短，将频度低的字符编码设置较长。【例】设待压缩的数据文件共有100个字符，这些字符均取自字符集C={a，b，c，d，e，f}，其中每个字符在文件中出现的次数(简称频度)如下： * --------------------------------------------------------------------字符????????????????????a???? b???? c???? d????? e?????