1、一、下面是有關二叉樹的敘述，請判斷正誤（）（ ）. 若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n1個非空指針域。（ ）.二叉樹中每個結點的兩棵子樹的高度差等于1。 （ ）.二叉樹中每個結點的兩棵子樹是有序的。 （ ）.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。 （ ）二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。 （應當是二叉排序樹的特點）（ ）.二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。（應2i-1） （ ）.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。 （ ）

2、.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i1個結點。（應2i-1）（ ）用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點的2n個指針區域中有n+1個為空指針。（正確。用二叉鏈表存儲包含n個結點的二叉樹，結點共有2n個鏈域。由于二叉樹中，除根結點外，每一個結點有且僅有一個雙親，所以只有n-1個結點的鏈域存放指向非空子女結點的指針，還有n+1個空指針。）即有后繼鏈接的指針僅n-1個。（ ）10.具有12個結點的完全二叉樹有5個度為2的結點。最快方法：用葉子數n/26，再求n2=n0-1=5 二、填空（）1 由個結點所構成的二叉樹有 5 種形態。 2.

3、一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n0-1=31 個分支結點和 26-1 =32 個葉子。注：滿二叉樹沒有度為1的結點，所以分支結點數就是二度結點數。3 一棵具有個結點的完全二叉樹，它的深度為 9 。（ 注：用ë log2(n) û+1= ë 8.xx û+1=94. 設一棵完全二叉樹有700個結點，則共有 350 個葉子結點。答：最快方法：用葉子數n/2350 5. 設一棵完全二叉樹具有1000個結點，則此完全二叉樹有 500 個葉子結點，有 499 個度為2的結點，有 1 個結點只有非空左子樹，有 0 個結點只有非空右子樹。答：最快

4、方法：用葉子數n/2500 ，n2=n0-1=499。 另外，最后一結點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數0.6. 一棵含有n個結點的k叉樹，可能達到的最大深度為 n ，最小深度為 2 。答：當k=1(單叉樹)時應該最深，深度n（層）；當k=n-1（n-1叉樹）時應該最淺，深度2（層），但不包括n=0或1時的特例情況。教材答案是“完全k叉樹”，未定量。)7. 二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按N L R次序），后序法（即按 L R

5、 N 次序）和中序法（也稱對稱序法，即按L N R次序）。這三種方法相互之間有關聯。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是 F E G H D C B 。 解：法1：先由已知條件畫圖，再后序遍歷得到結果；法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹。例如，前序遍歷BEFCGDH中，根結點在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計算。如B在前序序列中第一，中序中在中間（可知左右子樹上有哪些元素），則在后序中必為最后。如法對B的左右子樹同樣處理，則問題得解。8.中序遍歷的遞歸算法平均

6、空間復雜度為 O(n) 。答：即遞歸最大嵌套層數，即棧的占用單元數。精確值應為樹的深度k+1，包括葉子的空域也遞歸了一次。9. 用5個權值3, 2, 4, 5, 1構造的哈夫曼（Huffman）樹的帶權路徑長度是 33 。解：先構造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL（453）×2（12）×3=33 (15)(9) (6) （注：兩個合并值先后不同會導致編碼不同，即哈夫曼編碼不唯一） 4 5 3 (3) （注：合并值應排在葉子值之后）1 2（注：原題為選擇題：32 33 34 15）三、單項選擇題（）（ C ）1 不含任何結點的空樹 。（）是一棵樹; （）是一棵

7、二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹答：以前的標答是B，因為那時樹的定義是n1（ C ）2二叉樹是非線性數據結構，所以 。（）它不能用順序存儲結構存儲; （）它不能用鏈式存儲結構存儲; （）順序存儲結構和鏈式存儲結構都能存儲; （）順序存儲結構和鏈式存儲結構都不能使用 （ C ）3.具有n(n>0)個結點的完全二叉樹的深度為 。() élog2(n)ù () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1ù注1：éx ù表示不

8、小于x的最小整數；ë xû表示不大于x的最大整數，它們與 含義不同！注2：選（A）是錯誤的。例如當n為2的整數冪時就會少算一層。似乎ë log2(n) +1û是對的？（ A ）4把一棵樹轉換為二叉樹后，這棵二叉樹的形態是 。（）唯一的 （）有多種（）有多種，但根結點都沒有左孩子 （）有多種，但根結點都沒有右孩子5. 從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。樹是結點的有限集合，它A 根結點，記為T。其余的結點分成為m（m0）個 B 的集合T1，T2，Tm，每個集合又都是樹，此時結點T稱為Ti的父結點，Ti稱

