數(shù)據(jù)結(jié)構(gòu)教程李春葆課后答案第7章樹(shù)和二叉樹(shù)

1、數(shù)據(jù)結(jié)構(gòu)教程學(xué)習(xí)指導(dǎo)第7章樹(shù)和二叉樹(shù)教材中練習(xí)題及參考答案1. 有一棵樹(shù)的括號(hào)表示為A（B, C（E, F（G）, D）,回答下面的問(wèn)題:（1）指出樹(shù)的根結(jié)點(diǎn)。（2）指出棵樹(shù)的所有葉子結(jié)點(diǎn)。（3）結(jié)點(diǎn)C的度是多少？（4）這棵樹(shù)的度為多少？（5）這棵樹(shù)的高度是多少？（6）結(jié)點(diǎn)C的孩子結(jié)點(diǎn)是哪些？（7）結(jié)點(diǎn)C的雙親結(jié)點(diǎn)是誰(shuí)？答：該樹(shù)對(duì)應(yīng)的樹(shù)形表示如圖7.2所示。（1）這棵樹(shù)的根結(jié)點(diǎn)是A。（2）這棵樹(shù)的葉子結(jié)點(diǎn)是B、E、G、Do（3）結(jié)點(diǎn)C的度是2。（4）這棵樹(shù)的度為3。（5）這棵樹(shù)的高度是4。（6）結(jié)點(diǎn)C的孩子結(jié)點(diǎn)是E、Fo7o所以含有60個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)的 最小高度是7 o6. 已知一棵完全二

2、叉樹(shù)的第6層（設(shè)根結(jié)點(diǎn)為第1層）有8個(gè)葉子結(jié)點(diǎn)，則該完全二 叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是多少？最少是多少？答：完全二叉樹(shù)的葉子結(jié)點(diǎn)只能在最下面兩層，所以結(jié)點(diǎn)最多的情況是第6層為倒數(shù) 第2層，即16層構(gòu)成一棵滿二叉樹(shù)，其結(jié)點(diǎn)總數(shù)為26-1=63。其中第6層有25=32個(gè)結(jié) 點(diǎn)，含8個(gè)葉子結(jié)點(diǎn)，則另外有32-8=24個(gè)非葉子結(jié)點(diǎn)，它們中每個(gè)結(jié)點(diǎn)有兩個(gè)孩子結(jié)點(diǎn) （均為第7層的葉子結(jié)點(diǎn)），計(jì)為48個(gè)葉子結(jié)點(diǎn)。這樣最多的結(jié)點(diǎn)個(gè)數(shù)=63+48=111。結(jié)點(diǎn)最少的情況是第6層為最下層，即15層構(gòu)成一棵滿二義樹(shù)，其結(jié)點(diǎn)總數(shù)為 25-1=31,再加上第6層的結(jié)點(diǎn)，總計(jì)31+8=39。這樣最少的結(jié)點(diǎn)個(gè)數(shù)為39。7. 己知

3、一棵滿二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為2040之間，此二叉樹(shù)的葉子結(jié)點(diǎn)有多少個(gè)？答:一棵高度為h的滿二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為2耳1,有：2002040。則25,滿二叉樹(shù)中葉子結(jié)點(diǎn)均集中在最底層，所以葉子結(jié)點(diǎn)個(gè)數(shù)=251=16個(gè)。8. 己知一棵二義樹(shù)的中呼岸列為cbedahgijf,后呼序列為cedbhjigfa,給出該二義樹(shù)樹(shù) 形表示。答：該二叉樹(shù)的構(gòu)造過(guò)程和二叉樹(shù)如圖7.5所示。第7章樹(shù)形結(jié)構(gòu)#f(b0若 b=NULL第7章樹(shù)形結(jié)構(gòu)#根：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章樹(shù)形結(jié)構(gòu)#f(b0若 b=NULL第7章樹(shù)形結(jié)構(gòu)#根：J左中序:空右中序:空 左啟斥:空右啟承空?qǐng)D75二叉樹(shù)的構(gòu)造過(guò)程9. 給定5個(gè)字符af,它們的權(quán)值集合昭2, 3, 4, 7, 8, 9,試構(gòu)造關(guān)于W的一 棵哈夫曼樹(shù)，求其帶權(quán)路徑長(zhǎng)度WPL和各個(gè)字符的哈夫曼樹(shù)編碼。答：由權(quán)值集合W構(gòu)建

