第六章樹與二叉樹實(shí)戰(zhàn)計(jì)算機(jī)科學(xué)系陳寶興算法與數(shù)據(jù)結(jié)構(gòu)(二)漳州師范學(xué)院計(jì)算機(jī)應(yīng)用專業(yè)考試大綱計(jì)算機(jī)操作系統(tǒng)部分包括：操作系統(tǒng)引論、進(jìn)程管理、處理機(jī)調(diào)度與死鎖、存儲(chǔ)器管理、設(shè)備管理、文件管理、操作系統(tǒng)接口、系統(tǒng)安全性等。數(shù)據(jù)結(jié)構(gòu)部分包括：線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找、排序等

數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)操作系統(tǒng)各75分。難易適中，難題表現(xiàn)在知識(shí)的靈活應(yīng)用，并有一定的技巧，此類題占10%左右。占60—80%的題目基本是優(yōu)秀本科生都能完成的。選擇題約30％，填空題約20％，問答題約20％，綜合、應(yīng)用題約30％?？佳行畔ⅲㄖ貜?fù)信息）距離網(wǎng)上報(bào)名截止時(shí)間還有9天：2006-10-10~2006-10-319:00~22:00現(xiàn)場(chǎng)確認(rèn)時(shí)間：2006-11-10~2006-11-141、報(bào)告2、本校考試大綱已經(jīng)發(fā)到郵箱里3、答案問題樹與二叉樹實(shí)戰(zhàn)重點(diǎn)，難點(diǎn)二叉樹性質(zhì)二叉樹遍歷森林轉(zhuǎn)化二叉樹哈夫曼編碼樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系(3分)樹和二叉樹邏輯上都是樹形結(jié)構(gòu)，區(qū)別有三：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分支的情況下，也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空。廈門大學(xué)二叉樹->性質(zhì)性質(zhì)1：在二叉樹的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)性質(zhì)2：深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)（k≥1）至少？？？考題：

深度為k的完全二叉樹至少有？個(gè)結(jié)點(diǎn)，至多有？個(gè)結(jié)點(diǎn)。2001廈門大學(xué)5分，1999南京理工大學(xué)4分

性質(zhì)3：

對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為

2

的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）福州大學(xué)2分考題中多會(huì)出現(xiàn)，葉子節(jié)點(diǎn)的個(gè)數(shù)，度為2的節(jié)點(diǎn)的個(gè)數(shù)，度為X的節(jié)點(diǎn)個(gè)數(shù)極重要考點(diǎn)：2003福州大學(xué)3分，2002廈門大學(xué)4分作業(yè)：設(shè)一棵二叉樹共有50個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)），則共有（）個(gè)度為2的結(jié)點(diǎn)?？碱}：已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有？個(gè)。4999廈門大學(xué)2000作業(yè)：在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（）?？碱}：已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹有？個(gè)葉子結(jié)點(diǎn)

612度為k已知在一棵含有n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)。試求該樹含有的葉子結(jié)點(diǎn)的數(shù)目.n0+nk=nk*nk=n-1A.(k-1)*nk+1

B.n-(n-1)/k觀察這兩棵樹，可以得到什么信息12345678910123456789101112131415二叉樹性質(zhì)對(duì)其是否滿足？節(jié)點(diǎn)i如果有左孩子，則左孩子為2i(偶數(shù))，如果有右孩子，則右孩子為2i+1(奇數(shù))。若i=1,則i無雙親；若i>1,則i的雙親為i/2。性質(zhì)5觀察這兩棵樹，可以得到什么信息完全二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為？節(jié)點(diǎn)總數(shù)的奇偶由誰來決定？已知完全二叉樹的結(jié)點(diǎn)總數(shù)，是否能確定各類結(jié)點(diǎn)的個(gè)數(shù)？12345678910123456789性質(zhì)6

zh完全二叉樹作業(yè)：一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。作業(yè)：在一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹中，所含葉子結(jié)點(diǎn)的數(shù)目為？個(gè)。考題：如果具有奇數(shù)個(gè)結(jié)點(diǎn)的近似滿二叉樹有M個(gè)葉結(jié)點(diǎn)，那么該樹的結(jié)點(diǎn)總數(shù)為？2003福州大學(xué)5017完全二叉樹->性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n