9、為T的子結點（1im）。一個結點的子結點個數為該結點的 C 。供選擇的答案A： 有0個或1個 有0個或多個 有且只有1個 有1個或1個以上 B: 互不相交 允許相交 允許葉結點相交 允許樹枝結點相交C： 權 維數 次數（或度） 序答案：ABC1，1，36. 從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。二叉樹 A 。在完全的二叉樹中，若一個結點沒有 B ，則它必定是葉結點。每棵樹都能惟一地轉換成與它對應的二叉樹。由樹轉換成的二叉樹里，一個結點N的左子女是N在原樹里對應結點的 C ，而N的右子女是它在原樹里對應結點的 D 。供選擇的答案A： 是特殊的樹

10、 不是樹的特殊形式 是兩棵樹的總稱 有是只有二個根結點的樹形結構 B: 左子結點 右子結點 左子結點或者沒有右子結點 兄弟CD： 最左子結點 最右子結點 最鄰近的右兄弟 最鄰近的左兄弟 最左的兄弟 最右的兄弟答案：A= B= C= D 答案：ABCDE2，1，1，3四、簡答題（）1. 一棵度為2的樹與一棵二叉樹有何區別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結點只有一個孩子，就無需區分其左右次序，而在二叉樹中即使是一個孩子也有左右之分。C的結點類型定義如下：struct nodechar data;struct node *lchild

11、, rchild;C算法如下：void traversal(struct node *root)if (root) printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data);traversal(root->rchild);2.設如下圖所示的二叉樹B的存儲結構為二叉鏈表，root為根指針，結點結構為：（lchild,data,rchild）。其中lchild，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問題：1. 對下列二叉樹B，執行下列算

12、法traversal(root)，試指出其輸出結果；2. 假定二叉樹B共有n個結點，試分析算法traversal(root)的時間復雜度。（共8分）AB D C F G E二叉樹B解：這是“先根再左再根再右”，比前序遍歷多打印各結點一次，輸出結果為：A B C C E E B A D F F D G G特點：每個結點肯定都會被打印兩次；但出現的順序不同，其規律是：凡是有左子樹的結點，必間隔左子樹的全部結點后再重復出現；如A，B，D等結點。反之馬上就會重復出現。如C，E，F，G等結點。時間復雜度以訪問結點的次數為主，精確值為2*n，時間漸近度為O(n).3.給定二叉樹的兩種遍歷序列，分別是：前序

13、遍歷序列：D，A，C，E，B，H，F，G，I； 中序遍歷序列：D，C，B，E，H，A，G，I，F，試畫出二叉樹B，并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應前序遍歷序列中的元素集合，可繼續確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。 D A C FE GB H I2825 3340 60 08 54 554.給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹。解：要遵循中序遍歷的軌跡來畫出每個前驅和后繼

14、。中序遍歷序列：55 40 25 60 28 08 33 54282540555560330854NILNIL 2825 33 40 60 08 54 55五、閱讀分析題（）1.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A2. （P60 4-27）把如圖所示的樹轉化成二叉樹。答：注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結點一律歸入左子樹，新添連線結點一律歸入右子樹。 A B

15、E C K F H D L G I M J答：這是找結點后繼的程序。共有3處錯誤。注：當rtag1時說明內裝后繼指針，可直接返回，第一句無錯。當rtag0時說明內裝右孩子指針，但孩子未必是后繼，需要計算。中序遍歷應當先左再根再右，所以應當找左子樹直到葉子處。r=r->lchild; 直到LTag=1； 應改為：while(!r->Ltag)r=r->Lchild;BiTree InSucc(BiTree q)/已知q是指向中序線索二叉樹上某個結點的指針，/本函數返回指向*q的后繼的指針。r=q->rchild; /應改為r=q；if(!r->rtag) while

