《第五章课后答案》由会员分享，可在线阅读，更多相关《第五章课后答案（4页珍藏版）》请在金锄头文库上搜索。
1、. 一棵度为2的树与一棵二叉树有何区别?树与二叉树之间有何区别? 答:度为2的树,不是一棵二叉树,因为度为2 的树只有一种形态，而二叉树有两种形态。在二叉树中,每个结点的孩子是有左右之分的,而树中每个结点的孩子之间没有次序限制。即使在有序树中,每个结点的孩子之间限定了相对次序，但也没有左右之分的。 可见树和二叉树是两种不同的树型结构。首先:二叉树中每个结点最多有两个子树,而树不一定。其次:树中的结点的孩子是没有左右之分的，而二叉树中结点的孩子是有左右之分的。2.(1) 它的顺序存储结构示意图：ABDEFGH(2) 它的二叉链表存储结构示意图：ABCDEFHG(3) 它的三叉链表存储结构示意图D
2、ABCEFGH4画出图5-40所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应的森林中结点为叶子结点的条件。ABCDEFGHIJABCDEFGHIJ9.已知一棵度为m的树中有n个度为1的结点，n2个度为的结点,，n个度为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点? 解: 设树中有n0个叶子结点,那么树中结点总数目为 0+n1+n2nm 如果B是树中的总分支数，则:N=B+1 而= *n0+*1+n2+m*nm 从而有N= 0+n2+n0*n0+n+2*2+*nm+1 得出n0=n+n+（m-）*nm+1 所以该数中叶子结点总数为n0n2+2*3+(m-)m 而树中
3、非终端结点数=结点总数-终端结点数 = n+n2+m n0 = 1+2+nm. 设高度为h的二叉树上只有度为和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。 答：最大值:21 最小值:-112. 求表达式（a+*(c-d)/f)的波兰式和逆波兰式。 波兰式： - + * b c d / f 逆波兰式：a c d- * + e f / 5. 画出和下列已知序列对应的树T。 层次序列:C D E FGH I J 中序序列: B G E H A CI ABCEFGHDIJ 1. 给定一棵用二叉表示的二叉树，其根指针为rot。试写出求二叉树结点的数目的算法。 int countnode(b
4、itreerot） (root=NULL）retrn 0;if(rootlhid=ULL oot-child=ULL）retur 1；retur （cotode（rootchi） utnode(ro-ril)+);3. 给定一棵用链表表示的二叉树，其根指针为root。试写出求二叉树深度的算法。 int depth (bie oot)itd1,2；if (oot =NULL）eturn 0;if (rot-lchld =UL& ro-rchild =UL)return ;d1=dpth(roo-lcild);d= dep(roorchild);f(d2)re（d+1)ese retun （d21);5. 给定一棵用链表表示的二叉树，其根指针为roo。试写出将二叉树中所有结点的左、右子树相互交换的的算法。id cngel（itrero) bitee p； if (rot = =NUL)etun ; p=oot-child;root-lchd=roo -rchild，root -chilp; hangelr（roo -child); chglr(root-rchid);