+1。根據(jù)結(jié)點(diǎn)數(shù)求完全二叉樹的高度作業(yè)14.具有2000個(gè)節(jié)點(diǎn)的二叉樹，其高度至少為（）。（A）9（B）10（C）11（D）12考題中不一定出現(xiàn)“完全二叉樹”完全二叉樹->性質(zhì)4一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）A.11B.10C.11至1025之間D.10至1024之間在結(jié)點(diǎn)為N的各棵樹中，高度最小的樹的高度為（），它有（）個(gè)葉結(jié)點(diǎn)，高度最大的樹的高度是（），它有（）個(gè)葉子結(jié)點(diǎn)。Answer:2,N-1,N,1南京理工1992年北京郵電大學(xué)，2005年福州大學(xué)10分設(shè)T是一棵二叉樹，除葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度數(shù)皆為2，若T中有6個(gè)葉子結(jié)點(diǎn)，試問：(1)二叉樹T的最大高度Hmax=?最小高度Hmin=?(2)二叉樹T中共有多少非葉結(jié)點(diǎn)？(3)若葉結(jié)點(diǎn)的權(quán)值為1，2，3，4，5，6。請(qǐng)構(gòu)造一棵哈夫曼樹，并計(jì)算該哈夫曼樹的權(quán)路徑長(zhǎng)度WPL.6,4,5,51性質(zhì)3、4結(jié)合浙江大學(xué)2004下列完全二叉樹共有k層及n個(gè)節(jié)點(diǎn)，試在下圖涂黑的節(jié)點(diǎn)(葉子)標(biāo)上相應(yīng)的序號(hào)(用k或n表示)。(5分)(n+1)/2,2k-1-1,2k-1,n123cdab分析所考知識(shí)點(diǎn)：2007.5.10二叉樹性質(zhì)2二叉樹性質(zhì)3二叉樹性質(zhì)5二叉樹性質(zhì)6:完全二叉樹總結(jié)點(diǎn)數(shù)的奇偶性與度為一結(jié)點(diǎn)數(shù)的關(guān)系總結(jié)點(diǎn)數(shù)為奇數(shù)度為一的結(jié)點(diǎn)數(shù)為0總結(jié)點(diǎn)數(shù)為偶數(shù)度為一的結(jié)點(diǎn)數(shù)為1二叉樹的邏輯結(jié)構(gòu)例如:

ABDCEF012345678910111213ABCDEF1401326二叉樹的順序存儲(chǔ)表示ADEBCFrootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):二叉樹的鏈?zhǔn)酱鎯?chǔ)表示n個(gè)結(jié)點(diǎn)的二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，空指針的數(shù)目是（）。Kn(K-1)+1中序序列：

DGBEAFCEABCDFGNILNILA00

C10

B00

D01

E11

F11

G11

10

thrt線索二叉樹及其存儲(chǔ)結(jié)構(gòu)ABCDEFGHK二叉樹的遍歷，例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCB

HKGFE

A作業(yè)選講及實(shí)戰(zhàn)：作業(yè)：已知一棵二叉樹的前序遍歷結(jié)果是ABECDFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，則它的后序遍歷結(jié)果是（）。EDCBIHJGFA

作業(yè)：已知一棵二叉樹的中序遍歷結(jié)果為DBHEAFICG，后序遍歷結(jié)果為DHEBIFGCA，畫出該二叉樹_______。福州大學(xué)：已經(jīng)一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為？試找出滿足下列條件的二叉樹1、前序序列與中序序列相同或?yàn)榭諛洌驗(yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹2、中序序列與后序序列相同或?yàn)榭諛洌驗(yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹3、前序序列與后序序列相同或?yàn)榭諛?，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹4、中序序列與層次遍歷序列相同或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹真題實(shí)戰(zhàn)：南開大學(xué)2000一棵非空的二叉樹的前序遍歷與后序遍歷序列正好相反，則該二叉樹一定滿足A、所有的結(jié)點(diǎn)均無左孩子B、所有的結(jié)點(diǎn)均無右孩子C、只有一個(gè)葉結(jié)點(diǎn)D、是任意一棵二叉樹Answer:A,B,C1、單支樹2、高度等于其結(jié)點(diǎn)數(shù)3、只有一個(gè)葉結(jié)點(diǎn)ABCDEFGroot

ABCEDFGABCEDFG

樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法root由下列三棵樹組成轉(zhuǎn)的森林換成一棵二叉樹由下列三棵樹組成轉(zhuǎn)的森林換成一棵二叉樹abcdeijnklmabcdeijnklm比較如下兩題：設(shè)F是由T1，T2，T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B。已知T1，T2，T3的結(jié)點(diǎn)分別為n1,n2,n3，則二叉樹B的左子樹有？個(gè)結(jié)點(diǎn)，二叉樹B的右子樹有？個(gè)結(jié)點(diǎn)。（5分）

n1-1n2+n3設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2，M3，與森林對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)為（）左子樹上的結(jié)點(diǎn)個(gè)數(shù)為（）2001北方交通大學(xué)2分2000南京理工大學(xué)3分2003福州大學(xué)5分哈夫曼樹哈夫曼樹是？北京理工大學(xué)2001帶權(quán)路徑長(zhǎng)度最小的二叉樹，又稱最優(yōu)二叉樹構(gòu)造哈夫曼樹的算法？P145若葉結(jié)點(diǎn)的權(quán)值為1，2，3，4，5，6。請(qǐng)構(gòu)造一棵哈夫曼樹，并計(jì)算該哈夫曼樹的權(quán)路徑長(zhǎng)度WPL.6,4,5,51哈夫曼樹的特點(diǎn)：哈夫曼樹的特點(diǎn)：沒有度為1的結(jié)點(diǎn)。如果一棵哈夫曼樹T有n0個(gè)葉結(jié)點(diǎn)，那么，樹T有多少個(gè)結(jié)點(diǎn)？要求給出求解過程。復(fù)旦大學(xué)：（10分）設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）福州大學(xué)2分2n-1廈門大學(xué)設(shè)用于通信的電文僅由8個(gè)字母組成，它們?cè)陔娢闹谐霈F(xiàn)的頻率分別為0.30，0.07，0.10，0.03，0.20，0.06，0.22，0.02，試設(shè)計(jì)哈夫曼樹及其編碼。使用0~7的二進(jìn)制表示形式是另一種編碼方案。給出兩種編碼的對(duì)照表、帶權(quán)路徑長(zhǎng)度WPL值并比較兩種方案的優(yōu)缺點(diǎn)。浙江大學(xué)2000（18分）給定一組項(xiàng)及其權(quán)值，假定項(xiàng)都存放于二叉樹的樹葉結(jié)點(diǎn)，則具有最小帶權(quán)外部路徑長(zhǎng)度的樹稱為Huffman樹。1．給出構(gòu)造Huffman樹的算法。P1452．給定項(xiàng)及相應(yīng)的權(quán)如下表，畫出執(zhí)行上述算法后得到的Huffman樹。

序號(hào)123456789項(xiàng)ABCDEFGHI權(quán)1567122546115考試內(nèi)容：1/3樹的后序遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的？序序列。(中序)表達(dá)式(15-3)*6/3*(20+6)的逆波蘭式(后綴表示:表達(dá)式的二叉樹表示的后序遍歷,見P.129)，正確的是（）；

