數據結構第六章2課件

第6章樹和二叉樹

（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應用二叉樹的定義、性質和存儲結構二叉樹的運算16.2二叉樹為何要重點研究每結點最多只有兩個“叉”的樹？二叉樹的結構最簡單，規(guī)律性最強；可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。6.2.1 二叉樹的定義6.2.2 二叉樹的性質6.2.3二叉樹的存儲結構26.2.2二叉樹的性質

(3+2)性質1:在二叉樹的第i層上至多有2i-1個結點（i>0）。性質2:深度為k的二叉樹至多有2k-1個結點（k>0）。性質3:對于任何一棵二叉樹，若2度的結點數有n2個，則葉子數（n0）必定為n2＋1（即n0=n2+1）對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備以下2個性質：性質4:具有n個結點的完全二叉樹的深度必為log2n＋1性質5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結點，其左孩子編號必為2i，其右孩子編號為2i＋1；其雙親的編號必為i/2（i＝1時為根,除外）。

36.2.3二叉樹的存儲結構一、順序存儲結構按二叉樹的結點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問：順序存儲后能否復原成唯一對應的二叉樹形狀？答：若是完全/滿二叉樹則可以做到唯一復原。而且有規(guī)律：下標值為i的雙親，其左孩子的下標值必為2i，其右孩子的下標值必為2i＋1（即性質5）例如，對應[2]的兩個孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。T[0]一般不用5討論：不是完全二叉樹怎么辦？答：一律轉為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結點”，其內容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點：①浪費空間；②插入、刪除不便

6二、鏈式存儲結構

用二叉鏈表即可方便表示。dataleft_childright_childdataleft_childright_child二叉樹結點數據類型定義：typedefstructnode

*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,

right_child;}node;一般從根結點開始存儲。

（相應地，訪問樹中結點時也只能從根開始）注：如果需要倒查某結點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。7二叉樹鏈式存儲舉例：

ABECD^AB^D^C^^E^優(yōu)點：①不浪費空間；②插入、刪除方便

8遍歷規(guī)則———二叉樹由根、左子樹、右子樹構成，定義為D、

L、R以根結點為參照系注：“先、中、后”的意思是指訪問的結點D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。

D、L、R的組合定義了六種可能的遍歷方案：LDR,LRD,DLR,DRL,RDL,RLD

若限定先左后右，則有三種實現(xiàn)方案：DLRLDRLRD先序遍歷中序遍歷后序遍歷

10+*A*/EDCB先序遍歷結果+**/ABCDE—前綴表示法中序遍歷結果A/B*C*D+E—中綴表示法后序遍歷結果AB/C*D*E+—后綴表示法層次遍歷結果+*E*D/CAB例2：用二叉樹表示算術表達式12對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將print語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結點的時機不同。從虛線的出發(fā)點到終點的路徑上，每個結點經過3次。AFEDCBG第1次經過時訪問，是先序遍歷第2次經過時訪問，是中序遍歷第3次經過時訪問，是后序遍歷2.二叉樹遍歷的時間效率和空間效率時間效率:O(n)

//每個結點只訪問一次空間效率:O(n)

//棧占用的最大輔助空間精確值：樹深為k的遞歸遍歷需要k+1個輔助單元14例：【嚴題集6.42③】編寫遞歸算法，計算二叉樹中葉子結點的數目。

思路：若左右指針均空，必為葉子?？蛇x用任何一種遍歷算法查找葉子，將其統(tǒng)計并打印出來。DLR(node*root)//采用先序遍歷的遞歸算法{if(root!=NULL)//非空二叉樹條件，等效于if(root){if(!root->lchild&&!root->rchild)//是葉子結點則統(tǒng)計并打印{sum++;printf("%d\n",root->data);}

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

DLR(root->rchild);}//遞歸遍歷右子樹，直到葉子處；}return(0);}15用空格字符表示‘無孩子’或指針為空如何把二叉樹存入電腦內？怎樣建樹？見教材P131例例：將下面的二叉樹以二叉鏈表形式存入計算機內。ABGDFCE考慮1：輸入結點時怎樣表示“無孩子”？考慮2：以何種遍歷方式來輸入和建樹？將二叉樹按先序遍歷次序輸入：ABC

DE

G

F

(/n)以先序遍歷最為合適，讓每個結點都能及時被連接到位。字符串輸完后應當再加一特殊的結束符號(如$)，因為

