第6章樹(shù)與二叉樹(shù)B

1第6章樹(shù)和二叉樹(shù)（Tree&BinaryTree）6.1樹(shù)的基本概念6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.5赫夫曼樹(shù)及其應(yīng)用（本章及本課程的重點(diǎn)）上機(jī)內(nèi)容：

Huffman編/譯碼器的設(shè)計(jì)與實(shí)現(xiàn)（實(shí)驗(yàn)要求參見(jiàn)嚴(yán)題集P149）26.2二叉樹(shù)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹(shù)？二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性。1. 二叉樹(shù)的定義2. 二叉樹(shù)的性質(zhì)3. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（二叉樹(shù)的運(yùn)算見(jiàn)下一節(jié)）32.二叉樹(shù)的性質(zhì)(3+2)性質(zhì)1:在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>0）。性質(zhì)2:深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k>0）。性質(zhì)3:對(duì)于任何一棵二叉樹(shù)，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）課堂練習(xí)：1.樹(shù)Ｔ中各結(jié)點(diǎn)的度的最大值稱(chēng)為樹(shù)Ｔ的

。

Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度2.深度為k的二叉樹(shù)的結(jié)點(diǎn)總數(shù)，最多為

個(gè)。

Ａ)２k-1

Ｂ)log2kＣ)２k－１Ｄ)２k3.深度為9的二叉樹(shù)中至少有

個(gè)結(jié)點(diǎn)。

Ａ)２9

Ｂ)２8

Ｃ)９Ｄ)２9－1√√√4對(duì)于兩種特殊形式的二叉樹(shù)（滿(mǎn)二叉樹(shù)和完全二叉樹(shù)），還特別具備以下2個(gè)性質(zhì)：性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為log2n＋1性質(zhì)5:對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為i

的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)為2i＋1；其雙親的編號(hào)必為i/2（i＝1時(shí)為根,除外）。證明：根據(jù)性質(zhì)2，深度為k的二叉樹(shù)最多只有2k-1個(gè)結(jié)點(diǎn)，且完全二叉樹(shù)的定義是與同深度的滿(mǎn)二叉樹(shù)前面編號(hào)相同，即它的總結(jié)點(diǎn)數(shù)n位于k層和k-1層滿(mǎn)二叉樹(shù)容量之間，即2k-1-1<n≤2k-1或2k-1≤n<2k三邊同時(shí)取對(duì)數(shù)，于是有：k-1≤log2n<k因?yàn)閗是整數(shù)，所以k=log2n+1可根據(jù)歸納法證明。5課堂討論：Q1：滿(mǎn)二叉樹(shù)和完全二叉樹(shù)有什么區(qū)別？A1：滿(mǎn)二叉樹(shù)是葉子一個(gè)也不少的樹(shù)，而完全二叉樹(shù)雖然前n-1層是滿(mǎn)的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。

滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。Q3:設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，則它有

個(gè)葉子結(jié)點(diǎn)，有

個(gè)度為2的結(jié)點(diǎn)，有

個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有

個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。48948810Q2：為什么要研究滿(mǎn)二叉樹(shù)和完全二叉樹(shù)這兩種特殊形式？A1：因?yàn)橹挥羞@兩種形式可以實(shí)現(xiàn)順序存儲(chǔ)！由于最后一層葉子數(shù)為489個(gè)，是奇數(shù)，說(shuō)明有1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)；而完全二叉樹(shù)中不可能出現(xiàn)非空右子樹(shù)(0個(gè))。A3：易求出總層數(shù)和末層葉子數(shù)?？倢訑?shù)k=log2n＋1=10;且前9層總結(jié)點(diǎn)數(shù)為29-1=511

