數(shù)據(jù)結(jié)構(gòu)練習(xí)4

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)(二叉樹(shù))一、選擇題1按照二義樹(shù)定義，具有3個(gè)結(jié)點(diǎn)的二義樹(shù)共有C種形態(tài)。(A) 3 (B) 4 (C) 5 (D) 62. 具有五層結(jié)點(diǎn)的完全二叉樹(shù)至少有D個(gè)結(jié)點(diǎn)。(A) 9 (B) 15 (C) 31 (D) 163. 以下有關(guān)二叉樹(shù)的說(shuō)法正確的是B。(A)二義樹(shù)的度為2 (B)棵二叉樹(shù)的度可以小于2(C)至少有一個(gè)結(jié)點(diǎn)的度為2 (D)任一結(jié)點(diǎn)的度均為24. 已知二義樹(shù)的后序遍歷是dabec,中序遍歷是debac,則其前序遍歷是D。(A)acbed (B)decab (C) deabc (D) cedba5. 將一棵有1000個(gè)結(jié)點(diǎn)的完全二義樹(shù)從上到下，從左到右依次進(jìn)行編號(hào)，根結(jié)

2、點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為B o(A) 9899 (C) 50 (D)沒(méi)有右孩子6. 對(duì)具有100個(gè)結(jié)點(diǎn)的二義樹(shù)，若有二叉鏈表存儲(chǔ)，則其指針域共有D為空。(A) 50 (B) 99 (C) 100 (D) 1017. 設(shè)二叉樹(shù)的深度為h,且只有度為1和0的結(jié)點(diǎn)，則此二義樹(shù)的結(jié)點(diǎn)總數(shù)為(A) 2h (B) 2h-l (C) h (D) h+1&對(duì)一棵滿二叉樹(shù),m個(gè)樹(shù)葉,n個(gè)結(jié)點(diǎn)，深度為h,則D。(A) n二h+m (B) h+m二2n (C)m=h-1 (D)n二2hT9. 某二叉樹(shù)的先序序列和后序序列正好相反，則下列說(shuō)法錯(cuò)誤的是A。(A) 二叉樹(shù)不存在(B) 若二叉樹(shù)不為空

3、，則二義樹(shù)的深度等于結(jié)點(diǎn)數(shù)(0若二叉樹(shù)不為空，則任一結(jié)點(diǎn)不能同時(shí)擁有左孩子和右孩子(D)若二叉樹(shù)不為空，則任一結(jié)點(diǎn)的度均為110. 對(duì)二義樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(jìn)行編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子 的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào),可采用C遍 歷實(shí)現(xiàn)編號(hào)。(A)先序(B)中序(C)后序(D)層序11. -個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為C o(A) 10 (B)ll (O1T1025 (D) 10102412. 設(shè)n, m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí),n在m前的條件是C O(A) n在m右方(B) n是m祖先(C) n在m左方(D) n是m子孫13.

4、 實(shí)現(xiàn)對(duì)任意二叉樹(shù)的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是 二叉樹(shù)采用C存儲(chǔ)結(jié)構(gòu)。(A)二叉鏈表(B)廣義表(C)三叉鏈表(D)順序14. 一棵樹(shù)可轉(zhuǎn)換成為與其對(duì)應(yīng)的二叉樹(shù)，則下面敘述正確的是A。(A) 樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷相同(B) 樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二義樹(shù)的后序遍歷相同(0樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷相同(D) 以上都不對(duì)二、填空題1. 對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它為一棵完全二義樹(shù)時(shí)具有最小高度；當(dāng) 它為單分支時(shí)，具有最大高度。2. 在二義樹(shù)的第i (i$l)層上至多有2i-l個(gè)結(jié)點(diǎn)，深度為k(kl)的完全二叉 樹(shù)至多2k-l個(gè)結(jié)點(diǎn)，

5、最少2k-l個(gè)結(jié)點(diǎn)；3. 如果二叉樹(shù)的終端結(jié)點(diǎn)數(shù)為nO,度為2的結(jié)點(diǎn)數(shù)為n2,則n0n2+l。4. 已知一棵.叉樹(shù)的中序序列是cbedahgi jf,后序序列是cedbhjigfa,則該二 義樹(shù)的先序序列是abcdefghij，該二叉樹(shù)的深度為5 o5. 若一棵二叉樹(shù)的中序遍歷結(jié)果為ABC,則該二義樹(shù)有5中不同的形態(tài)。6. 在順序存儲(chǔ)的二叉樹(shù)中，下標(biāo)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是Iog2i=log2j 。7. 已知完全二義樹(shù)的第7層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)為36個(gè)。總結(jié)點(diǎn)數(shù) 為71個(gè)。8. 在對(duì)二義樹(shù)進(jìn)行非遞歸中序遍歷過(guò)程中，需要用棧來(lái)暫存所訪問(wèn)結(jié)點(diǎn)的地址; 進(jìn)行層序遍歷過(guò)程中，需要用

6、隊(duì)列來(lái)暫存所訪問(wèn)結(jié)點(diǎn)的地址；9. 高度為h,度為k的樹(shù)中至少有h+k-l個(gè)結(jié)點(diǎn)，至多有(k n-l)/(k-l)個(gè)結(jié) 點(diǎn)。10. 一維數(shù)組存放完全二叉樹(shù):ABCDEFGHI,則后序遍歷該二義樹(shù)的序列為 HIDEBFGCA 。三、應(yīng)用題1. 應(yīng)用題：說(shuō)明分別滿足下列條件的.二義樹(shù)各是什么？(1) 先序遍歷和中序遍歷相同；中序遍歷和后序遍歷相同；(3)先序遍歷和后序遍歷相同；思考:TLR、LTR、LRT(1) 空樹(shù)、只有根結(jié)點(diǎn)、右單分支二叉樹(shù)；(2) 空樹(shù)、只有根結(jié)點(diǎn)、左單分支二義樹(shù)(3) 空樹(shù)、只有根結(jié)點(diǎn)2. 已知一棵二義樹(shù)的中序序列是cbedahgi jf,后序序列是cedbhjigfa,畫(huà)出