A）15363206-*/*+B）153-6*3/206+*C）153-63206+*/*D）153-63*206+*/如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B為A的雙親，則B的度為（）。已知一棵二叉樹的前序結(jié)果為ABDEFHGC,中序遍歷結(jié)果為DBHFEGAC是否能確定一棵二叉樹，如能則畫出該二叉樹（6分）2/3福州大學(xué)2004年，所有有關(guān)樹的題目若二叉樹上只有度為0與2的結(jié)點(diǎn)，且度為0的結(jié)點(diǎn)數(shù)為h，則該二叉樹的結(jié)點(diǎn)數(shù)為？表達(dá)式(a+b)*(c+d)+(e+f)*h的后綴表達(dá)式為？已經(jīng)某字符串S中共出現(xiàn)8種字符，而且他們分別出現(xiàn)1,2,3,4,5,6,7,8次，若對(duì)S用碼集{0,1}進(jìn)行前綴編碼，則碼長(zhǎng)至少有？位2h-1,ab+cd+*ef+h*+,102(霍夫曼編碼)3/3福州大學(xué)2003年，所有有關(guān)樹的題目設(shè)樹T的度為4，其中度為1，2，3，4，的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1，則T中的葉子數(shù)為？已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為？8層近似滿二叉樹至少有？個(gè)結(jié)點(diǎn)高度為8的完全二叉樹至少有？個(gè)葉子結(jié)點(diǎn)。64深度為k的具有最少結(jié)點(diǎn)數(shù)的完全二叉樹按層次（同層次從左到右），用自然數(shù)依次編號(hào)，則編號(hào)最小的葉子結(jié)點(diǎn)的序號(hào)為？2k-2+1abchdefgijnklm請(qǐng)將下圖所示的森林轉(zhuǎn)換成二叉樹，并中序線索化該二叉樹，然后指出結(jié)點(diǎn)e的前驅(qū)與后繼結(jié)點(diǎn)；1998西安電子科技大學(xué)2005福州大學(xué)設(shè)F是一個(gè)森林，B是由F變換得到的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有？個(gè)(n+1)中序遍歷二叉樹非遞歸P131voidInOrder(BiTree

bt){BiTrees[100],p=bt;inttop=0;

//S是元素為二叉樹結(jié)點(diǎn)指針的棧

while(p||top){while(p){s[top++]=p;p=p->lchild;}//中序遍歷左子樹

if(top){p=s[--top];

printf(p->data);p=p->rchild;}//退棧，訪問，轉(zhuǎn)右子樹}}思考題:編程，判斷一棵二叉鏈表表示的二叉樹是否是完全二叉樹。【南京航空航天大學(xué)2001(10分)】

設(shè)二叉樹中結(jié)點(diǎn)的數(shù)據(jù)域的值互不相同，試設(shè)計(jì)一個(gè)算法將數(shù)據(jù)域值為x的結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的數(shù)據(jù)域打印出來?！颈狈浇煌ù髮W(xué)1996八(20分)】(上述兩題其存儲(chǔ)結(jié)構(gòu)均是二叉鏈表存儲(chǔ))1int

JudgeComplete(BiTree

bt)//判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0{inttag=0;BiTreep=bt,Q[];//Q是隊(duì)列，元素是二叉樹結(jié)點(diǎn)指針，容量足夠大if(p==null)return(1);QueueInit(Q);QueueIn(Q,p);//初始化隊(duì)列，根結(jié)點(diǎn)指針入隊(duì)while(!QueueEmpty(Q)){p=QueueOut(Q);//出隊(duì)

if(p->lchild&&!tag)QueueIn(Q,p->lchild);//左子女入隊(duì)

else{if(p->lchild)return0;//前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空

elsetag=1;}//首次出現(xiàn)結(jié)點(diǎn)為空

if(p->rchild&&!tag)QueueIn(Q,p->rchild);//右子女入隊(duì)

elseif(p->rchild)return0;elsetag=1;}//whilereturn1;}//JudgeComplete2.[題目分析]后序遍歷最后訪問根結(jié)點(diǎn)，當(dāng)訪問到值為x的結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先。voidSearch(BiTree

bt,ElemTypex)//在二叉樹bt中，查找值為x的結(jié)點(diǎn)，并打印其所有祖先{typedef

struct{BiTreet;inttag;}stack;//tag=0表示左子女被訪問，tag=1表示右子女被訪問stacks[];//棧容量足夠大top=0;while(bt!=null||top>0){while(bt!=null&&bt->data!=x)//結(jié)點(diǎn)入棧

{s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分枝向下

if(bt->data==x){printf(“所查結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的值為:\n”);//找到xfor(i=1;i<=top;i++)printf(s[i].t->data);return;}//輸出祖先值后結(jié)束

while(top!=0&&s[top].tag==1)top--;//退棧（空遍歷）

if(top!=0){s[top].tag=1;bt=s[top].t->rchild;}//沿右分枝向下遍歷

}//while(bt!=null||top>0)}結(jié)束search

因?yàn)椴檎业倪^程就是后序遍歷的過程，使用的棧的深度不超過樹的深度，算法復(fù)雜度為O(logn)。第二題的另一解法:voidSearch(BiTree

bt,ElemTypex)//在二叉樹bt中，查找值為x的結(jié)點(diǎn)，并打印其所有祖先{BiTreep=bt,Q[];//Q是隊(duì)列，元素是二叉樹結(jié)點(diǎn)指針，容量足夠大int

bh,order,find=0;struct{intt;int

zx;}s[];//數(shù)組容量足夠大,zx表示結(jié)點(diǎn)雙親之序號(hào)

QueueInit(Q);QueueIn(Q,p);s[0].t=p->data;bh=-1;order=1;s[0].zx=bh;//初始化隊(duì)列，根結(jié)點(diǎn)指針入隊(duì)while(!QueueEmpty(Q)){p=Queu