《树(第五章)综述》由会员分享，可在线阅读，更多相关《树(第五章)综述（52页珍藏版）》请在金锄头文库上搜索。
1、6章 树和二叉树6.1 已知一棵树边的集合为, , , , , , , , , , ，请画出这棵树，并回答下列问题： (1) 哪个是根结点？ (2) 哪些是叶子结点？ (3) 哪个是结点G的双亲？ (4) 哪些是结点G的祖先？ (5) 哪些是结点G的孩子？ (6) 哪些是结点E的子孙？ (7) 那些是结点E的子孙？ (8) 结点B和N的层次号分别是什么？ (9) 树的深度是多少？ (10) 以结点C为根的子树的深度是多少？6.2 一棵度为2的树与一棵二叉树有何区别？解：二叉树是颗有序树，但度为2的树则未必有序。6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。6.4 一棵深度
2、为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问： (1) 各层的结点数目是多少？ (2) 编号为p的结点的父结点（若存在）的编号是多少？ (3) 编号为p的结点的第i个儿子结点（若存在）的编号是多少？ (4) 编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？解：(1)(2)如果p是其双亲的最小的孩子（右孩子），则p减去根结点的一个结点，应是k的整数倍，该整数即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如果p是其双亲的最大的孩子（左孩子），则p+k-1为其最小的弟弟，再减去一个根结点，
3、除以k，即为其双亲结点的编号。综合来说，对于p是左孩子的情况，i=(p+k-2)/k；对于p是右孩子的情况，i=(p-1)/k如果左孩子的编号为p，则其右孩子编号必为p+k-1，所以，其双亲结点的编号为 向下取整，如1.5向下取整为1(3)结点p的右孩子的编号为kp+1，左孩子的编号为kp+1-k+1=k(p-1)+2，第i个孩子的编号为k(p-1)+2+i-1=kp-k+i+1。(4)当(p-1)%k != 0时，结点p有右兄弟，其右兄弟的编号为p+1。6.5 已知一棵度为k的树中有个度为1的结点，个度为2的结点，个度为k的结点，问该树中有多少个叶子结点？解：根据树的定义，在一颗树中，除树根
4、结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点树等于所有结点的分支数，即度数，从而可得树中的结点数等于所有结点的度数加1。总结点数为而度为0的结点数就应为总结点数减去度不为0的结点数的总和，即6.6 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子节点数目。解：利用上题结论易得结果。设度为k的结点个数为，则总结点数为。叶子结点的数目应等于总结点数减去度不为0的结点的数目，即6.7 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？解：能达到最大深度的树是单支树，其深度为n。满k叉
5、树的深度最小，其深度为(证明见徐孝凯著数据结构实用教程P166)6.8 证明：一棵满k叉树上的叶子结点数和非叶子结点数之间满足以下关系：解：一棵满k叉树的最后一层(深度为h)的结点数(叶子结点数)为，其总结点数为，则非叶子结点数，从而得6.9 试分别推导含有n个结点和含个叶子结点的完全三叉树的深度H。解：(1) 根据完全三叉树的定义(2) 设总的结点数为n，非叶子结点数为注意到每个非叶子结点的度均为3，则由 6.10 对于那些所有非叶子结点均含有左右子数的二叉树： (1) 试问：有n个叶子结点的树中共有多少个结点？ (2) 试证明：，其中n为叶子结点的个数，表示第i个叶子结点所在的层次（设根节
6、点所在层次为1）。解：（1）总结点数为，其中为非叶子结点数，则叶子结点数为，所以总结点数为 。（2）用归纳法证明。i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点，,，结论成立。设有n个叶子结点时也成立，即，现假设增加一个叶子结点，这意味着在某叶子结点p上新生两个叶子结点，而结点p则成为非叶子结点，可见，总结点数增2，叶子结点数增1。此时，所有叶子结点是原结点除去p，然后加上两个深度为的新叶子结点，由此，则当i=n+1时，也成立，由此即得到证明。6.11 在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节，每个信息域占k个字节。试问：对于
7、一棵有n个结点的二叉树，且在顺序存储结构中最后一个节点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？解：采用三叉链表结构，需要n(k+12)个字节的存储空间。采用顺序存储结构，需要mk个字节的存储空间，则当mkrchild;if(!r-ltag)while(!r-ltag) r=r-lchild;return r; / InSucc6.18 解：如果p是根结点，则其后继为空。否则需查找p的双亲结点。从p结点开始中序线索遍历，如果某结点的左指针域等于p，说明该结点是p的双亲结点，且p是它的左孩子；如果某结点的右指针域等于p，说明该结点是p的双亲结点，且p是它的右孩子；如此即可确定访问
8、次序。若是右孩子，其后继是双亲结点；若是左孩子，其后继是其兄弟最左下的子孙，如果兄弟不存在，其后继是其双亲结点。6.19 分别画出和下列树对应的各个二叉树：解：6.20 解：(1) 先序：1 2 3 4 5 6 8 7 9 10 11 12 13 15 14(2) 中序：3 4 8 6 7 5 2 1 10 9 11 15 14 13 12(3) 后序：8 7 6 5 4 3 2 10 15 14 13 12 11 9 16.23 解：树的先根序列为GFKDAIEBCHJ，后根序列为DIAEKFCJHBG，可以先转化成二叉树，再通过二叉树转换成树。注意二叉树的先根序列与等价树的先根序列相同，二
9、叉树的中序序列对应着树的后根序列。GFKDAIEBCHJ为所求二叉树的先序序列，DIAEKFCJHBG为二叉树的中序序列。通过观察先序序列，G为二叉树的根结点，再由中序序列，G的左子树序列为DIAEKFCJHB，右子为空。可以表示成如下形式：G(DIAEKFCJHB，NULL)对于子树先序序列为FKDAIEBCHJ，中序序列为DIAEKFCJHB，显然子树根为F。再由中序序列可以看到，F的左子树是DIAEK，右子树为CJHB。进一步表示成：G(F(DIAEK,CJHB),NULL)对于DIAEK（中序表示），先序为KDAIE，K为根，左子为DIAE，右子为空；对于CJHB，B为根，左子为CJH
10、，右子为空。进一步表示成：G(F(K(DIAE,NULL),B(CJH,NULL),NULL)G(F(K(D(NULL,IAE),NULL),B(C(NULL,JH),NULL),NULL)G(F(K(D(NULL,A(I,E),NULL),B(C(NULL,H(J,NULL),NULL),NULL)由此画出二叉树，进而画出树。6.24 解：本题应注意下列转换：树森林二叉树先根先序先序后根中序中序6.25 解；用归纳法证明。当n=2时，要使其成为最优二叉树，必须使两个结点都成为叶子结点。设n=k时成立，则当n=k+1时，要使其成为最优，必须用k个结点的哈夫曼树与第k+1个结点组成一个新的最优二
11、叉树，所以n=k+1时也成立。6.26 解：不妨设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。A:1101 B:01 C:11111 D:1110 E:10 F:11110 G:00 H:1100 采用这种方式编码，电文最短。6.27 解：6.33 解：int Visit(int u,int v)if(u=v) return 1;if(Lv=0)/左子树不存在if(Rv=0)/右子树也不存在return 0;else/ 右子树存在，继续访问右子树if(Visit(u,Rv) return 1;else return 0;else/ 左子树存在if(Visit(u,Lv)/ 左子树中存在目标return 1;else/ 左子树中没有目标，需访问右子树if(Rv=0)/ 没有右子树return 0;else/ 右子树存在，继续访问右子树if(Visit(u,Rv) return 1;else return 0;6.34 解：int Visit(int u,int v)int Nv;Nv=NumEl