(完全二叉樹(shù)的前k-1層肯定是滿(mǎn)的)所以末層葉子數(shù)為1000-511=489個(gè)。6請(qǐng)注意葉子結(jié)點(diǎn)總數(shù)≠末層葉子數(shù)！還應(yīng)當(dāng)加上第k-1層（靠右邊）的0度結(jié)點(diǎn)個(gè)數(shù)。分析：末層的489個(gè)葉子只占據(jù)了上層的245個(gè)結(jié)點(diǎn)（489/2)上層（k=9)右邊的0度結(jié)點(diǎn)數(shù)還有29-1-245=11個(gè)！另一法：可先求2度結(jié)點(diǎn)數(shù),再由此得到葉子總數(shù)。首先，k-2層的28-1（255）個(gè)結(jié)點(diǎn)肯定都是2度的（完全二叉）另外，末層葉子（剛才已求出為489）所對(duì)應(yīng)的雙親也是度＝2，（共有489/2＝244個(gè)）。所以，全部2度結(jié)點(diǎn)數(shù)為255(k-2層)＋244(k-1層)=499個(gè)；總?cè)~子數(shù)＝2度結(jié)點(diǎn)數(shù)＋1=500個(gè)。第i層上的滿(mǎn)結(jié)點(diǎn)數(shù)為2i-1所以，全部葉子數(shù)＝489(末層)＋11(k-1層)=500個(gè)。度為2的結(jié)點(diǎn)＝葉子總數(shù)－1=499個(gè)。74.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)按二叉樹(shù)的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問(wèn)：順序存儲(chǔ)后能否復(fù)原成唯一對(duì)應(yīng)的二叉樹(shù)形狀？答：若是完全/滿(mǎn)二叉樹(shù)則可以做到唯一復(fù)原。而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)5）例如，對(duì)應(yīng)[2]的兩個(gè)孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。T[0]一般不用8討論：不是完全二叉樹(shù)怎么辦？答：一律轉(zhuǎn)為完全二叉樹(shù)！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便

9二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_childright_childdataleft_childright_child二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)類(lèi)型定義：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;一般從根結(jié)點(diǎn)開(kāi)始存儲(chǔ)。

（相應(yīng)地，訪問(wèn)樹(shù)中結(jié)點(diǎn)時(shí)也只能從根開(kāi)始）注：如果需要倒查某結(jié)點(diǎn)的雙親，可以再增加一個(gè)雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。10例：

ABECD^AB^D^C^^E^116.3遍歷二叉樹(shù)和線索二叉樹(shù)一、遍歷二叉樹(shù)（TraversingBinaryTree）遍歷定義——指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱(chēng)周游）。遍歷用途——它是樹(shù)結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹(shù)一切運(yùn)算的基礎(chǔ)和核心。

遍歷方法——牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看都是“先左后右”。12遍歷規(guī)則———二叉樹(shù)由根、左子樹(shù)、右子樹(shù)構(gòu)成，定義為D、

L、RD、L、R的組合定義了六種可能的遍歷方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，則有三種實(shí)現(xiàn)方案：

DLRLDRLRD先(根)序遍歷中(根)序遍歷后(根)序遍歷

注：“先、中、后”的意思是指訪問(wèn)的結(jié)點(diǎn)D是先于子樹(shù)出現(xiàn)還是后于子樹(shù)出現(xiàn)。13例1：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：ABCDEABDECDBEACDEBCA口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根14+*A*/EDCB先序遍歷+**/ABCDE前綴表示中序遍歷A/B*C*D+E中綴表示后序遍歷AB/C*D*E+后綴表示層序遍歷+*E*D/CAB例2：用二叉樹(shù)表示算術(shù)表達(dá)式15遍歷的算法實(shí)現(xiàn)：用遞歸形式格外簡(jiǎn)單！回憶1：二叉樹(shù)結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型定義：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;則三種遍歷算法可寫(xiě)出:回憶2：第1章自測(cè)卷4.2題：longintfact(n)//求n!intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}16先序遍歷算法DLR(liuyu*root){if(root!=NULL)//非空二叉樹(shù)