5、的哈夫曼樹(shù)如圖7.6所示。其帶權(quán)路徑長(zhǎng)度 WP(9+7+8)x2+4x3+(2+3)x4=80。各個(gè)字符的哈夫曼樹(shù)編碼:a： 0000 b： 0001, c： 001 d： 10, e： 11, f： 01。a圖76 棵哈夫曼樹(shù)10. 假設(shè)二義樹(shù)中每個(gè)結(jié)點(diǎn)的值為單個(gè)字符，設(shè)計(jì)一個(gè)算法將一棵以二義鏈方式存儲(chǔ) 的二叉樹(shù)b轉(zhuǎn)換成對(duì)應(yīng)的順斥存儲(chǔ)結(jié)構(gòu)a-解：設(shè)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)類型為SqBTYee,先將順序存儲(chǔ)結(jié)構(gòu)a中所有元素置為 #(表示空結(jié)點(diǎn))。將b轉(zhuǎn)換成a的遞歸模型如下：f(b, a, 1)三當(dāng) b=NULLf(b, a, i)三由b結(jié)點(diǎn)data域值建立ai元素，其他情況f(b-lchild.

6、a, 2*i), f(b-i-child. a, 2*i+l)調(diào)用方式為：f(b a, 1) (a的下標(biāo)從1開(kāi)始)。對(duì)應(yīng)的算法如下：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. 假設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)值為單個(gè)字符，采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。設(shè)計(jì)一個(gè)算法， 求二叉樹(shù)t中的葉子結(jié)點(diǎn)個(gè)數(shù)。解：用i遍歷所有的結(jié)點(diǎn)，當(dāng)i大于等于MaxSize時(shí)，返回0。當(dāng)ti是空結(jié)點(diǎn)時(shí)返回0； 當(dāng)ti是非空結(jié)點(diǎn)時(shí)，

