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-