{printf(“%d”,root->data);//訪問(wèn)DDLR(root->lchild);//遞歸遍歷左子樹(shù)DLR(root->rchild);//遞歸遍歷右子樹(shù)

}return(0);}中序遍歷算法LDR(x*root){if(root!=NULL){LDR(root->lchild);printf(“%d”,root->data);

LDR(root->rchild);}return(0);}后序遍歷算法LRD(x*root){if(root!=NULL)

{LRD(root->lchild);LRD(root->rchild);printf(“%d”,root->data);}return(0);}結(jié)點(diǎn)數(shù)據(jù)類(lèi)型自定義typedefstructliuyu{intdata;structliuyu*lchild,*rchild；}liuyu;liuyu*root;

17對(duì)遍歷的分析：1.

從前面的三種遍歷算法可以知道：如果將print語(yǔ)句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說(shuō)這三種遍歷算法的訪問(wèn)路徑是相同的，只是訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過(guò)3次。AFEDCBG第1次經(jīng)過(guò)時(shí)訪問(wèn)＝先序遍歷第2次經(jīng)過(guò)時(shí)訪問(wèn)＝中序遍歷第3次經(jīng)過(guò)時(shí)訪問(wèn)＝后序遍歷2.二叉樹(shù)遍歷的時(shí)間效率和空間效率時(shí)間效率:O(n)

//每個(gè)結(jié)點(diǎn)只訪問(wèn)一次空間效率:O(n)

//棧占用的最大輔助空間（精確值：樹(shù)深為k的遞歸遍歷需要k+1個(gè)輔助單元！）18例：【嚴(yán)題集6.42③】編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。

思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來(lái)。DLR(liuyu*root)//采用中序遍歷的遞歸算法{if(root!=NULL)//非空二叉樹(shù)條件，還可寫(xiě)成if(root){if(!root->lchild&&!root->rchild)//是葉子結(jié)點(diǎn)則統(tǒng)計(jì)并打印

{sum++;printf("%d\n",root->data);}

DLR(root->lchild);//遞歸遍歷左子樹(shù)，直到葉子處；

DLR(root->rchild);}//遞歸遍歷右子樹(shù)，直到葉子處；}return(0);}19注：要實(shí)現(xiàn)遍歷運(yùn)算必須先把二叉樹(shù)存入機(jī)內(nèi)。思路：利用前序遍歷來(lái)建樹(shù)

（結(jié)點(diǎn)值陸續(xù)從鍵盤(pán)輸入，用DLR為宜）BintreecreateBTpre(){BintreeT;charch;scanf(“%c”,&ch);if(ch==’’)T=NULL;else{T=(Bintree)malloc(sizeof(BinTNode));T->data=ch;T->lchild=createBTpre();T->rchild=createBTpre();}returnT;}怎樣建樹(shù)？見(jiàn)教材P131程序。20習(xí)題討論：1.求二叉樹(shù)深度，或從x結(jié)點(diǎn)開(kāi)始的子樹(shù)深度。

算法思路：只查各結(jié)點(diǎn)后繼鏈表指針，若左(右)孩子的左(右)指針?lè)强?，則層次數(shù)加1；否則函數(shù)返回。技巧：遞歸時(shí)應(yīng)當(dāng)從葉子開(kāi)始向上計(jì)數(shù)，層深者保留。否則不易確定層數(shù)。2.按層次輸出二叉樹(shù)中所有結(jié)點(diǎn)。

算法思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹(shù)結(jié)點(diǎn)的指針是個(gè)好辦法，而不必拘泥于遞歸算法。技巧：當(dāng)根結(jié)點(diǎn)入隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì)，……由此便可產(chǎn)生按層次輸出的效果。ABCDE213中序遍歷的非遞歸(迭代)算法算法思路：若不用遞歸，則要實(shí)現(xiàn)二叉樹(shù)遍歷的“嵌套”規(guī)則，必用堆棧?？芍苯佑脀hile語(yǔ)句和push/pop操作。參見(jiàn)教材P130-131程序。4.判別給定二叉樹(shù)是否為完全二叉樹(shù)（即順序二叉樹(shù)）。