16、(!r->rtag)r=r->rchild; /應改為 while(!r->Ltag) r=r->Lchild;return r; /應改為return r->rchild；/ISucc3.閱讀下列算法，若有錯，改正之。4.畫出和下列二叉樹相應的森林。答：注意根右邊的子樹肯定是森林，而孩子結點的右子樹均為兄弟。六、算法設計題（）1.編寫遞歸算法，計算二叉樹中葉子結點的數目。解：思路：輸出葉子結點比較簡單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子，將其打印出來。法一：核心部分為：DLR(liuyu *root) /*中序遍歷 遞歸函數*/if(root!

17、=NULL) if(root->lchild=NULL)&&(root->rchild=NULL)sum+; printf("%dn",root->data); DLR(root->lchild); DLR(root->rchild); return(0);法二：int LeafCount_BiTree(Bitree T)/求二叉樹中葉子結點的數目 if(!T) return 0; /空樹沒有葉子 else if(!T->lchild&&!T->rchild) return 1; /葉子結點 else

18、 return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);/左子樹的葉子數加 上右子樹的葉子數 /LeafCount_BiTree 注：上機時要先建樹！例如實驗二的方案一。 打印葉子結點值（并求總數）思路：先建樹，再從遍歷過程中打印結點值并統計。步驟1 鍵盤輸入序列12，8，17，11，16，2，13，9，21，4，構成一棵二叉排序樹。葉子結點值應該是4，9, 13, 21, 總數應該是4. 127 17 2 11 16 21 4 9 13編程： 生成二叉樹排序樹之后，再中序遍歷排序查找結點的完整程序如下： 說明部分為：#include

19、 <stdio.h>#include <stdlib.h>typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root)root=s; return

20、;p=root; while(p) /*如何接入二叉排序樹的適當位置*/ q=p;if(p->data=x)printf("data already exist! n");return;else if(x<p->data)p=p->lchild; else p=p->rchild; if(x<q->data)q->lchild=s;else q->rchild=s;DLR(liuyu *root) /*中序遍歷 遞歸函數*/if(root!=NULL) if(root->lchild=NULL)&&

21、(root->rchild=NULL)sum+; printf("%dn",root->data); DLR(root->lchild); DLR(root->rchild); return(0); main() /*先生成二叉排序樹，再調用中序遍歷遞歸函數進行排序輸出*/int i,x;i=1; root=NULL; /*千萬別忘了賦初值給root!*/doprintf("please input data%d:",i);i+;scanf("%d",&x); /*從鍵盤采集數據，以-9999表示輸入結

22、束*/if(x=-9999) DLR(root); printf("nNow output count value:%dn",sum); return(0); else insert_data(x); /*調用插入數據元素的函數*/while(x!=-9999); return(0);執行結果：若一開始運行就輸入-9999，則無葉子輸出，sum=0。2.寫出求二叉樹深度的算法，先定義二叉樹的抽象數據類型。 （）編寫遞歸算法，求二叉樹中以元素值為x的結點為根的子樹的深度。答；設計思路：只查后繼鏈表指針，若左或右孩子的左或右指針非空，則層次數加1；否則函數返回。但注意，遞歸時應

23、當從葉子開始向上計數，否則不易確定層數。 int depth(liuyu*root) /*統計層數*/int d,p; /*注意每一層的局部變量d,p都是各自獨立的*/p=0;if(root=NULL)return(p); /*找到葉子之后才開始統計*/else d=depth(root->lchild);if(d>p) p=d; /*向上回朔時，要挑出左右子樹中的相對大的那個深度值*/d=depth(root->rchild);if(d>p)p=d;p=p+1;return(p);法二：int Get_Sub_Depth(Bitree T,int x)/求二叉樹中以值

24、為x的結點為根的子樹深度 if(T->data=x) printf("%dn",Get_Depth(T); /找到了值為x的結點,求其深度 exit 1; else if(T->lchild) Get_Sub_Depth(T->lchild,x); if(T->rchild) Get_Sub_Depth(T->rchild,x); /在左右子樹中繼續尋找 /Get_Sub_Depth int Get_Depth(Bitree T)/求子樹深度的遞歸算法 if(!T) return 0; else m=Get_Depth(T->lchild

25、); n=Get_Depth(T->rchild); return (m>n?m:n)+1; /Get_Depth 附：上機調試過程步驟1 鍵盤輸入序列12，8，17，11，16，2，13，9，21，4，構成一棵二叉排序樹。層數應當為4 12 8 17 2 11 16 21 4 9 13 步驟2： 執行求深度的函數，并打印統計出來的深度值。完整程序如下：#include <stdio.h>#include <stdlib.h>typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuy

26、u *root;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root)root=s; return;p=root; while(p) /*如何接入二叉排序樹的適當位置*/ q=p;if(p->data=x)printf("data already exist! n");return;el

