數(shù)據(jù)結(jié)構(gòu)二叉樹習(xí)題含答案

1、第 6 章 樹和二叉樹1選擇題（ 1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ） 。A.唯一的B .有多種C.有多種，但根結(jié)點都沒有左孩子D.有多種，但根結(jié)點都沒有右孩子（ 2）由 3 個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（ ）A 2 B 3 C 4D 5（ 3）一棵完全二叉樹上有1001 個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ） 。A 250 B 500 C 254D 501（ 4）一個具有1025 個結(jié)點的二叉樹的高 h 為（ ） 。A 11 B 10C 11 至 1025之間D 10 至 1024 之間（5）深度為h的滿m叉樹的第k層有（）個結(jié)點。（1=<k=<h）A mk-

2、1B mk-1C mh-1D mh-1（ 6）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ） 。A.指向最左孩子B.指向最右孩子C .空 D .非空7）對二叉樹的結(jié)點從1 開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子 的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（ ）遍歷 實現(xiàn)編號。A.先序 B. 中序C. 后序 D.從根開始按層次遍歷（ 8）若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用（ ）遍歷方法最合適。A.前序 B .中序C .后序 D .按層次9 ）在下列存儲形式中，（ ）不是樹的存儲形式？A.雙親表示法B .孩子鏈表表示法C

3、 .孩子兄弟表示法D.順序存儲表示法（ 10） 一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反， 則該二叉樹一定滿足（ ） 。A.所有的結(jié)點均無左孩子B.所有的結(jié)點均無右孩子C.只有一個葉子結(jié)點D.是任意一棵二叉樹（ 11）某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。A.空或只有一個結(jié)點B.任一結(jié)點無左子樹C.高度等于其結(jié)點數(shù)D.任一結(jié)點無右子樹（12）若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（）。A X 的雙親B X 的右子樹中最左的結(jié)點C X 的左子樹 中最右結(jié)點D X 的左子樹中最右葉結(jié)點B 為了能在二叉樹中方便的進行插入與刪使二

4、叉樹的遍歷結(jié)果唯一C 物理D 線性13）引入二叉線索樹的目的是（） 。A.加快查找結(jié)點的前驅(qū)或后繼的速度C.為了能方便的找到雙親D14）線索二叉樹是一種（）結(jié)構(gòu)。A.邏輯B邏輯和存儲(15)設(shè)F是一個森林，B是由F變換得的二叉樹。若 F中有n個非終端結(jié)點，則 B中 右指針域為空的結(jié)點有()個。A. n-1 B . nC. n+1 D . n+22 .應(yīng)用題(1)試找出滿足下列條件的二叉樹中序序列與后序序列相同中序序列與層次遍歷序列相同先序序列與后序序列相同先序序列與中序序列相同先序遍歷二叉樹的順序是“根一左子樹一右子樹”，中序遍歷“左子樹一根一右子樹”后序遍歷順序是：“左子樹一右子樹一根&qu

5、ot;，根據(jù)以上原則，本題解答如下：(1) 若先序序列與后序序列相同，則或為空樹，或為只有根結(jié)點的二叉樹(2)若中序序列與后序序列相同，則或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹.(3)若先序序列與中序序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹.(4) 若中序序列與層次遍歷序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹 的二叉樹,中序序列：B F D A G E H C(2)設(shè)一棵二叉樹的先序序列：A B D F C E G H畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹(或森林)。nullH(2)(3)假設(shè)用于通信白電文僅由8個字母組成，字母在電

6、文中出現(xiàn)的頻率分別為0.07,0.19, 0.02, 0.06, 0.32, 0.03, 0.21 , 0.10。試為這8個字母設(shè)計赫夫曼編碼。試設(shè)計另一種由二進制表示的等長編碼方案。 對于上述實例，比較兩種方案的優(yōu)缺點。解：方案1;哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。w=7,19,2,6,32,3,21,10,按哈夫曼規(guī)則：(2,3),6, (7,10)1 ,19, 21,3210 6(5)字母 編P對應(yīng) 編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.32方案比較:字母 編p對應(yīng) 編碼出現(xiàn) 頻率10000.0720010.1930

7、100.0240110.0651000.32610003-的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案 2 的 WPL = 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼(4)已知下列字符AB、C、DkE、F、G的權(quán)值分別為3、12、7、4、2、8,11 ,試填寫出其對應(yīng)哈夫曼樹 HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。初態(tài):weightparentlchildrchild13000212000370004400052000

8、680007110008000900010000110001200013000weightparentlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112終態(tài)3 .算法設(shè)計題以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編寫以下算法：(1)統(tǒng)計二叉樹的葉結(jié)點個數(shù)。int LeafNodeCount(BiTree T) if(T=NULL)return 0;/如果是空樹，則葉子結(jié)點個數(shù)為0else if(T->lchild=NULL&&T->

9、;rchild=NULL)return 1;/判斷該結(jié)點是否是葉子結(jié)點(左孩子右孩子都為空)，若是則返回1elsereturn LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); (2)判別兩棵樹是否相等。(3)交換二叉樹每個結(jié)點的左孩子和右孩子。void ChangeLR(BiTree &T) BiTree temp;if(T->lchild=NULL&&T->rchild=NULL)return;else temp = T->lchild;T->lchild = T->rch