無法唯一表示結束。16建樹算法：StatusCreateBiTree(BiTree&T){//構造二叉樹Tscanf(“%c”,&ch);if(ch==’’)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(overflow);T->data=ch;//生成根結點CreateBiTree(T->lchild);//構造左子樹CreateBiTree(T->rchild);//構造右子樹}returnOK;}//CreateBiTree輸入序列：

ABC

DE

G

F

17特別討論：若已知先序（或后序）遍歷結果和中序遍歷結果，能否“恢復”出二叉樹？例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請畫出這棵二叉樹。分析：①由后序遍歷特征，根結點必在后序序列尾部（即A）；②由中序遍歷特征，根結點必在其中間，而且其左部必全部是左子樹的子孫（即BDCE），其右部必全部是右子樹的子孫（即FHG）；③繼而，根據后序中的DECB子樹可確定B為A的左孩子，根據HGF子串可確定F為A的右孩子；以此類推?！緡李}集6.31④】請證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。

186.3.2線索二叉樹所以，空指針數目＝2n－(n-1)=n+1個。證明：用二叉鏈表存儲包含n個結點的二叉樹，結點必有2n個鏈域（見二叉鏈表數據類型說明）。除根結點外，二叉樹中每一個結點有且僅有一個雙親，意即每個結點地址占用了雙親的一個直接后繼，n個結點地址共占用了n-1個雙親的指針域。也就是說，只會有n－1個結點的鏈域存放指針。ThreadedBinaryTree討論：用二叉鏈表法（l_child,r_child）存儲包含n個結點的二叉樹，結點的指針區(qū)域中會有多少個空指針？有n+1個！或2*n0+1*n1+0*n2=n0+n1+n2+1=n+120思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——我們可以用它來存放當前結點的直接前驅和后繼等線索，以加快查找速度。結論：用二叉鏈表法存儲包含n個結點的二叉樹，結點的指針區(qū)域中會有n+1個空指針。這就是線索二叉樹（ThreadedBinaryTree）21①每個結點增加兩個域：fwd和bwd；存放前驅指針存放后繼指針如何預存這類信息？有兩種解決方法：②與原有的左右孩子指針域“復用”，充分利用那n+1個空鏈域。規(guī)定：1）若結點有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(即線索)；2）若結點有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。datalchildrchildfwdbwddatalchildrchild缺點：空間效率太低！問題：計算機如何判斷是孩子指針還是線索指針？如何區(qū)別？23lchildLTagdataRTagrchild約定:當Tag域為0時,表示正常情況;當Tag域為1時,表示線索情況.前驅(后繼)左(右)孩子為區(qū)別兩種不同情況，特增加兩個標志域：問：增加了前驅和后繼等線索有什么好處？——能方便找出當前結點的前驅和后繼，不用堆棧（遞歸）也能遍歷整個樹。各1bit24dataAGEIDJHCFBLtag0011110101Rtag0001010111AGEIDJHCFB例：帶了兩個標志的某先序遍歷結果如下表所示，請畫出對應的二叉樹。ATag=1表示線索:Ltag=1表示前驅Rtag=1表示后繼26ABCGEIDHFroot懸空？NIL懸空？NIL解：對該二叉樹中序遍歷的結果為:

H,D,I,B,E,A,F,C,G所以添加線索應當按如下路徑進行：為避免懸空態(tài)，應增設一個頭結點例1：畫出以下二叉樹對應的中序線索二叉樹。2.線索二叉樹的生成——線索化線索化過程就是在遍歷過程中修改空指針的過程2700A00C00B11E11F11G00D11I11H注：此圖中序遍歷結果為:

H,D,I,B,E,A,F,C,

G0root0對應的中序線索二叉樹存儲結構如圖所示：28線索二叉樹的生成算法（遞歸算法見教材P134-135）目的：在遍歷二叉樹的過程中修改空指針，添加前驅或后繼的線索，使之成為線索二叉樹。為了記下遍歷過程中訪問結點的先后次序，需要設置兩個指針：p指針→當前結點之指針；pre指針→當前結點的前趨結點指針。設計技巧：依某種順序遍歷二叉樹，對每個結點p，判斷其左指針是否為空，以及其前驅結點的右指針是否為空。每次只修改前驅結點的右指針（后繼）和本結點的左指針（前驅），參見算法6.6。若p->lchild＝NULL,則{p->Ltag=1;p->lchild＝pre;}

//p的前驅線索應存p結點的左邊若pre->rchild＝NULL,則{pre->Rtag＝1;pre->rchild=p;}

//pre的后繼線索應存pre結點的右邊303.線索二叉樹的遍歷（無需堆棧）對于線索二叉樹的遍歷，只要找到序列中的第一個結點，然后依次訪問結點的后繼直到后繼為空為止。（因為建立線索時已遍歷一次，相當于線性化了！）難點：在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，當標志為0時，則需要通過一定運算才能找到它的后繼。以中序線索二叉樹為例：當RTag=1時，直接后繼指針就在其rchild域內；當R