27、se if(x<p->data)p=p->lchild; else p=p->rchild; if(x<q->data)q->lchild=s;else q->rchild=s;int depth(liuyu*root) /*統計層數*/int d,p; /*注意每一層的局部變量d,p都是各自獨立的*/p=0;if(root=NULL)return(p); /*找到葉子之后才開始統計*/else d=depth(root->lchild);if(d>p) p=d; /*向上回朔時，要挑出左右子樹中的相對大的那個深度值*/d=depth

28、(root->rchild);if(d>p)p=d;p=p+1;return(p);void main() /*先生成二叉排序樹，再調用深度遍歷遞歸函數進行統計并輸出*/int i,x;i=1; root=NULL; /*千萬別忘了賦初值給root!*/doprintf("please input data%d:",i);i+;scanf("%d",&x); /*從鍵盤采集數據，以-9999表示輸入結束*/if(x=-9999) printf("nNow output depth value=%dn", depth

29、 (root); return; else insert_data(x); /*調用插入數據元素的函數*/while(x!=-9999); return;執行結果：3.編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。或：按層次輸出二叉樹中所有結點；解：思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結點的指針是個好辦法。這是一個循環算法，用while語句不斷循環，直到隊空之后自然退出該函數。技巧之處：當根結點入隊后，會自然使得左、右孩子結點入隊，而左孩子出隊時又會立即使得它的左右孩子結點入隊，以此產生了按層次輸出的效果。level(liuyu*T)/* liuyu *T,*p,*q10

30、0; 假設max已知*/int f,r;f=0; r=0; /*置空隊*/r=(r+1)%max;qr=T; /*根結點進隊*/while(f!=r) /*隊列不空*/f=(f+1%max);p=qf; /*出隊*/printf("%d",p->data); /*打印根結點*/if(p->lchild)r=(r+1)%max; qr=p->lchild; /*若左子樹不空，則左子樹進隊*/ if(p->rchild)r=(r+1)%max; qr=p->rchild; /*若右子樹不空，則右子樹進隊*/ return(0);法二：void La

31、yerOrder(Bitree T)/層序遍歷二叉樹 InitQueue(Q); /建立工作隊列 EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); /LayerOrder 可以用前面的函數建樹，然后調用這個函數來輸出。完整程序如下（已上機通過）#include <stdio.h>#include <stdlib.h>#define max

32、 50typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root,*p,*qmax;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root)root=s; return;p=root; while(p) /*如何接入二叉排序樹

33、的適當位置*/ q=p;if(p->data=x)printf("data already exist! n");return;else if(x<p->data)p=p->lchild; else p=p->rchild; if(x<q->data)q->lchild=s;else q->rchild=s;level(liuyu*T)/* liuyu *T,*p,*q100; 假設max已知*/int f,r;f=0; r=0; /*置空隊*/r=(r+1)%max;qr=T; /*根結點進隊*/while(f!=r)

34、 /*隊列不空*/f=(f+1%max);p=qf; /*出隊*/printf("%d",p->data); /*打印根結點*/if(p->lchild)r=(r+1)%max; qr=p->lchild; /*若左子樹不空，則左子樹進隊*/ if(p->rchild)r=(r+1)%max; qr=p->rchild; /*若右子樹不空，則右子樹進隊*/ return(0);void main() /*先生成二叉排序樹，再調用深度遍歷遞歸函數進行統計并輸出*/int i,x;i=1; root=NULL; /*千萬別忘了賦初值給root!*/

35、doprintf("please input data%d:",i);i+;scanf("%d",&x); /*從鍵盤采集數據，以-9999表示輸入結束*/if(x=-9999) printf("nNow output data value:n", level(root); return; else insert_data(x); /*調用插入數據元素的函數*/while(x!=-9999); return;4. 已知一棵具有n個結點的完全二叉樹被順序存儲于一維數組A中，試編寫一個算法打印出編號為i的結點的雙親和所有的孩子。答：首先，由于是完全二叉樹，不必擔心中途會出現孩子為null的情況。其次分析：結點i的左孩子為2i，右孩子為2i+1;直接打印即可。Printf(“Le