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

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

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

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

5、的哈夫曼樹如圖7.6所示。其帶權(quán)路徑長度 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. 假設(shè)二義樹中每個結(jié)點的值為單個字符，設(shè)計一個算法將一棵以二義鏈方式存儲 的二叉樹b轉(zhuǎn)換成對應(yīng)的順斥存儲結(jié)構(gòu)a-解：設(shè)二叉樹的順序存儲結(jié)構(gòu)類型為SqBTYee,先將順序存儲結(jié)構(gòu)a中所有元素置為 #(表示空結(jié)點)。將b轉(zhuǎn)換成a的遞歸模型如下：f(b, a, 1)三當(dāng) b=NULLf(b, a, i)三由b結(jié)點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開始)。對應(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è)二叉樹中每個結(jié)點值為單個字符，采用順序存儲結(jié)構(gòu)存儲。設(shè)計一個算法， 求二叉樹t中的葉子結(jié)點個數(shù)。解：用i遍歷所有的結(jié)點，當(dāng)i大于等于MaxSize時，返回0。當(dāng)ti是空結(jié)點時返回0； 當(dāng)ti是非空結(jié)點時，

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

9、單個字符，采用二叉鏈存儲結(jié)構(gòu)存儲。設(shè)計一個算法 求二叉樹b中最小值的結(jié)點值。解：設(shè)f(b, min)是在二叉樹b中尋找最小結(jié)點值inim其遞歸模型如下：f(b,f(b,若 b=NULL其他悄況min)三不做任何事件min)三 當(dāng) b-datadataf(b-lchild min), f(b-rchild, min),對應(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)在左子樹中找最小結(jié)點值在右子樹中找最小結(jié)點值輸出最小結(jié)點值(b!二 NULL)char min=b-data;F indMinNode (b. min); printf (Min二cn, min);14. 假設(shè)二叉樹中每個結(jié)點值為單個字符，采用二義鏈存儲結(jié)構(gòu)存儲。設(shè)計一個算法 將二叉鏈bl復(fù)制到二叉鏈b2中。解:當(dāng)bl為空時，置b2為空樹。當(dāng)bl不為空時，建立b2結(jié)點(b2為根結(jié)點)，置 b2-data=bl-data；遞歸調(diào)用 Copy(bl-1 child, b2-lcliild),由 bl 的左子樹建立 b2 的左 子樹；遞歸調(diào)用Copy(bl-rcliild, b2-rcliild

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

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

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

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

18、,t-lchild2, t-rchild=tl對應(yīng)的算法如下(算法返回左、右子樹交換后的二叉樹)： 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;/復(fù)制產(chǎn)生根結(jié)點tt l=Swap (blch訂d);t2二Swap(brchild);t-lchild=t2;trchild=tl;return t;或者設(shè)計成如下算法(算法產(chǎn)生左、右子樹交換后的二義樹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é)點blSwapl (blchild, blrchild);Swapl (brchild, bl-lchild);)設(shè)計如下主函數(shù)：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;程序執(zhí)行結(jié)果如下：交換前的二叉樹:A(B(D(, G),C(E,F)交換后的二叉樹:A(C (F,E),B(,D(G)假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)，設(shè)計一個算法判斷一棵二叉樹b的左、右子樹 是否同構(gòu)。第7章樹形結(jié)構(gòu)#解：判斷二義樹bl. b2是否同構(gòu)的遞歸模型如下:第7章樹形結(jié)構(gòu)#第7章樹形結(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中有一個為空，另一個不為空其他悄況第7章樹形結(jié)構(gòu)#第7章樹形結(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;對應(yīng)的算法如下:bool SymmCBlKode *bl, BTNode *b2) /判斷二叉樹 bl 和 b2 是否同構(gòu) if (bl=NULL & b2=NULL)return true,else if (bl二二NULL | b2二二NULL)return false;elsereturn (Symm(bl-