7、 這棵二義樹(shù)的邏輯結(jié)構(gòu)圖。3. 棵二叉樹(shù)的先序、中序、后序序列如下，其中一部分未標(biāo)出，試構(gòu)造出該 二叉樹(shù)。先序序列：ABCDEFGHIJK中序序列:C BEDFAHJKIG后序序列：CEFDBKJIHGA4. 有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，已知葉子結(jié)點(diǎn)個(gè)數(shù)為nO,回答下列問(wèn)題：(1) 寫(xiě)出求度為1的結(jié)點(diǎn)的個(gè)數(shù)nl的計(jì)算公式；(2) 若此樹(shù)是深度為k的完全二義樹(shù)，寫(xiě)出n為最小的公式；(3) 若二義樹(shù)中僅有度為0和度為2的結(jié)點(diǎn)，寫(xiě)出求該二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)n的公 式；(1) 記度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則n二n0+nl+n2,另一方面，除了根結(jié)點(diǎn)以外，其 余結(jié)點(diǎn)均有父結(jié)點(diǎn)的分支射出，所以結(jié)點(diǎn)數(shù)n二l+nl+2柏2;

8、綜合上面兩式可得 nl=n+l2n0o(2) 當(dāng)樹(shù)是深度為k的完全二義樹(shù)時(shí),n的最小值n min=2k-l;(3) 當(dāng)二義樹(shù)中僅有度為0和2的結(jié)點(diǎn)時(shí)，二義樹(shù)的結(jié)點(diǎn)個(gè)數(shù)n二2n0-1。四、算法設(shè)計(jì)題1. 編寫(xiě)求二義樹(shù)BT中結(jié)點(diǎn)總數(shù)的算法。int BTreeCount (BTreeNode *BT) /二叉樹(shù)中結(jié)點(diǎn)的總數(shù)if(BT二二NULL)return 0;else 辻(BT-left =NULL&BT-right 二二NULL)return 1;elsereturn BTreeCount(BT-left ) BTreeCount(BT-right ) + 1;2. 編寫(xiě)求二叉樹(shù)BT中葉子結(jié)點(diǎn)

9、數(shù)的算法。int BTreeCount (BTreeNode *BT) / .X樹(shù)中結(jié)點(diǎn)的總數(shù)辻(BT二二NULL)return 0;else 辻(BT-left =NULL&BT-right 二二NULL)return 1;elsereturn BTreeCount(BT-left ) BTreeCount(BT-)right );3. 若已知兩棵二義樹(shù)BT1和BT2皆為空，或者皆不為空且BT1的左、右子樹(shù)和 BT2的左、右子樹(shù)分別相似，則稱二叉樹(shù)BT1和BT2相似。編寫(xiě)算法,判別給定的兩 棵二叉樹(shù)是否相似。int BTreeSim(BTreeNode *BT1, BTreeNode *BT

10、2) /判斷兩棵二叉樹(shù)是否相 似if(!BTl&!BT2) return 1;else if (!BT1!BT2) return 0;elsereturn BTreeSim(BTl-lchild, BT2-lchile)&BTreeSim(BTl-rchild,BT2- rchild);4. 編寫(xiě)算法，求二義樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度。int Get_Sub_Depth(BTreeNode *BT , ElemType x) /值為 x 的結(jié)點(diǎn)為根的 子樹(shù)的深度if(!BT) return 0;else if(BT-data=x) return DepthBTree(BT);els

11、e if(BT-lch訂d!二NULL) return Get_Sub_Depth(BT-lch訂d , x);else 辻(BT-rchild!二NULL) return Get_Sub_Depth(BT-rchild, x);else return 0;int DepthBTree (BTreeNode *BT) /求二義樹(shù) BT 的深度if (!BT) return 0; /空樹(shù)深度為 0else int depl二DepthBTree(BT-lchiid) ; /先求根結(jié)點(diǎn)左子樹(shù)的深度int dep2=DepthBTree(BT-rchild) ; /再求根結(jié)點(diǎn)右子樹(shù)的深度 辻(dep

12、ldep2) /返回最大值，并加上根結(jié)點(diǎn)這一層return depl+1;elsereturn dep2+l;5. 編寫(xiě)算法，計(jì)算二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)和度為2的結(jié)點(diǎn)數(shù)。int si二0, s2=0;void BTreebranch(BTreeNode *BT) 辻（BT!二NULL） 辻（BT-lchild!二NULL） 辻（BT-rchild!=NULL） s2+;else sl+;BTreebranch（BT-lchild）;辻（BT-rchild!二NULL） 辻（BT-lchild!二NULL） sl+;BTreebranch（BT-rchild）;6. 試?yán)脳５幕静僮骶帉?xiě)一個(gè)先序遍歷的非遞歸算法。若二義樹(shù)非空，首先訪問(wèn)根結(jié)點(diǎn)并將其地址進(jìn)棧，然后沿著左鏈遍歷根結(jié)點(diǎn)的 左子樹(shù)。若二義樹(shù)為空，則彈出棧頂元素，取得最近訪問(wèn)過(guò)的根結(jié)點(diǎn)地址，然后沿右 鏈遍歷根結(jié)點(diǎn)的右子樹(shù)。【算法源代碼】void PreOrder