《数据结构与算法（java版） 教学课件 ppt 作者 罗文劼 习题解答 第4章》由会员分享，可在线阅读，更多相关《数据结构与算法（java版） 教学课件 ppt 作者 罗文劼 习题解答 第4章（12页珍藏版）》请在金锄头文库上搜索。
1、第 4 章 树结构 1.简答题 （1）一棵度为 2 的树与一棵二叉树有何区别？树与二叉树之间有何区别？ 【解答】 二叉树是有序树，度为 2 的树是无序树，二叉树的度不一定是 2。 二叉树是有序树，每个结点最多有两棵子树，树是无 序树，且每个结点可以有多棵子树。 （2）对于图 4-39 所示二叉树，试给出： 1）它的顺序存储结构示意图； 2）它的二叉链表存储结构示意图； 3）它的三叉链表存储结构示意图。 【解答】 1）顺序存储结构示意图： 2）二叉链表存储结构示意图： 3）三叉链表存储结构示意图： （3）对于图 4-40 所示的树，试给出： 1）双亲数组表示法示意图； 2）孩子链表表示法示意图；
2、 3）孩子兄弟链表表示法示意图。 A B C D E F GH A D B G E H C F (图 4-39) A B C D E F G H A BC D E F G H I D E FG C B A N M K J H (图 4-40) 【解答】 1）双亲数组表示法示意图： 2）孩子链表表示法示意图： 3）孩子兄弟链表表示法示意图： （4）画出图 4-41 所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的 结点在二叉树中是叶子。 【解答】 A B N H C G F EDI J K M I G H F DB C A E J (图 4-41) 0 A -1 1 B 0 2 C
3、0 3 D 2 4 E 2 5 F 1 6 G 1 7 H 5 8 I 2 9 J 4 10 K 4 11 M 3 12 N 8 2 6 4 10 1 5 3 11 9 7 12 0 A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K 11 M 12 N 8 在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩 子也没有右兄弟结点。 （5）将题 4-42 图所示的二叉树转换成相应的森林。 【解答】森林： （6）证明：在结点数多于 1 的哈夫曼树中不存在度为 1 的结点。 证明： 由哈夫曼树的构造过程可知， 哈夫曼树的每一分支结点都是由两棵
4、子树合并产生 的新结点，其度必为 2，所以哈夫曼树中不存在度为 1 的结点。 （7）证明：若哈夫曼树中有 n 个叶结点，则树中共有 2n1 个结点。 证明：n 个叶结点，需经 n-1 次合并形成哈夫曼树，而每次合并产生一个分支结点，所 以树中共有 2n-1 个结点。 （8）证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。 证明：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因 为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设 l 个元 素）表示左子树，若左边无元素，则说明左子树为空；右边（设 r 个元素）是右子树，若为 空，则右子树为
5、空。根据前序遍历中“根左子树右子树”的顺序，则由从第二元素开始 的 l 个结点序列和中序序列根左边的 l 个结点序列构造左子树，由前序序列最后 r 个元素序 列与中序序列根右边的 r 个元素序列构造右子树。 （9）已知一棵度为 m 的树中有 n1个度为 1 的结点，n2个度为 2 的结点，nm个 度为 m 的结点，问该树中共有多少个叶子结点？有多少个非终端结点？ 解：设树中共有 n 个结点，n0个叶结点，那么 H F G I J A B CE D A B HE G D C F n=n0+n1+nm (1) 树中除根结点外，每个结点对应着一个分支，而度为 k 的结点发出 k 个分支，所以： n=
6、n1+2*n2+m*nm+1 (2) 由(1)、(2)可知 n0= n2+2*n3+3*n4+(m-1)*nm+1 （10）在具有 n（n1）个结点的树中，深度最小的那棵树其深度是多少？它共有多少 叶子和非叶子结点？深度最大的那棵树其深度是多少？它共有多少叶子和非叶子结点？ 2; n-1; 1; n; 1, n-1 （11） 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点， 问该二叉树的结点数可能达 到的最大值和最小值。 最大值：2h-1； 最小值：2h-1 （12）求表达式： ab*(cd)e/f 的波兰式（前缀式）和逆波兰式（后缀式） 。 波兰式： - + a * b c d /
7、 e f 逆波兰式：a b c d - * + e f / - （13）画出和下列已知序列对应的树 T： 树的先根次序访问序列为：GFKDAIEBCHJ； 树的后根访问次序为：DIAEKFCJHBG。 【解答】对应的二叉树和树分别如下左、右图所示： （14）画出和下列已知序列对应的森林 F： 森林的先根次序访问序列为：ABCDEFGHIJKL； 森林的后根访问次序为：CBEFDGAJIKLH。 （15）画出和下列已知序列对应的树 T： 二叉树的层次访问序列为：ABCDEFGHIJ； 二叉树的中序访问次序为：DBGEHJACIF。 G B I EAD K F CH J A B D G C E F
8、 H IK J L G B I E A D K F C H J 【解答】 按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部 分左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空， 则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左 到右每个结点或是当前情况下子树的根或是叶子。 16假设用于通信的电文由字符集a,b,c,d,e,f,g中的字母构成。它们在电文中出现的频 度分别为0.31,0.16,0.10,0.08,0.11,0.20,0.04, （1）为这 7 个字母设计哈夫曼编码。 （2）对这 7 个字母进行等
9、长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文 总长压缩多少？ （1）哈夫曼树： a：10 b：110 c：010 d：1110 e：011 f：00 g：1111 （2）对这 7 个字母进行等长编码，至少需要 3 位二进制数。 等长编码的平均长度：0.31*3+0.16*3+0.10*3+0.08*3+0.11*3+0.20*3+0.04*3=3 哈夫曼编码：0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.54 哈夫曼编码比等长编码使电文总长压缩了：1 - 2.54/3=15.33% 2.算法设计题 （1）给定一棵用二叉链表表示
10、的二叉树，其根引用为 root，试写出求二叉树结点的数 目的算法。 【提示】采用递归算法实现。 public static int count(LinkBiTNode root) if(root=NULL) return (0); else return (count(root.lchild)+count(root.rchild)+1); A B C D E F G H I J 1.00 0.59 0.41 0.28 0.21 0.12 0.31 0.16 0.80 0.40 0.20 0.100.11 1 1 1 1 1 1 二叉树结点的数目 0 当二叉树为空 左子树结点数目右子树结点数目1
11、 当二叉树非空 （2）请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链 表。二叉树按 lchild-rchild 方式存储，链接时用叶结点的 rchild 域存放链引用。 【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论 先序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。 而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表， 因此， 可以采用三种 遍历中的任意一种方法遍历。 这里使用中序递归遍历。 设置前驱结点引用为 pre， 初始为空。 第一个叶子结点由引用变量 head 指向，遍历到叶子结点时，就
12、将它前驱的 rchild 引用指向 它，最后叶子结点的 rchild 为空。 LinkBiTNode head,pre=NULL; /全局变量 LinkBiTNode InOrder(LinkBiTNode T) /中序遍历二叉树 T，将叶子结点从左到右链成一个单链表，表头引用为 head if(T)InOrder(T.lchild); /中序遍历左子树 if(T.lchild=NULL pre=T; /处理第一个叶子结点 else pre.rchild=T; pre=T; /将叶子结点链入链表 InOrder(T.rchild); /中序遍历右子树 pre.rchild=NULL; /设置链
13、表尾结点 return(head); （3）给定一棵用二叉链表表示的二叉树，其根引用为 root，试写出求二叉树的深度的 算法。 【提示】采取递归算法。 public static int Height(LinkBiTNode root) int hl,hr; if (root=NULL) return(0); elsehl=Height(root.lchild); hr=Height(root.rchild); if (hlhr) return (hl+1); else return(hr+1); （4） 给定一棵用二叉链表表示的二叉树， 其根引用为 root， 试求二叉树各结点的层数。 【
14、提示】采用先序递归遍历算法实现。 void fun (LinkBiTNode root,int n) if(t=NULL) return; else System.out.println(“%d”,n); 二叉树结点的层次数 1 当结点为根结点 其双亲结点的层次数1 当结点非根结点 fun(root.lchild,n+1); fun(root.rchild,n+1); （5）给定一棵用二叉链表表示的二叉树，其根引用为 root，试写出将二叉树中所有结 点的左、右子树相互交换的算法。 【提示】设 root 为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于 后序遍历实现：交换左子树
15、上各结点的左右子树；交换右子树上各结点的左右子树；再交换 根结点的左右子树。 void Exchange(LinkBiTNode root) LinkBiTNode p; if(root) Exchange(root.lchild); Exchange(root.rchild); p=root.lchild; root.lchild=root.rchild; root.rchild=p; （6）一棵具有 n 个结点的完全二叉树采用顺序结构存储，试设计非递归算法对其进行 先序遍历。 【提示】 二叉树的顺序存储是按完全二叉树的顺序存储格式按层次存储的， 双亲结点与子女 结点的下标间有确定的关系。 对顺序存储结构的二叉树进行先序遍历， 与二叉链表存放二叉 树的遍历策略类似。 但是在顺序存储结构下， 判二叉树结点为空的条件为： 结点下标大于 n， 或结点值为 0（一般二叉树中的“虚结点” ） 。 public static void PreOrder(DataType data, int n) /0 号单元未用 int stack=new intn ; int top; if(n0) /第一次在栈中 p=stacktop.rchild; /转向右子树 stacktop=-stacktop;
