数据结构以及应用算法教程参考答案（9）6章 树和二叉树

关注公众号凡花花的小窝，收获更多的考研计算机专业编程相关的资料 6章 树和二叉树 6.1 已知一棵树边的集合为{<I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <A,C>}，请画出这棵树，并回答下列问题： (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 一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问： (1) 各层的结点数目是多少？ (2) 编号为p的结点的父结点（若存在）的编号是多少？ (3) 编号为p的结点的第i个儿子结点（若存在）的编号是多少？ (4) 编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 　　解：(1) 　　(2)如果p是其双亲的最小的孩子（右孩子），则p减去根结点的一个结点，应是k的整数倍，该整数即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如果p是其双亲的最大的孩子（左孩子），则p+k-1为其最小的弟弟，再减去一个根结点，除以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的结点，问该树中有多少个叶子结点？ 　　解：根据树的定义，在一颗树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点树等于所有结点的分支数，即度数，从而可得树中的结点数等于所有结点的度数加1。总结点数为

而度为0的结点数就应为总结点数减去度不为0的结点数的总和，即

6.6 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子节点数目。 　　解：利用上题结论易得结果。设度为k的结点个数为，则总结点数为。叶子结点的数目应等于总结点数减去度不为0的结点的数目，即

6.7 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？ 　　解：能达到最大深度的树是单支树，其深度为n。满k叉树的深度最小，其深度为 (证明见徐孝凯著数据结构实用教程P166) 6.8 证明：一棵满k叉树上的叶子结点数和非叶子结点数之间满足以下关系：

解：一棵满k叉树的最后一层(深度为h)的结点数(叶子结点数)为，其总结点数为，则非叶子结点数，从而得

6.9 试分别推导含有n个结点和含个叶子结点的完全三叉树的深度H。 　　解：(1) 根据完全三叉树的定义

(2) 设总的结点数为n，非叶子结点数为注意到每个非叶子结点的度均为3，则 由

6.10 对于那些所有非叶子结点均含有左右子数的二叉树： (1) 试问：有n个叶子结点的树中共有多少个结点？ (2) 试证明：，其中n为叶子结点的个数，表示第i个叶子结点所在的层次（设根节点所在层次为1）。 　　解：（1）总结点数为，其中为非叶子结点数，则叶子结点数为，所以总结点数为 。 （2）用归纳法证明。 i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点，, ，结论成立。 设有n个叶子结点时也成立，即，现假设增加一个叶子结点，这意味着在某叶子结点p上新生两个叶子结点，而结点p则成为非叶子结点，可见，总结点数增2，叶子结点数增1。此时，所有叶子结点是原结点除去p，然后加上两个深度为的新叶子结点，由此，

则当i=n+1时，也成立，由此即得到证明。 6.11 在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节，每个信息域占k个字节。试问：对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个节点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？ 　　解：采用三叉链表结构，需要n(k+12)个字节的存储空间。采用顺序存储结构，需要mk个字节的存储空间，则当mk<n(k+12)时，即时，采用顺序存储比采用三叉链表更节省空间。 6.12 对题6.3所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 6.13 假设n和m为二叉树中两结点，用1、0或#（分别表示肯定、恰恰相反或不一定）填写下表： 问 已知 前序遍历时 n在m前？ 中序遍历时 n在m前？ 后序遍历时 n在m前？ n在m左方 　 　 　 n在m右左方 　 　 　 n是m祖先 　 　 　 n是m子孙 　 　 　 注：如果(1)离a和b最近的共同祖先p存在，且(2)a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。 6.14 找出所有满足下列条件的二叉树： (a) 它们在先序遍历和中序遍历时，得到的节点访问序列相同； (b) 它们在后序遍历和中序遍历时，得到的结点访问序列相同； © 它们在先序遍历和后序遍历时，得到的节点访问序列相同。 　　解：(a) 不含左子树的二叉树。 (b) 不含右子树的二叉树。 © 即不含左子树，也不含右子树的二叉树。 6.15 解：

6.16 解：1 2 3 4 5 6 7 8 9 10 11 12 13 14 Info A B C D E F G H I J K L M N Ltag 0 0 0 1 0 1 0 1 0 0 1 1 1 1 Lchild 2 4 6 2 7 3 10 14 12 13 13 9 10 11 Rtag 0 0 1 1 0 0 0 1 1 1 0 1 1 1 Rchild 3 5 6 5 8 9 11 3 12 13 14 0 11 8 6.17 解：其错误在于中序遍历应先访问其左子树，可做如下修改： BiTree InSucc(BiTree q){ // 一直q是指向中序线索二叉树上某个结点的指针， // 本函数返回指向*q的后继的指针。 r=q->rchild; if(!r->ltag) while(!r->ltag) r=r->lchild; return r; } // InSucc 6.18 解：如果p是根结点，则其后继为空。否则需查找p的双亲结点。从p结点开始中序线索遍历，如果某结点的左指针域等于p，说明该结点是p的双亲结点，且p是它的左孩子；如果某结点的右指针域等于p，说明该结点是p的双亲结点，且p是它的右孩子；如此即可确定访问次序。若是右孩子，其后继是双亲结点；若是左孩子，其后继是其兄弟最左下的子孙，如果兄弟不存在，其后继是其双亲结点。 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 1

6.23 解：树的先根序列为GFKDAIEBCHJ，后根序列为DIAEKFCJHBG，可以先转化成二叉树，再通过二叉树转换成树。注意二叉树的先根序列与等价树的先根序列相同，二叉树的中序序列对应着树的后根序列。 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，右子为空。进一步表示成： 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个结点组成一个新的最优二叉树，所以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(L[v]==0){//左子树不存在 if(R[v]==0)//右子树也不存在 return 0; else{// 右子树存在，继续访问右子树 if(Visit(u,R[v])) return 1; else return 0; } } else{// 左子树存在 if(Visit(u,L[v]))// 左子树中存在目标 return 1; else{// 左子树中没有目标，需访问右子树 if(R[v]0)// 没有右子树 return 0; else{// 右子树存在，继续访问右子树 if(Visit(u,R[v])) return 1; else return 0; } } } } 6.34 解： int Visit(int u,int v) { int Nv; Nv=NumElem(v); // 返回结点v的下标 if(Nv-1) exit(-2); // 结点v不存在，退出

if(u==v) return 1; if(L[Nv]==0){//左子树不存在 if(R[Nv]==0)//右子树也不存在 return 0; else{// 右子树存在，继续访问右子树 if(Visit(u,R[Nv])) return 1; else return 0; } } else{// 左子树存在 if(Visit(u,L[Nv]))// 左子树中存在目标 return 1; else{// 左子树中没有目标，需访问右子树 if(R[Nv]==0)// 没有右子树 return 0; else{// 右子树存在，继续访问右子树 if(Visit(u,R[Nv])) return 1; else return 0; } } }

} // 返回结点在数组T中的下标 int NumElem(int x) { int i=0; while(i<N&&T[i]!=x) i++; if(T[i]==x) return i; else return -1; } 6.35 解： #define N 8 char T[N]={‘0’,‘a’,‘b’,‘c’,‘d’,‘e’,‘f’,‘g’}; // 用顺序数组存储，0为头结点， // a为根结点，b为左子树，c为右子树，…

// 若某结点编号为奇数， // 则它必为其双亲的右孩子，否则为左孩子 // 编号为k的结点的双亲结点的编号为k/2

int NumTree(char c);// 求结点在树中的编号 int Exp(int a,int b);// 求a的b次方 int NumElem(char c);// 返回元素在数组中的下标

int main() { char c; cout<<“请输入结点的值：”; cin>>c; cout<<NumTree©<<endl; return 0; }

int NumTree(char c)// 求结点在树中的编号 { int k,i=0; int Code[N]; k=NumElem©; // 返回结点c的下标 if(k==-1) exit(-2); // 结点c不存在，退出

while(k){ // 如果k为偶数，记录一个代码1 if(k%2==1) Code[i]=1; else Code[i]=0; k=k/2; i++; } int x=0,j; for(j=0;j<i;j++) x=x+Code[j]*Exp(2,j); return x;

}

int Exp(int a,int b) { int i; int x=1; for(i=0;i<b;i++) x=x*a; return x; }

// 返回结点在数组T中的下标 int NumElem(char c) { int i=0; while(i<N&&T[i]!=c) i++; if(T[i]==c) return i; else return -1; } 6.36 解： Status SimilarTree(BiTree& T1,BiTree& T2) { if(!T1){// T1是空树 if(!T2) return TRUE;// T2是空树 else return FALSE; } else{// T1是非空树 if(!T2) return FALSE; else{// T2是非空树 if(SimilarTree(T1->lchild,T2->lchild) && SimilarTree(T1->rchild,T2->rchild)) return TRUE; else return FALSE; } } }