数据结构教程李春葆课后答案第7章树和二叉树

1、数据结构教程学习指导第7章树和二叉树教材中练习题及参考答案1. 有一棵树的括号表示为A（B, C（E, F（G）, D）,回答下面的问题:（1）指出树的根结点。（2）指出棵树的所有叶子结点。（3）结点C的度是多少？（4）这棵树的度为多少？（5）这棵树的高度是多少？（6）结点C的孩子结点是哪些？（7）结点C的双亲结点是谁？答：该树对应的树形表示如图7.2所示。（1）这棵树的根结点是A。（2）这棵树的叶子结点是B、E、G、Do（3）结点C的度是2。（4）这棵树的度为3。（5）这棵树的高度是4。（6）结点C的孩子结点是E、Fo7o所以含有60个叶子结点的二叉树的 最小高度是7 o6. 已知一棵完全二

2、叉树的第6层（设根结点为第1层）有8个叶子结点，则该完全二 叉树的结点个数最多是多少？最少是多少？答：完全二叉树的叶子结点只能在最下面两层，所以结点最多的情况是第6层为倒数 第2层，即16层构成一棵满二叉树，其结点总数为26-1=63。其中第6层有25=32个结 点，含8个叶子结点，则另外有32-8=24个非叶子结点，它们中每个结点有两个孩子结点 （均为第7层的叶子结点），计为48个叶子结点。这样最多的结点个数=63+48=111。结点最少的情况是第6层为最下层，即15层构成一棵满二义树，其结点总数为 25-1=31,再加上第6层的结点，总计31+8=39。这样最少的结点个数为39。7. 己知

3、一棵满二叉树的结点个数为2040之间，此二叉树的叶子结点有多少个？答:一棵高度为h的满二叉树的结点个数为2耳1,有：2002040。则25,满二叉树中叶子结点均集中在最底层，所以叶子结点个数=251=16个。8. 己知一棵二义树的中呼岸列为cbedahgijf,后呼序列为cedbhjigfa,给出该二义树树 形表示。答：该二叉树的构造过程和二叉树如图7.5所示。第7章树形结构#f(b0若 b=NULL第7章树形结构#根：a左中序:cbed右中序hgijf左厉序cedbt右后序:hjigf根：b 左中序Q右中序ed 左启岸右丿“序ed根：f左中序hgij,右中序空左后序hjigt右丿订序空根：C

