數(shù)據(jù)結(jié)構(gòu)第六章樹(shù)B課件

第6章樹(shù)和二叉樹(shù)（Tree&BinaryTree）6.1樹(shù)的基本概念6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.5哈夫曼樹(shù)及其應(yīng)用6.2二叉樹(shù)1. 二叉樹(shù)的定義2. 二叉樹(shù)的性質(zhì)3. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（二叉樹(shù)的運(yùn)算見(jiàn)下一節(jié)）2.二叉樹(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）對(duì)于兩種特殊形式的二叉樹(shù)（滿二叉樹(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í)為根,除外）。

3.二叉樹(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ù)形狀？答：若是完全/滿二叉樹(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]一般不用討論：不是完全二叉樹(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)空間；②插入、刪除不便

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

datal_childr_childdataLCHILDRCHILD二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)類型定義：typedefstructBiTNode

{

TElemType

data;

structBiTNode

*l_child,*r_child;}BiTNode,*BiTree;二叉鏈表的結(jié)點(diǎn)類型PARENTlchilddatarchildparent三叉鏈表的結(jié)點(diǎn)類型例：

ABECD^AB^D^C^^E^空指針個(gè)數(shù)：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1一般從根結(jié)點(diǎn)開(kāi)始存儲(chǔ)。

（相應(yīng)地，訪問(wèn)樹(shù)中結(jié)點(diǎn)時(shí)也只能從根開(kāi)始）^遍歷規(guī)則———二叉樹(shù)由根、左子樹(shù)、右子樹(shù)構(gòu)成，定義為D、L、R注：“先、中、后”的意思是指訪問(wèn)結(jié)點(diǎn)D的操作是先于子樹(shù)出現(xiàn)還是后于子樹(shù)出現(xiàn)。

D、L、R的組合定義了六種可能的遍歷方案：

DLR,

LDR,LRD,

DRL,RDL,RLD

若限定先左后右，則有三種實(shí)現(xiàn)方案：

DLRLDRLRD先序遍歷中序遍歷后序遍歷