10、ild;T->rchild = temp;ChangeLR(T->lchild);ChangeLR(T->rchild);( 4)設(shè)計二叉樹的雙序遍歷算法(雙序遍歷是指對于二叉樹的每一個結(jié)點來說，先訪問這個結(jié)點， 再按雙序遍歷它的左子樹， 然后再一次訪問這個結(jié)點， 接下來按雙序遍歷它的 右子樹) 。void DoubleTraverse(BiTree T)if(T = NULL)return;else if(T->lchild=NULL&&T->rchild=NULL) cout<<T->data;elsecout<<

11、T->data;DoubleTraverse(T->lchild);cout<<T->data;DoubleTraverse(T->rchild);( 5)計算二叉樹最大的寬度(二叉樹的最大寬度是指二叉樹所有層中結(jié)點個數(shù)的最大值) 。 題目分析 求二叉樹高度的算法見上題。求最大寬度可采用層次遍歷的方法，記下各 層結(jié)點數(shù)，每層遍歷完畢，若結(jié)點數(shù)大于原先最大寬度，則修改最大寬度。int Width(BiTree bt)/ 求二叉樹 bt 的最大寬度 if (bt=null)return (0); / 空二叉樹寬度為 0elseBiTree Q;/Q 是隊列，元素

12、為二叉樹結(jié)點指針，容量足夠大front=1;rear=1;last=1;/front隊頭指針 ,rear 隊尾指針 ,last 同層最右結(jié)點在隊列中的位置temp=0; maxw=0; /tempQrear=bt; / while (front<=last)p=Qfront+; temp+; /記局部寬度, maxw 記最大寬度根結(jié)點入隊列同層元素數(shù)加1if (p->lchild!=null) Q+rear=p->lchild; /左子女入隊if (p->rchild!=null) Q+rear=p->rchild; /右子女入隊if (front>last

13、) /一層結(jié)束，last=rear;if (temp>maxw) maxw=temp;/last 指向下層最右元素, 更新當前最大寬度temp=0;/ if/ whilereturn (maxw);/ 結(jié)束 width( 6)用按層次順序遍歷二叉樹的方法，統(tǒng)計樹中具有度為1 的結(jié)點數(shù)目。int Level(BiTree bt) / 層次遍歷二叉樹，并統(tǒng)計度為 1 的結(jié)點的個數(shù) int num=0; /num 統(tǒng)計度為 1 的結(jié)點的個數(shù)if (bt)QueueInit(Q); QueueIn(Q,bt) ； /Q 是以二叉樹結(jié)點指針為元素的隊列 while (!QueueEmpty(Q)p

14、=QueueOut(Q); printf(p->data); /出隊 , 訪問結(jié)點if (p->lchild && !p->rchild |!p->lchild && p->rchild)num+;/度為1 的結(jié)點if (p->lchild) QueueIn(Q,p->lchild); /非空左子女入隊if (p->rchild) QueueIn(Q,p->rchild); /非空右子女入隊 / if (bt)return (num); / 返回度為 1 的結(jié)點的個數(shù)( 7)求任意二叉樹中第一條最長的路徑長度

15、，并輸出此路徑上各結(jié)點的值。 題目分析 因為后序遍歷棧中保留當前結(jié)點的祖先的信息， 用一變量保存棧的最高棧頂指針， 每當退棧時， 棧頂指針高于保存最高棧頂指針的值時， 則將該棧倒入輔助棧中， 輔助 棧始終保存最長路徑長度上的結(jié)點，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。void LongestPath(BiTree bt)/ 求二叉樹中的第一條最長路徑長度BiTree p=bt,l,s; /l, s是棧，元素是二叉樹結(jié)點指針， l 中保留當前最長路徑中的結(jié)點int i ， top=0,tag,longest=0;while (p | top>0) while (p) s+top=p；

16、tagtop=0; p=p->Lc; / 沿左分枝向下if (tagtop=1) / 當前結(jié)點的右分枝已遍歷 if (!stop->Lc && !stop->Rc) / 只有到葉子結(jié)點時，才查看路徑長度if (top>longest) for (i=1;i<=top;i+) li=si; longest=top; top-;/ 保留當前最長路徑到 l 棧，記住最高棧頂指針，退棧 else if (top>0) tagtop=1; p=stop.Rc; /沿右子分枝向下/ while (p!=null|top>0)/ 結(jié)束 LongestPath( 8)輸出二叉樹中從每個葉子結(jié)點到根結(jié)點的路徑。 題目分析 采用先序遍歷的遞歸方法，當找到葉子結(jié)點 *b 時，由于 *b 葉子結(jié)點尚未添加到path 中，因此在輸出路徑時還需輸出 b->data 值。對應(yīng)的遞歸算法如下：void AllPath(BTNode *b,ElemType path,int pathlen) int i;if (b!=NULL)為葉子結(jié)點if (b->lchild=NULL && b->rchild=NULL) /*b cout << " " << b-&