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

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

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

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

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

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

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

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

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

10、2) /判斷兩棵二叉樹是否相 似if(!BTl&!BT2) return 1;else if (!BT1!BT2) return 0;elsereturn BTreeSim(BTl-lchild, BT2-lchile)&BTreeSim(BTl-rchild,BT2- rchild);4. 編寫算法，求二義樹中以元素值為x的結點為根的子樹的深度。int Get_Sub_Depth(BTreeNode *BT , ElemType x) /值為 x 的結點為根的 子樹的深度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) /求二義樹 BT 的深度if (!BT) return 0; /空樹深度為 0else int depl二DepthBTree(BT-lchiid) ; /先求根結點左子樹的深度int dep2=DepthBTree(BT-rchild) ; /再求根結點右子樹的深度 辻(dep

12、ldep2) /返回最大值，并加上根結點這一層return depl+1;elsereturn dep2+l;5. 編寫算法，計算二叉樹中度為1的結點數和度為2的結點數。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. 試利用棧的基本操作編寫一個先序遍歷的非遞歸算法。若二義樹非空，首先訪問根結點并將其地址進棧，然后沿著左鏈遍歷根結點的 左子樹。若二義樹為空，則彈出棧頂元素，取得最近訪問過的根結點地址，然后沿右 鏈遍歷根結點的右子樹。【算法源代碼】void PreOrder