7、若它為葉子結(jié)點(diǎn),num增;否則遞歸調(diào)用numl=LeftNode(t, 2*i) 求出左子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)niunl.再遞歸調(diào)用num2=LeftNode(t, 2水i+1)求出右子樹(shù)的葉 子結(jié)點(diǎn)個(gè)數(shù)num2,置num-F=numl +inini2。最后返回num。對(duì)應(yīng)的算法如下：int LeftNode (SqBTree t, int i)/i的初值為1int numl, num2, num二0;if (i0若 b=NULL第7章樹(shù)形結(jié)構(gòu)11f(bf(b-lchild)+fb-rchild)+1若 b 結(jié)點(diǎn)為單分支f(bf(b lchild)+f(b-rchild)其他情況對(duì)應(yīng)的算法如下：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;為單分支結(jié)點(diǎn)elsen=0;其他結(jié)點(diǎn)numl=SSonNodes (b-lchild), /遞歸求左子樹(shù)山單分支結(jié)點(diǎn)數(shù) num2=SSonNodes (brchild); 遞歸求右子樹(shù)中單分支結(jié)點(diǎn)數(shù) return (numl +num2 +n);上述算法采用的是先序遍歷的思路。13. 假設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)值為

9、單個(gè)字符，采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。設(shè)計(jì)一個(gè)算法 求二叉樹(shù)b中最小值的結(jié)點(diǎn)值。解：設(shè)f(b, min)是在二叉樹(shù)b中尋找最小結(jié)點(diǎn)值inim其遞歸模型如下：f(b,f(b,若 b=NULL其他悄況min)三不做任何事件min)三 當(dāng) b-datadataf(b-lchild min), f(b-rchild, min),對(duì)應(yīng)的算法如下:void FindMinNode (BTNode b char Amin) if (b-datadata_.FindMinNode (b-lchild, min);F indMinNode (b*rchild, min);void MinNode (BTNode *

10、b)在左子樹(shù)中找最小結(jié)點(diǎn)值在右子樹(shù)中找最小結(jié)點(diǎn)值輸出最小結(jié)點(diǎn)值(b!二 NULL)char min=b-data;F indMinNode (b. min); printf (Min二cn, min);14. 假設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)值為單個(gè)字符，采用二義鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。設(shè)計(jì)一個(gè)算法 將二叉鏈bl復(fù)制到二叉鏈b2中。解:當(dāng)bl為空時(shí)，置b2為空樹(shù)。當(dāng)bl不為空時(shí)，建立b2結(jié)點(diǎn)(b2為根結(jié)點(diǎn))，置 b2-data=bl-data；遞歸調(diào)用 Copy(bl-1 child, b2-lcliild),由 bl 的左子樹(shù)建立 b2 的左 子樹(shù)；遞歸調(diào)用Copy(bl-rcliild, b2-rcliild

11、),由bl的右子樹(shù)建立b2的右子樹(shù)。對(duì)應(yīng)的 算法如下：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. 假設(shè)二義樹(shù)中每個(gè)結(jié)點(diǎn)值為單個(gè)字符，采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。設(shè)計(jì)一個(gè)算法， 求二叉樹(shù)b中第k層上葉子結(jié)點(diǎn)個(gè)數(shù)。解：采用先序遍歷方法，當(dāng)b為空時(shí)返回0。置num為0。若b不為空，當(dāng)前結(jié)點(diǎn)的 層次為k,并且b

12、為葉子結(jié)點(diǎn)，則num增1,遞歸調(diào)用numl=LevelkCount(b-ldiild, k, h+1) 求出左子樹(shù)中第k層的結(jié)點(diǎn)個(gè)數(shù)numl遞歸調(diào)用nuni2=LevelkCount(b-rchild, k, h+1)求 出右子樹(shù)中第k層的結(jié)點(diǎn)個(gè)數(shù)num2, H niuii4-=niuiil4-iium2,最后返回num。對(duì)應(yīng)的算法如 下：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 返回二叉樹(shù)b中第k層上葉子結(jié)點(diǎn)個(gè)數(shù)return LevelkCount (b, k, 1);16. 假設(shè)二義樹(shù)中每個(gè)結(jié)點(diǎn)值為單個(gè)字符，采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。設(shè)計(jì)一個(gè)算法， 判斷值為x的結(jié)點(diǎn)與值為y的結(jié)點(diǎn)是否互為兄弟，假設(shè)這樣的結(jié)點(diǎn)值是唯一的。解：采用先序遍歷方法，當(dāng)b為空時(shí)直接返回false；否則，若當(dāng)前結(jié)點(diǎn)b是雙

14、分支結(jié) 點(diǎn)，且有兩個(gè)互為兄弟的結(jié)點(diǎn)x、y,則返回true；否則，遞歸調(diào)用fl a g=Brother(b-l cliil d, x, y),求出x、y在左子樹(shù)中是否互為兄弟，若Hag為true,則返回true：否則遞歸調(diào)用 Brother(b-rchild x, y),求出x、y在右子樹(shù)中是否互為兄弟，并返回其結(jié)果。對(duì)應(yīng)的算 法如下：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. 假設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)值為單個(gè)字符，采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。設(shè)計(jì)一個(gè)算法， 采用先斥遍歷方法求二義樹(shù)b中值為x的結(jié)點(diǎn)的子孫，假設(shè)值為x的結(jié)點(diǎn)是唯一的。解：設(shè)計(jì)Output(p)算法輸出以p為根結(jié)點(diǎn)的所有結(jié)點(diǎn)。首先在二叉樹(shù)b中查找值為x 的結(jié)點(diǎn)，當(dāng)前b結(jié)點(diǎn)是這樣的結(jié)點(diǎn)，調(diào)用Out

