第六章习题提示汇总.ppt

1、1. 熟练掌握树与二叉树的结构特性与递归定义，会用递归方法求解二叉树的各类问题，如二叉树的创建、销毁、先中后序遍历和输出、求树深、结点数、叶结点数、复制、左右子树互换、查找、删除(参考例程),小结,2. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，会构造线索二叉树(中序),会在中序线索化树上找给定结点的前驱和后继，理解线索化算法与正向、逆向遍历算法,3.掌握树、二叉树、线索二叉树、Huffman树的定义和相关性质,掌握二叉树的顺序存储与二叉、三叉链表存储，掌握树的双亲表示法 孩子表示法 孩子(双亲)链表表示法和孩子兄弟表示法，掌握森林的孩子兄弟表示法优缺点 掌握

2、树和森林的操作在孩子兄弟表示法即二叉链表表示法上的实现 掌握树、森林与二叉树之间的转换 掌握树和森林的遍历规则(注意与二叉链表遍历规则的对应关系)及其实现, 会由遍历序列画出对应的树和森林,会求树或森林的深度等,掌握最优树与赫夫曼树的概念 会构造赫夫曼树 掌握赫夫曼树的应用算法设计/编码/文件压缩 赫夫曼树和赫夫曼编码的存储表示及求取作业:求哈夫曼编码，A-H出现频率 (%) 7， 19，2，6，32，3，21，10 推荐习题: 1-9 12-17 19-24 27-28 49 54 60 65 71(后文有提示),推荐习题提示,1、给出边的集合要求画出该颗树,并求根结点、叶子结点、指定结点的

3、双亲、祖先、孩子、子孙、兄弟、结点的层次号、树深、子树的深度、结点的度 2、度为2的树与二叉树的区别 前者至少一结点度为2,且为无序树；后者度主要不超过2即可，且为有序树 3、试分别画出具有3个结点的树和二叉树的不同形态(形态可假设所有结点值等,2/5),4、深度为H的满k叉树，将所有结点按层序从1开始编号，则各层的结点数是？编号为p的结点的父结点(若存在)编号是？编号为p的结点的第i个儿子结点的编号是？编号为p的结点有右兄弟的条件是什么？右兄弟编号是多少? 提示：分析满k叉树的结构可得，关键看倒数第二个孩子结点，可借助具体的某个满3叉树和4叉树验证。,5、度为k的树中有ni个度为i的结点,1

4、=i=k,求树中叶子结点数 提示：e=n0+n1+nk-1 =n1+2n2+knk 6、含n个结点的树中，只有度为k的分支结点和度为0的叶子结点,试求该树含有的叶子结点数 提示:n0+nk=n; e=n-1=knk;,7、含n个结点的k叉树，可能的最大和最小深度是多少？ 注意k叉树是度不超过k的有序树，最小对应完全k叉树 8、求证一颗满k叉树上的叶子结点数n0和非叶子结点数n之间存在关系n0=(k-1)n+1 提示：n=nk; n0+nk=n; e=n-1=knk; 9、分别推导含n结点和n0叶子结点的完全三叉树的深度 提示:参照完全二叉树深度的求取,12.求二叉树前序、中序和后序遍历序列 提

5、示：从各种规则的定义出发,注意递归 13.设n和m为二叉树两结点,当n在m左方时前序、中序和后序遍历时n在前吗？N在m右方、n是m祖先、n是m子孙如何？左右是指同层方向 14、先序序列和中序序列相同的二叉树有何特点？后序和中序相同如何？先序和后序相同如何？ 任意结点无左孩子；任意结点无右孩子;只有一个结点,6.15/16对给定二叉树进行后序线索化 头结点初始化;遍历序列;第1结点;最后结点; 17阅读中序线索二叉树上求结点后继的算法改错 1 BiTree InSucc(BiTree q) 2 r=q-rchild; 3 if(!r-rtag) /Link代表0；Thread代表1 4 whil

6、e(!r-rtag) 5 r=r-rchild; 6 return r; /3if(!q-rtag) 4while(!r-ltag) 5r=r-lchild,19-21 树、森林和二叉树的相互转换 提示:考虑孩子兄弟链表存储结构即得，类似课程设计 22 求给定树的先根序列和后根序列 注意后根的递归，先根对应二叉链表先序、后根对应二叉链表的中序 23 给出树的先根序列GFKDAIEBCHJ和后根序列DIAEKFCJHBG求树 两种方法:借助二叉树或根据定义，具体见下页 24给出森林先序和中序序列求森林ABCDEFGHIJKL； CBEFDGAJIKLH 两种方法，具体见下页 27-28 给二叉树

7、的先序+中序 或 后序+中序求该二叉树 具体见前面相应内容,由树的先根和后根遍历序列确定树,方法一(间接法，借助二叉链表)：树的先根序列对应二叉链表的先序序列、后根序列对应二叉链表的中序序列，由先序序列与中序序列可确定出二叉链表，再根据此二叉链表按照孩子兄弟表示法的含义可得此二叉链表对应的树 方法二(直接法，根据遍历规则)：先根序列中第1个X一定是整颗树的根结点,而后根序列中唯有遍历完X的所有子树后方访问X,故X必然出现在最后；先根序列中第二个顶点必然是第一个子树的根结点，后根序列中该结点前的结点为此子树中各结点；除去第一颗子树中的结点后，先根序列中第一个结点必为第二颗子树的根结点，而后根序列

8、中此结点前的结点构成第二颗子树，以此类推，最终可确定,先根:A B E F C D G H I J K,后根:E F B C I J K H G D A,由森林的先序和中序遍历序列确定森林,方法一(间接法，借助二叉链表):森林的先序序列对应二叉链表的先序序列、中序序列对应二叉链表的中序序列，由先序序列与中序序列可确定出二叉链表，再根据此二叉链表按照孩子兄弟表示法的含义可得此二叉链表对应的森林 方法二(直接法，根据遍历规则)：先序序列中第1个X一定是第一颗树的根结点,而中序序列中在遍历完第一颗树的最后访问X,故中序序列中X之前的结点构成森林的第一颗树，这些结点在先序和中序序列中的出现次序即为第一

9、颗树的先根序列和后根序列，根据树的确定方法可得第一颗树；除去第一颗树的结点后，先序序列中余下的第一个结点为第二颗树的根结点，中序序列中该结点前结点的构成第二颗树,依次类推，最终可得森林,先序: BEFKLCGDHIJ,中序:EKLFBGCHIJD,49判断二叉树是否为完全二叉树 求树深，递归，关键看倒数第二层 54给定一颗顺序存储的完全二叉树构造该树的二叉链表存储结构。 开辟根结点；对第2个结点开始的各结点，先开辟空间，而求其父结点并赋予相应的值即可.也可用层序遍历(自行思考,队列,图广度优先遍历) 60统计树的叶子结点数(firstchild为空) 65前序和中序序列分别存于两个一维数组中，据此构造该二叉树的二叉链表存储结构 递归，创建根,创建左子树,创建右子树，创建函数的参数含根和中序数组中结点起始下标 71凹式打印树:逐行打印,先根序,凹入深度由结点所在层次控制,用递归,6.26给出电文字符集及各字符频率求Huffman编码方案 具体例子如下页,练习题2 假设8个字符出现概率分别为%7，%19，%2，%6，%32，%3，%21，%10，构造Huffman树并求各字符编码,19,21,32,7,10,6,2