若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:遍歷算法的遞歸描述Preorder(BiTreeT）

{//

先序遍歷二叉樹(shù)

if(T){

visit(T->data);//訪問(wèn)結(jié)點(diǎn)

Preorder(T->lchild);//遍歷左子樹(shù)

Preorder(T->rchild);//遍歷右子樹(shù)

}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回pre(TR);先序序列：ABDCT>T>對(duì)遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將print語(yǔ)句抹去，從遞歸執(zhí)行過(guò)程看，這三種算法是完全相同的，或者說(shuō)這三種算法遍歷過(guò)程中經(jīng)過(guò)結(jié)點(diǎn)的路線是相同的，只是訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路線上，每個(gè)結(jié)點(diǎn)經(jīng)過(guò)3次。第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)

//棧占用的最大輔助空間AFEDCBG-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef例:前綴表示中綴表示后綴表示1、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)遍歷算法的應(yīng)用舉例void

CountLeaf

(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;//對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->lchild,count);

CountLeaf(

T->rchild,count);}//if}//CountLeaf思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計(jì)并打印出來(lái)。用空格字符表示‘無(wú)孩子’或指針為空2、要實(shí)現(xiàn)遍歷運(yùn)算，必須先把二叉樹(shù)存入電腦內(nèi)怎樣建樹(shù)？見(jiàn)教材P131例例：將下面的二叉樹(shù)以二叉鏈表形式存入計(jì)算機(jī)內(nèi)。ABGDFCE考慮1：輸入結(jié)點(diǎn)時(shí)怎樣表示“無(wú)孩子”？考慮2：以何種遍歷方式來(lái)輸入和建樹(shù)？將二叉樹(shù)按先序遍歷次序輸入：ABC

DE

G

F

以先序遍歷最為合適，讓每個(gè)結(jié)點(diǎn)都能及時(shí)被連接到位。ABGDFCE^^^^^^AB

C

D

ABCD上頁(yè)算法執(zhí)行過(guò)程舉例如下：ATBCD^^^^^

僅知二叉樹(shù)的先序序列“abcdefg”能唯一確定一棵二叉樹(shù)

如果同時(shí)已知二叉樹(shù)的中序序列“cbdaegf”，則會(huì)如何？

二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根？不能特別討論：若已知先序（或后序）遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹(shù)？已知中序遍歷：BDCEAFHG已知后序遍歷：DECBHGFA（BDCE）（FHG）A（DCE）BFGHCDEABB已知中序遍歷和后序遍歷結(jié)果，畫(huà)出二叉樹(shù)(或給出先序遍歷結(jié)果)ACCD

C

E思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——我們可以用它來(lái)存放當(dāng)前結(jié)點(diǎn)在某一遍歷序列中的直接前驅(qū)和后繼等線索，以加快查找速度。用二叉鏈表法存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的指針區(qū)域中會(huì)有n+1個(gè)空指針。線索二叉樹(shù)①每個(gè)結(jié)點(diǎn)增加兩個(gè)域：fwd和bwd；存放前驅(qū)指針存放后繼指針如何預(yù)存這類信息？有兩種解決方法：②與原有的左右孩子指針域“復(fù)用”，充分利用那n+1個(gè)空鏈域。規(guī)定：1）若結(jié)點(diǎn)有左子樹(shù)，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹(shù)，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。datalchildrchildfwdbwddatalchildrchild缺點(diǎn)：空間效率太低！問(wèn)題：計(jì)算機(jī)如何判斷是孩子指針還是線索指針？如何區(qū)別？lchildLTagdataRTagrchild約定:當(dāng)Tag域?yàn)?時(shí),表示正常情況;當(dāng)Tag域?yàn)?時(shí),表示線索情況.前驅(qū)(后繼)左(右)孩子為區(qū)別兩種不同情況，特增加兩個(gè)標(biāo)志域：?jiǎn)枺涸黾恿饲膀?qū)和后繼等線索有什么好處？——能方便找出當(dāng)前結(jié)點(diǎn)在某一序列中的前驅(qū)和后繼，不用堆棧（遞歸）也能遍歷整個(gè)樹(shù)。各1bit1.有關(guān)線索二叉樹(shù)的幾個(gè)術(shù)語(yǔ)：

線索鏈表：線索：線索二叉樹(shù)：線索化：用含Tag的結(jié)點(diǎn)樣式所構(gòu)成的二叉鏈表指向結(jié)點(diǎn)前驅(qū)和后繼的指針加上線索的二叉樹(shù)對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程線索化過(guò)程就是在遍歷過(guò)程中修改空指針的過(guò)程：將空的lchild改為結(jié)點(diǎn)的直接前驅(qū)；將空的rchild改為結(jié)點(diǎn)的直接后繼。非空指針呢？仍然指向孩子結(jié)點(diǎn)（稱為“正常情況”）ABCGEIDHFroot懸空？NIL懸空？NIL解：對(duì)該二叉樹(shù)中序遍歷的結(jié)果為:

H,D,I,B,E,A,F,C,G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)例1：畫(huà)出以下二叉樹(shù)對(duì)應(yīng)的中序線索二叉樹(shù)。2.線索二叉樹(shù)的生成——線索化線索化過(guò)程就是在遍歷過(guò)程中修改空指針的過(guò)程00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,

G對(duì)應(yīng)的中序線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)（鏈表）如圖所示：0root0例2：給定如圖所示二叉樹(shù)T，請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線索二叉樹(shù)。

2825405560330854解:因?yàn)橹行虮闅v序列是：5540256028083354對(duì)應(yīng)線索樹(shù)應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹(shù)中添加虛線。NILNIL3.線索二叉樹(shù)的遍歷（無(wú)需堆棧）對(duì)于線索二叉樹(shù)的遍歷，只要找到序列中的第一個(gè)結(jié)點(diǎn)，然后依次訪問(wèn)結(jié)點(diǎn)的后繼直到后繼為