《数据结构与算法习题解答第4章》由会员分享，可在线阅读，更多相关《数据结构与算法习题解答第4章（12页珍藏版）》请在金锄头文库上搜索。
1、第4章树结构1. 选择题（1）C（2）C（3）B（4）B（5）B（6）C（7）C（8）D（9）A（10）D（11）D（12）B（13）B（14）D（15）B2. 判断题(I) V(2)V(3)X(4)X(5)J(6)X(7)J(8)V(9)V(10)X(II) X(12)X(13)V(14)X(15)X(16)X(17)V(18)X(19)X(20)V3. 简答题（1）解答】一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2。二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个结点可以有多棵子树。（2）对于图4-37所示二
2、叉树，试给出1）它的顺序存储结构示意图；2）它的二叉链表存储结构示意图；3）它的三叉链表存储结构示意图。GH(图4-37)【解答】1）顺序存储结构示意图ABCDEFAAAGAAH2）二叉链表存储结构示意图：3）三叉链表存储结构示意图：ABC人AD人EAAFAGaaha（3）对于图4-38所示的树，试给出1）双亲数组表示法示意图；2）孩子链表表示法示意图；3）孩子兄弟链表表示法示意图。BCADAEAAFAGAAHAABCGFEDIHJKMN(图4-38)A【解答】1）双亲数组表示法示意图：2）孩子链表表示法示意图3）孩子兄弟链表表示法示意图：人J人K人人M人AN人（4）画出图4-39所示的森林经
3、转换后所对应的二叉树，并指出森林中满足什么条件的结点在二叉树中是叶子。AFJBCDGEHI(图4-39)解答】ABFECGJDH在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩子也没有右兄弟结点。（5）将题4-40图所示的二叉树转换成相应的森林。【解答】森林：ArrBEHDG（6）证明：在结点数证明：由哈夫曼树的构的新结点，其度必为2,所（7）证明：若哈夫曼树中有n个叶结点，则树中共有2n1个结点。证明：n个叶结点，需经n-1次合并形成哈夫曼树，而每次合并产生一个分支结点，所以树中共有2n-1个结点。（8）证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。证
4、明：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根左子树右子树”的顺序，则由从第二元素开始的1个结点序列和中序序列根左边的1个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。（9）已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，n个12m度为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？解：设树中共有n个结点，n
5、0个叶结点，那么=%+叫+.+%树中除根结点外，每个结点对应着（1）个分支，而度为k的结点发出k个分支，所以:n=n+2*n,+.+m*n+1(2)12m由(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) 求表达式：a+b*(cd)e/f的波兰式
6、(前缀式)和逆波兰式(后缀式)。波兰式：-+a*b一cd/ef逆波兰式：abcd-*+ef/-(13) 画出和下列已知序列对应的树T：树的先根次序访问序列为：GFKDAIEBCHJ树的后根访问次序为：DIAEKFCJHBG。解答】对应的二叉树和树分别如下左、右图所示：GKFBDCAHIEJGFBKCHDAEJ(14) 画出和下列已知序列对应的森林F：森林的先根次序访问序列为：ABCDEFGHIJKL森林的后根访问次序为：CBEFDGAJIKLH。AHBDGIKLCEFJ(15) 画出和下列已知序列对应的树T：二叉树的层次访问序列为：ABCDEFGHIJ二叉树的中序访问次序为：DBGEHJACI
7、F解答】ABCDEF按层次遍历，第一个结点(若树不空)为根，该结点在中序序列中把序列分成左右两部分左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空，则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。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个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？
8、(1)哈夫曼树：1.001a：100.41f0.591b：1100.20、0.210.31、0.28c：01011d：11100的0.110盘60.12e：011f：00g：111110.800.40(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. 给定一棵用二叉链表表
9、示的二叉树，其根指针为root，试写出求二叉树结点的数目的算法。【提示】采用递归算法实现。0当二叉树为空二叉树结点的数目=左子树结点数目右子树结点数目1当二叉树非空intcount(BiTreeroot)if(root=NULL)return(0);elsereturn(count(root-lchild)+count(root-rchild)+1);2. 请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按lchild-rchild方式存储，链接时用叶结点的rchild域存放链指针。【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论
10、前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkListhead,pre=NULL;/*全局变量*/LinkListInOrder(BiTreeT)/*中序遍历二叉树T,将叶子结点从左到右链成一个单链表，表头指针为head*/if(T)InOrder(T-lchild);/*中
11、序遍历左子树*/if(T-lchild=NULL&T-rchild=NULL)/*当前是叶子结点*/if(pre=NULL)head=T;pre=T;/*处理第一个叶子结点*/elsepre-rchild=T;pre=T;/*将叶子结点链入链表*/InOrder(T-rchild);/*中序遍历右子树*/pre-rchild=NULL;/*设置链表尾结点*/return(head);3. 给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树的深度的算法。【提示】采取递归算法。intHeight(BiTreeroot)inthl,hr;if(root=NULL)return(0);
12、elsehl=Height(root-lchild);hr=Height(root-rchild);if(hlhr)return(hl+1);elsereturn(hr+1);4给定一棵用二叉链表表示的二叉树，其根指针为root，试求二叉树各结点的层数。【提示】采用先序递归遍历算法实现。1二叉树结点的层次数二其双亲结点的层次数+i当结点为根结点当结点非根结点voidfun(BiTreeroot,intn)if(t=NULL)return;elseprintf(“%d”,n);fun(root-lchild,n+1);fun(root-rchild,n+1);5给定一棵用二叉链表表示的二叉树，其
13、根指针为root，试写出将二叉树中所有结点的左、右子树相互交换的算法。【提示】设root为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树；交换左子树上各结点的左右子树；再交换根结点的左右子树。voidExchange(BiTreeroot)BiTNode*p;if(root)Exchange(root-lchild);Exchange(root-rchild);p=root-lchild;root-lchild=root-rchild;root-rchild=p;6.棵具有n个结点的完全二叉树采用顺序结构存储，试设计非递归算法对其进行先
14、序遍历。【提示】二叉树的顺序存储是按完全二叉树的顺序存储格式按层次存储的，双亲结点与子女结点的下标间有确定的关系。对顺序存储结构的二叉树进行先序遍历，与二叉链表存放二叉树的遍历策略类似。但是在顺序存储结构下，判二叉树结点为空的条件为：结点下标大于n，或结点值为0(一般二叉树中的“虚结点”)。voidPreOrder(datatypedatan+1)/*0号单元未用*/intstackn;inttop;if(n1)return;t=1;top=0;while(t0)while(t=n&datat!=0)Visite(datat);stacktop=t;top+;t=t*2;if(top=0)return;elsetop-;t=stacktop;t=t*2+1;7.二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先结点算法。【提示】对二叉树进行先序非递归遍历，查找值为x的结点。进入子树时，将子