算法思路：完全二叉樹(shù)的特點(diǎn)是：沒(méi)有左子樹(shù)空而右子樹(shù)單獨(dú)存在的情況(前k-1層都是滿(mǎn)的，且第k層左邊也滿(mǎn)）。技巧:按層序遍歷方式，先把所有結(jié)點(diǎn)（不管當(dāng)前結(jié)點(diǎn)是否有左右孩子）都入隊(duì)列.若為完全二叉樹(shù),則層序遍歷時(shí)得到的肯定是一個(gè)連續(xù)的不包含空指針的序列.如果序列中出現(xiàn)了空指針，則說(shuō)明不是完全二叉樹(shù)。22特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹(shù)？【嚴(yán)題集6.31④】

證明：由一棵二叉樹(shù)的先序序列和中序序列可唯一確定這棵二叉樹(shù)。

例：已知一棵二叉樹(shù)的中序序列和后序序列分別是BDCEAFHG

和DECBHGFA，請(qǐng)畫(huà)出這棵二叉樹(shù)。分析：①由后序遍歷特征，根結(jié)點(diǎn)必在后序序列尾部（即A）；②由中序遍歷特征，根結(jié)點(diǎn)必在其中間，而且其左部必全部是左子樹(shù)子孫（即BDCE），其右部必全部是右子樹(shù)子孫（即FHG）；③繼而，根據(jù)后序中的DECB子樹(shù)可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類(lèi)推。23中序遍歷：BDCEAFHG

后序遍歷：DECBHGFA（BDCE）（FHG）ABF

（DCE）

（HG）CDEGHABBFF24問(wèn)：用二叉鏈表法（l_child,r_child）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針？分析：用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)必有2n個(gè)鏈域（見(jiàn)二叉鏈表數(shù)據(jù)類(lèi)型說(shuō)明）。 最壞情況：除根結(jié)點(diǎn)外，二叉樹(shù)中每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親（直接前驅(qū)），所以只會(huì)有n－1個(gè)結(jié)點(diǎn)的鏈域存放指針，指向非空子女結(jié)點(diǎn)（即直接后繼）。思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——我們可以用它來(lái)存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線索，以加快查找速度。所以，空指針數(shù)目＝2n－(n-1)=n+1個(gè)。n+125二、線索二叉樹(shù)（ThreadedBinaryTree）普通二叉樹(shù)只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過(guò)程中獲得。若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來(lái)，則從第一個(gè)結(jié)點(diǎn)開(kāi)始就能很快“順藤摸瓜”而遍歷整個(gè)樹(shù)了。兩種解決方法增加兩個(gè)域：fwd和bwd；利用空鏈域（n+1個(gè)空鏈域）存放前驅(qū)指針存放后繼指針如何預(yù)存這類(lèi)信息？例如中序遍歷結(jié)果：BDCEAFHG，實(shí)際上已將二叉樹(shù)轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！可能是根、或最左（右）葉子26規(guī)定：1）若結(jié)點(diǎn)有左子樹(shù)，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹(shù)，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)

。為了避免混淆，增加兩個(gè)標(biāo)志域，如下圖所示：lchildLTagdataRTagrchild約定:當(dāng)Tag域?yàn)?時(shí),表示正常情況;當(dāng)Tag域?yàn)?時(shí),表示線索情況.27有關(guān)線索二叉樹(shù)的幾個(gè)術(shù)語(yǔ)：

線索鏈表：用前頁(yè)結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表線索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹(shù)：加上線索的二叉樹(shù)（圖形式樣）線索化：對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程注：在線索化二叉樹(shù)中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的，當(dāng)標(biāo)志為0時(shí)，則需要通過(guò)一定運(yùn)算才能找到它的后繼。28dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例1：帶了兩個(gè)標(biāo)志的某先序遍歷結(jié)果如表所示，請(qǐng)畫(huà)出對(duì)應(yīng)二叉樹(shù)。29ABCGEIDHFroot懸空？懸空？解：該二叉樹(shù)中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：例2：畫(huà)出以下二叉樹(shù)對(duì)應(yīng)的中序線索二叉樹(shù)。為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)30對(duì)應(yīng)的中序線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H