4、左中序空，右中序空左后序空，右后序空根：d左中序e,右中序空左启序e,右启序空根：g 左中序此右中序ij 片.h I h 彳 i11 f- ji根：e左中序空，右中序空左E序空，右亡序空根：h左中序:空，右中序:空左启序空右后序:空根：1 左中序:空.右中序J 左后序:空右后序Jf(b0若 b=NULL第7章树形结构#f(b0若 b=NULL第7章树形结构#根：J左中序:空右中序:空 左启斥:空右启承空图75二叉树的构造过程9. 给定5个字符af,它们的权值集合昭2, 3, 4, 7, 8, 9,试构造关于W的一 棵哈夫曼树，求其带权路径长度WPL和各个字符的哈夫曼树编码。答：由权值集合W构建

5、的哈夫曼树如图7.6所示。其带权路径长度 WP(9+7+8)x2+4x3+(2+3)x4=80。各个字符的哈夫曼树编码:a： 0000 b： 0001, c： 001 d： 10, e： 11, f： 01。a图76 棵哈夫曼树10. 假设二义树中每个结点的值为单个字符，设计一个算法将一棵以二义链方式存储 的二叉树b转换成对应的顺斥存储结构a-解：设二叉树的顺序存储结构类型为SqBTYee,先将顺序存储结构a中所有元素置为 #(表示空结点)。将b转换成a的递归模型如下：f(b, a, 1)三当 b=NULLf(b, a, i)三由b结点data域值建立ai元素，其他情况f(b-lchild.

6、a, 2*i), f(b-i-child. a, 2*i+l)调用方式为：f(b a, 1) (a的下标从1开始)。对应的算法如下：void Ctree (BTNode *b, SqBTree d int i) if (b!二NULL)( ai=b-data;Ctree (blchild, a. 2*i);Ctree (brchild, a, 2*i+l);else ai=，#;)11. 假设二叉树中每个结点值为单个字符，采用顺序存储结构存储。设计一个算法， 求二叉树t中的叶子结点个数。解：用i遍历所有的结点，当i大于等于MaxSize时，返回0。当ti是空结点时返回0； 当ti是非空结点时，

7、若它为叶子结点,num增;否则递归调用numl=LeftNode(t, 2*i) 求出左子树的叶子结点个数niunl.再递归调用num2=LeftNode(t, 2水i+1)求出右子树的叶 子结点个数num2,置num-F=numl +inini2。最后返回num。对应的算法如下：int LeftNode (SqBTree t, int i)/i的初值为1int numl, num2, num二0;if (i0若 b=NULL第7章树形结构11f(bf(b-lchild)+fb-rchild)+1若 b 结点为单分支f(bf(b lchild)+f(b-rchild)其他情况对应的算法如下：i

8、nt SSonNodes (BTNode *b) int numl, num2, n;if (b二二NULL)return 0;else if (b-lchild二二NULL & b-rch订d!二NULL) | | (blchild!二NULL & b-rchild=NULL) n=l;为单分支结点elsen=0;其他结点numl=SSonNodes (b-lchild), /递归求左子树山单分支结点数 num2=SSonNodes (brchild); 递归求右子树中单分支结点数 return (numl +num2 +n);上述算法采用的是先序遍历的思路。13. 假设二叉树中每个结点值为

9、单个字符，采用二叉链存储结构存储。设计一个算法 求二叉树b中最小值的结点值。解：设f(b, min)是在二叉树b中寻找最小结点值inim其递归模型如下：f(b,f(b,若 b=NULL其他悄况min)三不做任何事件min)三 当 b-datadataf(b-lchild min), f(b-rchild, min),对应的算法如下:void FindMinNode (BTNode b char Amin) if (b-datadata_.FindMinNode (b-lchild, min);F indMinNode (b*rchild, min);void MinNode (BTNode *

10、b)在左子树中找最小结点值在右子树中找最小结点值输出最小结点值(b!二 NULL)char min=b-data;F indMinNode (b. min); printf (Min二cn, min);14. 假设二叉树中每个结点值为单个字符，采用二义链存储结构存储。设计一个算法 将二叉链bl复制到二叉链b2中。解:当bl为空时，置b2为空树。当bl不为空时，建立b2结点(b2为根结点)，置 b2-data=bl-data；递归调用 Copy(bl-1 child, b2-lcliild),由 bl 的左子树建立 b2 的左 子树；递归调用Copy(bl-rcliild, b2-rcliild

11、),由bl的右子树建立b2的右子树。对应的 算法如下：void Copy (BTNode *b 1, BTNode *ftb2) if (bl=NULL)b2二NULL;elseb2=(BTNode *)malloc(sizeof(BTNode);b2-data=bl-data;Copy (bllchild, b2-lchild);Copy (blrchild, b2-rchild);)15. 假设二义树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法， 求二叉树b中第k层上叶子结点个数。解：采用先序遍历方法，当b为空时返回0。置num为0。若b不为空，当前结点的 层次为k,并且b

12、为叶子结点，则num增1,递归调用numl=LevelkCount(b-ldiild, k, h+1) 求出左子树中第k层的结点个数numl递归调用nuni2=LevelkCount(b-rchild, k, h+1)求 出右子树中第k层的结点个数num2, H niuii4-=niuiil4-iium2,最后返回num。对应的算法如 下：int LevelkCount (BTNode 也 int k, int h)/h的初值为1int numl, num2, num=0;if (b!二NULL) 辻(h=k & b-lchild=NULL & b-rchild=NULL)num+;numl=

13、Leve 1 kCount (b-lchild, k, h+1);num2=Leve 1 kCount (b*rchild, k, h+1);num+=numl +num2; return num;return 0;int Levelkleft (BTNode *b, int k 返回二叉树b中第k层上叶子结点个数return LevelkCount (b, k, 1);16. 假设二义树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法， 判断值为x的结点与值为y的结点是否互为兄弟，假设这样的结点值是唯一的。解：采用先序遍历方法，当b为空时直接返回false；否则，若当前结点b是双

14、分支结 点，且有两个互为兄弟的结点x、y,则返回true；否则，递归调用fl a g=Brother(b-l cliil d, x, y),求出x、y在左子树中是否互为兄弟，若Hag为true,则返回true：否则递归调用 Brother(b-rchild x, y),求出x、y在右子树中是否互为兄弟，并返回其结果。对应的算 法如下：bool Brother (BTNode b, char char y) bool flag,if (b=NULL)return false;else if (b-lchildJ=NULL & b-rchild!=NULL) 辻(b-lchild-data二二x

15、& b-rchild-data=y) 11(blchild-data=y & brchilddata=x) return true;)flag二Brother (blchild. x. y);if (flag=true)return true;elsereturn Brother (brchild, x. y);)17. 假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法， 采用先斥遍历方法求二义树b中值为x的结点的子孙，假设值为x的结点是唯一的。解：设计Output(p)算法输出以p为根结点的所有结点。首先在二叉树b中查找值为x 的结点，当前b结点是这样的结点，调用Out

16、put(b-lcliild)输出其左子树中所有结点，调用 Output(b-rcliild)输出其右子树中所有结点，并返回；否则，递归调用Cluld(b-lchild, x) 在左子树中查找值为x的结点，递归调用Cliild(b-rcliild,x)在右子树中查找值为x的结点。 对应的算法如下：void Output (BTNode *p)/输出以p为根结点的子树 if (p! =NULL) printf (z/%c p-data);Output (plchild);Output(p-rchild);void Child(BTNode *b, char x)输出 x 结点的子孙 if (b!

17、=NULL) if (b-data=x) if (b-lchild!=NULL)Output(blchild);if (b-rchildJ=NULL)Output(brchild);return;)Child(b-lchild, x);Child (brchiId, x);18. 假设二叉树采用二叉链存储结构，设计一个算法把二义树b的左、右子树进行交 换。要求不破坏原二叉树。并用相关数据进行测试。解：交换二义树的左、右子树的递归模型如下：Kb, I) = l=NULL若 b=NULLf(b, t)三复制根结点b产生结点t,其他情况f(b-lchildf tl), f(b-i-child t2)

18、,t-lchild2, t-rchild=tl对应的算法如下(算法返回左、右子树交换后的二叉树)： include btree. cpp二叉树基本运算算法BTNode *Swap (BTNode *b) BTNode *t, *tl, *t2;if (b=NULL)t二NULL;else t = (BTNode *)malloc(sizeof (BTNode)；t-data=bdata;/复制产生根结点tt l=Swap (blch订d);t2二Swap(brchild);t-lchild=t2;trchild=tl;return t;或者设计成如下算法(算法产生左、右子树交换后的二义树bl)

19、:void Swap1(BTNode *b, BTNode *ftbl) if (b=NULL)bl=NULL;else bl= (BTNode *)malloc (sizeof (BTNode);bl-data=b-data;复制产生根结点blSwapl (blchild, blrchild);Swapl (brchild, bl-lchild);)设计如下主函数：int mainO BTNode *b, *bl；CreateBTree (b, A(B (D (, G), C (E, F);printf (交换前的二叉树:”);DispBTree (b);printf (n);bl二Swap

20、 (b);printf (交换后的二叉树:);DispBTree (bl) ; printf (n);DestroyBTree(b);DestroyBTree (bl);return 1;程序执行结果如下：交换前的二叉树:A(B(D(, G),C(E,F)交换后的二叉树:A(C (F,E),B(,D(G)假设二叉树采用二叉链存储结构，设计一个算法判断一棵二叉树b的左、右子树 是否同构。第7章树形结构#解：判断二义树bl. b2是否同构的递归模型如下:第7章树形结构#第7章树形结构#f(bl b2)=truef(bl b2)=falsef(bl b2)=flj 1 -lchild b2-lchi

21、ld)& f(b 1 -rchild b2-rchild)bl=b2=NULL若bl、b2中有一个为空，另一个不为空其他悄况第7章树形结构#第7章树形结构13bool ConpBTree (BTNode *b) BTNode *QuMaxSize, *p;int front二0, rear=0;bool cm二true;bool bj=true;if (b=NULL) return true; rear+;Qu rear =b;while (front!二rear)front= (front+l)%MaxSize;p=Qufront;if (p-lchild=NULL)bj二false;if (pTrchild!二NULL)cm二false;对应的算法如下:bool SymmCBlKode *bl, BTNode *b2) /判断二叉树 bl 和 b2 是否同构 if (bl=NULL & b2=NULL)return true,else if (bl二二NULL | b2二二NULL)return false;elsereturn (Symm(bl-