16、put(b-lcliild)輸出其左子樹(shù)中所有結(jié)點(diǎn)，調(diào)用 Output(b-rcliild)輸出其右子樹(shù)中所有結(jié)點(diǎn)，并返回；否則，遞歸調(diào)用Cluld(b-lchild, x) 在左子樹(shù)中查找值為x的結(jié)點(diǎn)，遞歸調(diào)用Cliild(b-rcliild,x)在右子樹(shù)中查找值為x的結(jié)點(diǎn)。 對(duì)應(yīng)的算法如下：void Output (BTNode *p)/輸出以p為根結(jié)點(diǎn)的子樹(shù) if (p! =NULL) printf (z/%c p-data);Output (plchild);Output(p-rchild);void Child(BTNode *b, char x)輸出 x 結(jié)點(diǎn)的子孫 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. 假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法把二義樹(shù)b的左、右子樹(shù)進(jìn)行交 換。要求不破壞原二叉樹(shù)。并用相關(guān)數(shù)據(jù)進(jìn)行測(cè)試。解：交換二義樹(shù)的左、右子樹(shù)的遞歸模型如下：Kb, I) = l=NULL若 b=NULLf(b, t)三復(fù)制根結(jié)點(diǎn)b產(chǎn)生結(jié)點(diǎn)t,其他情況f(b-lchildf tl), f(b-i-child t2)

18、,t-lchild2, t-rchild=tl對(duì)應(yīng)的算法如下(算法返回左、右子樹(shù)交換后的二叉樹(shù))： include btree. cpp二叉樹(shù)基本運(yùn)算算法BTNode *Swap (BTNode *b) BTNode *t, *tl, *t2;if (b=NULL)t二NULL;else t = (BTNode *)malloc(sizeof (BTNode)；t-data=bdata;/復(fù)制產(chǎn)生根結(jié)點(diǎn)tt l=Swap (blch訂d);t2二Swap(brchild);t-lchild=t2;trchild=tl;return t;或者設(shè)計(jì)成如下算法(算法產(chǎn)生左、右子樹(shù)交換后的二義樹(shù)bl)

19、:void Swap1(BTNode *b, BTNode *ftbl) if (b=NULL)bl=NULL;else bl= (BTNode *)malloc (sizeof (BTNode);bl-data=b-data;復(fù)制產(chǎn)生根結(jié)點(diǎn)blSwapl (blchild, blrchild);Swapl (brchild, bl-lchild);)設(shè)計(jì)如下主函數(shù)：int mainO BTNode *b, *bl；CreateBTree (b, A(B (D (, G), C (E, F);printf (交換前的二叉樹(shù):”);DispBTree (b);printf (n);bl二Swap

20、 (b);printf (交換后的二叉樹(shù):);DispBTree (bl) ; printf (n);DestroyBTree(b);DestroyBTree (bl);return 1;程序執(zhí)行結(jié)果如下：交換前的二叉樹(shù):A(B(D(, G),C(E,F)交換后的二叉樹(shù):A(C (F,E),B(,D(G)假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法判斷一棵二叉樹(shù)b的左、右子樹(shù) 是否同構(gòu)。第7章樹(shù)形結(jié)構(gòu)#解：判斷二義樹(shù)bl. b2是否同構(gòu)的遞歸模型如下:第7章樹(shù)形結(jié)構(gòu)#第7章樹(shù)形結(jié)構(gòu)#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中有一個(gè)為空，另一個(gè)不為空其他悄況第7章樹(shù)形結(jié)構(gòu)#第7章樹(shù)形結(jié)構(gòu)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;對(duì)應(yīng)的算法如下:bool SymmCBlKode *bl, BTNode *b2) /判斷二叉樹(shù) bl 和 b2 是否同構(gòu) if (bl=NULL & b2=NULL)return true,else if (bl二二NULL | b2二二NULL)return false;elsereturn (Symm(bl-