5.1樹(shù)和二叉樹(shù)的基本概念第5章樹(shù)和二叉樹(shù)5.1.1樹(shù)的定義及相關(guān)術(shù)語(yǔ)1．樹(shù)的定義樹(shù)(Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T，n=0時(shí)稱(chēng)為空樹(shù)，否則它滿(mǎn)足如下兩個(gè)條件：（1）有且僅有一個(gè)特定的稱(chēng)為根(Root)的結(jié)點(diǎn)；（2）其余的結(jié)點(diǎn)可分為m(m>=0)個(gè)互不相交的子集T1、T2、T3、???、Tm，其中每個(gè)子集又是一棵樹(shù)，并稱(chēng)其為根結(jié)點(diǎn)的子樹(shù)(Subtree)。從樹(shù)的定義和圖5-1的示例可以看出，樹(shù)具有下面兩個(gè)特點(diǎn)：樹(shù)的根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)；(2)樹(shù)中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。5.1樹(shù)和二叉樹(shù)的基本概念第5章樹(shù)和二叉樹(shù)2.相關(guān)術(shù)語(yǔ)(1)樹(shù)的結(jié)點(diǎn)(Node)指一個(gè)數(shù)據(jù)元素及指向其子樹(shù)的分支。(2)結(jié)點(diǎn)的度(Degree)結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。圖5-1中結(jié)點(diǎn)A的度為3，結(jié)點(diǎn)B的度為4，結(jié)點(diǎn)F的度為2，結(jié)點(diǎn)D的度為1，結(jié)點(diǎn)C、E、G、H、I、J、K的度為0。(3)樹(shù)的度樹(shù)中各結(jié)點(diǎn)度的最大值稱(chēng)為該樹(shù)的度。圖5-1中樹(shù)的度為4。(4)分支結(jié)點(diǎn)度大于0的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。圖5-1中的分支結(jié)點(diǎn)有A、B、D、F。(5)葉子結(jié)點(diǎn)(Leaf)度為0的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)，簡(jiǎn)稱(chēng)葉子。圖5-1中的葉子結(jié)點(diǎn)為C、E、G、H、I、J、K。(6)孩子結(jié)點(diǎn)(Child)某一結(jié)點(diǎn)的子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，簡(jiǎn)稱(chēng)孩子。圖5-1中結(jié)點(diǎn)A的孩子為B、C、D。5.1樹(shù)和二叉樹(shù)的基本概念第5章樹(shù)和二叉樹(shù)(7)雙親結(jié)點(diǎn)(Parent)一個(gè)結(jié)點(diǎn)稱(chēng)為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。圖5-1中結(jié)點(diǎn)B的雙親為A。(8)兄弟、堂兄弟具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱(chēng)為兄弟；雙親在同一層的結(jié)點(diǎn)互為堂兄弟。圖5-1中B、C、D為兄弟，E、I是堂兄弟。(9)祖先、子孫在樹(shù)中，從根到某個(gè)結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的祖先；一個(gè)結(jié)點(diǎn)的子樹(shù)中的任一結(jié)點(diǎn)為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。(10)結(jié)點(diǎn)的層數(shù)(Level)規(guī)定樹(shù)的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加1。圖5-1中A的層數(shù)為1，B、C、D的層數(shù)為2，E、F、G、H、I的層數(shù)為3，J、K的層數(shù)為4。(11)樹(shù)的深度(Depth)樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)。圖5-1中樹(shù)的深度為4。(12)有序樹(shù)和無(wú)序樹(shù)如果一棵樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，即如果交換了某結(jié)點(diǎn)各子樹(shù)的相對(duì)位置，則構(gòu)成不同的樹(shù)，稱(chēng)這棵樹(shù)為有序樹(shù)；反之，則稱(chēng)為無(wú)序樹(shù)。(13)森林(Forest)—棵或更多棵互不相交的樹(shù)的集合。5.1樹(shù)和二叉樹(shù)的基本概念第5章樹(shù)和二叉樹(shù)5.1.2二叉樹(shù)的定義及特殊二叉樹(shù)1．二叉樹(shù)的定義二叉樹(shù)T(BinaryTree)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，它滿(mǎn)足下面兩個(gè)條件：（1）當(dāng)n=0時(shí)，T為空二叉樹(shù)；（2）當(dāng)n>0時(shí)，它是由一個(gè)稱(chēng)為根的結(jié)點(diǎn)t及兩個(gè)互不相交的子集組成，其中每個(gè)子集又是一棵二叉樹(shù)，分別稱(chēng)為t的左子樹(shù)和右子樹(shù)。由上述二叉樹(shù)的定義可知，對(duì)于非空二叉樹(shù)有且僅有一個(gè)結(jié)點(diǎn)t沒(méi)有前驅(qū)，稱(chēng)為樹(shù)根；除t之外，二叉樹(shù)中的所有結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)、最多有兩個(gè)直接后繼。同時(shí)，在此定義中又用到了二叉樹(shù)的概念，所以二叉樹(shù)的定義是一個(gè)遞歸定義，它刻畫(huà)出了二叉樹(shù)的固有特性。5.1樹(shù)和二叉樹(shù)的基本概念第5章樹(shù)和二叉樹(shù)5.1.2二叉樹(shù)的定義及特殊二叉樹(shù)1．二叉樹(shù)的定義二叉樹(shù)T(BinaryTree)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，它滿(mǎn)足下面兩個(gè)條件：（1）當(dāng)n=0時(shí)，T為空二叉樹(shù)；（2）當(dāng)n>0時(shí)，它是由一個(gè)稱(chēng)為根的結(jié)點(diǎn)t及兩個(gè)互不相交的子集組成，其中每個(gè)子集又是一棵二叉樹(shù)，分別稱(chēng)為t的左子樹(shù)和右子樹(shù)。由上述二叉樹(shù)的定義可知，對(duì)于非空二叉樹(shù)有且僅有一個(gè)結(jié)點(diǎn)t沒(méi)有前驅(qū)，稱(chēng)為樹(shù)根；除t之外，二叉樹(shù)中的所有結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)、最多有兩個(gè)直接后繼。同時(shí)，在此定義中又用到了二叉樹(shù)的概念，所以二叉樹(shù)的定義是一個(gè)遞歸定義，它刻畫(huà)出了二叉樹(shù)的固有特性。5.1樹(shù)和二叉樹(shù)的基本概念第5章樹(shù)和二叉樹(shù)5.1樹(shù)和二叉樹(shù)的基本概念第5章樹(shù)和二叉樹(shù)2．特殊二叉樹(shù)(1)滿(mǎn)二叉樹(shù)(FullBinaryTree)若一棵二叉樹(shù)的最下面一層結(jié)點(diǎn)度數(shù)全為0，其它所有結(jié)點(diǎn)的度數(shù)均為2，則稱(chēng)這種二叉樹(shù)為滿(mǎn)二叉樹(shù)。如圖5-7(a)所示。(2)完全二叉樹(shù)(CompleteBinaryTree)

若一棵二叉樹(shù)至多只有最下面的兩層結(jié)點(diǎn)的度數(shù)小于2，并且最下面一層結(jié)點(diǎn)都集中在該層的最左邊，則稱(chēng)這種二叉樹(shù)為完全二叉樹(shù)。如圖5-7(b)所示，而圖5-7（c）不是完全二叉樹(shù)。5.1樹(shù)和二叉樹(shù)的基本概念第5章樹(shù)和二叉樹(shù)5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)5.2.1二叉樹(shù)的性質(zhì)性質(zhì)1在非空二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。證明此性質(zhì)用數(shù)學(xué)歸納法來(lái)證明。當(dāng)i=1時(shí)，第一層上只有—個(gè)根結(jié)點(diǎn)，結(jié)論成立；假設(shè)對(duì)所有的j,（1≤j<i），結(jié)論成立，即第j層上有2j-1個(gè)結(jié)點(diǎn)。則有，對(duì)于j=i-1時(shí)，由歸納假設(shè)可知第i-1層上最多有2i-2個(gè)結(jié)點(diǎn)，又由于二叉樹(shù)的每個(gè)結(jié)點(diǎn)的度最多為2，所以在第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層最大結(jié)點(diǎn)數(shù)的2倍，即有2×2i-2=2i-1，故對(duì)于j=i時(shí)結(jié)論成立，得證。5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)性質(zhì)2深度為k的二叉樹(shù)最多有2k-1個(gè)結(jié)點(diǎn)(k≥1)。證明由性質(zhì)1可知，深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為：5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)性質(zhì)3對(duì)任何一棵二叉樹(shù)T，如果終端結(jié)點(diǎn)(葉子結(jié)點(diǎn))的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，那么n0=n2+1。證明設(shè)二叉樹(shù)T的總結(jié)點(diǎn)數(shù)為n，度為1的結(jié)點(diǎn)數(shù)為n1，由于二叉樹(shù)中結(jié)點(diǎn)的度都小于等于2，所以二叉樹(shù)的結(jié)點(diǎn)總數(shù)n為：5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)性質(zhì)4一棵非空二叉樹(shù)空子樹(shù)的數(shù)目等于其結(jié)點(diǎn)數(shù)目加1。證明設(shè)二叉樹(shù)T有n個(gè)結(jié)點(diǎn)，將其所有空子樹(shù)換成葉結(jié)點(diǎn)，把新的二叉樹(shù)記為T(mén)'，即T'中的葉結(jié)點(diǎn)數(shù)恰為T(mén)中的空子樹(shù)的數(shù)目，設(shè)有n0個(gè)。所有原來(lái)樹(shù)T的結(jié)點(diǎn)現(xiàn)在是樹(shù)T'的分支結(jié)點(diǎn)，即T'中分支結(jié)點(diǎn)有n個(gè)，又由于樹(shù)T'中的所有分支結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，即在T'中度為2的結(jié)點(diǎn)數(shù)n2=n，由性質(zhì)3可以得出，n0=n+1，得證。5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)性質(zhì)5具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為證明設(shè)該二叉樹(shù)的深度為K，則由性質(zhì)2和完全二叉樹(shù)的定義可知：則有，因?yàn)閗為數(shù)，所以有。5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)性質(zhì)6如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層數(shù)編號(hào)(從第1層到第層，每層從左到右編號(hào))，那么對(duì)任意結(jié)點(diǎn)i(1≤i≤n)有：①如果i＝1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親結(jié)點(diǎn)；如果i＞1，則其雙親結(jié)點(diǎn)的編號(hào)是；②如果2i＞n，則結(jié)點(diǎn)i無(wú)左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn))；否則其左孩子結(jié)點(diǎn)的編號(hào)是2i；③如果2i+1＞n，則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子結(jié)點(diǎn)的編號(hào)是2i+1。。5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)5.2.2二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1.二叉樹(shù)的順序存儲(chǔ)表示(1)完全（滿(mǎn)）二叉樹(shù)的順序存儲(chǔ)由二叉樹(shù)的性質(zhì)6可知，完全二叉樹(shù)按層編號(hào)后，結(jié)點(diǎn)編號(hào)間有一定的關(guān)系。在順序存儲(chǔ)中，利用此性質(zhì)，將完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為i的分量中，圖5-7（b）所示完全二叉樹(shù)的順序存儲(chǔ)如圖5-8所示，這樣第0個(gè)單元不存儲(chǔ)數(shù)據(jù)。5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)(2)一般二叉樹(shù)的存儲(chǔ)對(duì)于一般二叉樹(shù)可以參照完全二叉樹(shù)的存儲(chǔ)來(lái)實(shí)現(xiàn)。如圖5-9（a）所示二叉樹(shù)的順序存儲(chǔ)如圖5-9（b）所示，圖5-9（c）指明了每個(gè)結(jié)點(diǎn)之間的相互關(guān)系。5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)2.二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示鏈?zhǔn)酱鎯?chǔ)就是用鏈表來(lái)存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)，通過(guò)指針?lè)从辰Y(jié)點(diǎn)之間的邏輯關(guān)系。二叉樹(shù)常用的鏈?zhǔn)酱鎯?chǔ)形式有二叉鏈表、三叉鏈表及線(xiàn)索鏈表等。對(duì)于線(xiàn)索鏈表在后面再進(jìn)行說(shuō)明。(1)二叉鏈表二叉樹(shù)中的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，因此可以用這樣的方式存儲(chǔ)二叉樹(shù)：在每個(gè)結(jié)點(diǎn)中包含三個(gè)域，即一個(gè)數(shù)據(jù)元素域及兩個(gè)分別指向左、右子樹(shù)根結(jié)點(diǎn)的指針域組成。這種結(jié)點(diǎn)結(jié)構(gòu)稱(chēng)之為二叉鏈表結(jié)構(gòu)。結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如下：5.2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)第5章樹(shù)和二叉樹(shù)(2)三叉鏈表為了方便地查找雙親，在二叉鏈表的結(jié)點(diǎn)中再增加一個(gè)指向雙親的指針域，這種結(jié)構(gòu)稱(chēng)做為三叉鏈表存儲(chǔ)結(jié)構(gòu)。結(jié)點(diǎn)結(jié)構(gòu)如下：其中，data、lchild、rchild三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。同樣，在三叉鏈表中也增加一個(gè)指向根結(jié)點(diǎn)的指針BT。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)5.3.1遍歷二叉樹(shù)在二叉樹(shù)的一些應(yīng)用中，常常要求在樹(shù)中查找具有某種特征的結(jié)點(diǎn)；或者對(duì)樹(shù)中全部結(jié)點(diǎn)逐一進(jìn)行某種處理，比如打印出每個(gè)結(jié)點(diǎn)的內(nèi)容、判斷二叉樹(shù)是否連通等等。這都是與二叉樹(shù)的遍歷有關(guān)的問(wèn)題。遍歷二叉樹(shù)(TraversingBinaryTree)是指按照某條搜索路徑訪問(wèn)二叉樹(shù)中的每個(gè)結(jié)點(diǎn),使得每一個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。在此的所謂“訪問(wèn)”可以是對(duì)結(jié)點(diǎn)做各種處理，如輸出結(jié)點(diǎn)數(shù)據(jù)域值、比較、更新、查看元素內(nèi)容等等。對(duì)線(xiàn)性表的遍歷，可以按表的順序很簡(jiǎn)單地實(shí)現(xiàn)。但由于二叉樹(shù)是一種非線(xiàn)性結(jié)構(gòu)，因此，對(duì)二叉樹(shù)的遍歷就不能那樣簡(jiǎn)單地實(shí)現(xiàn)。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)1.二叉樹(shù)遍歷的遞歸算法(1)．先序遍歷（PreorderTraversal）先序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則①訪問(wèn)根結(jié)點(diǎn)；②先序遍歷根的左子樹(shù)；③先序遍歷根的右子樹(shù)。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)(2)．中序遍歷（LDR）中序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則①中序遍歷根的左子樹(shù)；②訪問(wèn)根結(jié)點(diǎn)；③中序遍歷根的右子樹(shù)。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)(3)．后序遍歷（LRD）后序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則（1）后序遍歷根的左子樹(shù)；（2）后序遍歷根的右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)2.二叉樹(shù)遍歷的非遞歸算法前面給出的二叉樹(shù)先序、中序和后序三種遍歷算法都是遞歸算法。遞歸算法相對(duì)簡(jiǎn)潔直觀，容易寫(xiě)出，但可讀性一般不好，執(zhí)行效率也不高。因此，就存在如何把一個(gè)遞歸算法轉(zhuǎn)化為非遞歸算法的問(wèn)題。對(duì)于圖5-16（a）所示的二叉樹(shù)，其先序、中序和后序遍歷都是從根結(jié)點(diǎn)A開(kāi)始的，且在遍歷過(guò)程中經(jīng)過(guò)結(jié)點(diǎn)的路線(xiàn)也是一樣的，只是訪問(wèn)的時(shí)機(jī)不同而已。圖(b)是從根結(jié)點(diǎn)左外側(cè)開(kāi)始，到根結(jié)點(diǎn)右外側(cè)結(jié)束的路線(xiàn)，即是圖(a)的遍歷路線(xiàn)。沿著該路線(xiàn)按標(biāo)記的結(jié)點(diǎn)讀得的序列為先序序列ABDFCE，按標(biāo)記讀得的序列為中序序列BFDAEC，按標(biāo)記讀得的序列為后序序列FDBECA。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)3．二叉樹(shù)的確定性前面給出了二叉樹(shù)的先序、中序和后序遍歷的算法，對(duì)于給定的二叉樹(shù)調(diào)用相應(yīng)的算法也就得到了相應(yīng)的先序、中序和后序遍歷序列。很明顯，對(duì)于不同形態(tài)的二叉樹(shù)，先序遍歷序列可能相同；中序遍歷序列可能相同；后序遍歷序列也可能相同。但是，如果給定某棵二叉樹(shù)的兩種遍歷序列，是否可以唯一的確定二叉樹(shù)呢？實(shí)際上，有如下的定理：定理任何n（n≥0）個(gè)不同結(jié)點(diǎn)的二叉樹(shù)，都可由它的中序序列和先序序列唯一地確定。這個(gè)定理也是二叉樹(shù)的確定性。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)5.3.2線(xiàn)索二叉樹(shù)常用的不用棧的二叉樹(shù)遍歷的非遞歸方法有以下幾種：（1）對(duì)二叉樹(shù)采用三叉鏈表存放，這樣在遍歷深入到不能再深人時(shí)，可沿著走過(guò)的路徑回退到任何一棵子樹(shù)的根結(jié)點(diǎn)，并再向另一方向走。當(dāng)然，這一方法在每個(gè)結(jié)點(diǎn)中增加了一個(gè)雙親域，故其存儲(chǔ)開(kāi)銷(xiāo)相應(yīng)的有所增加。（2）在線(xiàn)索二叉樹(shù)上的遍歷，即利用二叉樹(shù)中葉子結(jié)點(diǎn)和度為1結(jié)點(diǎn)的空指針域，來(lái)存放線(xiàn)索，然后在這種具有線(xiàn)索的二叉樹(shù)上遍歷，這種遍歷方法既不需要棧，也不需要遞歸。下面給出有關(guān)線(xiàn)索二叉樹(shù)的詳細(xì)內(nèi)容。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)1．線(xiàn)索二叉樹(shù)的定義在線(xiàn)性結(jié)構(gòu)中，結(jié)點(diǎn)有唯一的直接前驅(qū)和直接后繼。而二叉樹(shù)是非線(xiàn)性結(jié)構(gòu)，它的后繼并不唯一。但在遍歷二叉樹(shù)時(shí)，按照一定的規(guī)則將二叉樹(shù)的結(jié)點(diǎn)排列成一個(gè)線(xiàn)性序列，從而得到了二叉樹(shù)的先序序列、中序序列和后序序列。因此遍歷操作實(shí)際上是將二叉樹(shù)進(jìn)行線(xiàn)性化的操作，也就是把非線(xiàn)性的二叉樹(shù)線(xiàn)性化成了一個(gè)邏輯上除第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)和最后一個(gè)結(jié)點(diǎn)無(wú)后繼外，其它所有結(jié)點(diǎn)都有一個(gè)前驅(qū)和一個(gè)后繼的線(xiàn)性序列。但是在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，只有左右孩子的信息而無(wú)前驅(qū)和后繼的信息，從而只能在對(duì)二叉樹(shù)遍歷的動(dòng)態(tài)過(guò)程中得到這些信息。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)2．線(xiàn)索二叉樹(shù)的結(jié)構(gòu)為了避免混淆，一般是在結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域來(lái)標(biāo)識(shí)二叉鏈表的指針域是指向兒子的指針還是指向某遍歷序列的前驅(qū)或后繼的指針。這時(shí)結(jié)點(diǎn)結(jié)構(gòu)定義如下。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)3．二叉樹(shù)的線(xiàn)索化及遍歷線(xiàn)索二叉樹(shù)給出一棵用二叉鏈表存儲(chǔ)的二叉樹(shù)，要將它按中序線(xiàn)索化，或者說(shuō)對(duì)二叉樹(shù)中序線(xiàn)索化，實(shí)質(zhì)上就是按中序遍歷此二叉樹(shù)，在遍歷的過(guò)程中用線(xiàn)索代替空的指針，即檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，則改為指向其在中序遍歷序列中的直接前驅(qū)結(jié)點(diǎn)或直接后繼結(jié)點(diǎn)。另外，在對(duì)一棵二叉樹(shù)加線(xiàn)索時(shí)，模仿線(xiàn)性鏈表的存儲(chǔ)結(jié)構(gòu)，在二叉樹(shù)的線(xiàn)索鏈表上也添加一個(gè)頭結(jié)點(diǎn)，并且建立頭結(jié)點(diǎn)與二叉樹(shù)的根結(jié)點(diǎn)的指向關(guān)系，即令頭結(jié)點(diǎn)lchild域的指針指向二叉樹(shù)的根結(jié)點(diǎn)；對(duì)二叉樹(shù)線(xiàn)索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線(xiàn)索，即頭結(jié)點(diǎn)的rchild域的指針指向中序遍歷時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)。同時(shí)，令二叉樹(shù)中序序列中的第一個(gè)結(jié)點(diǎn)的lchild域指針和最后一個(gè)結(jié)點(diǎn)的rchild域指針均指向頭結(jié)點(diǎn)；就像為二叉樹(shù)建立了一個(gè)雙向線(xiàn)索鏈表。5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)3．二叉樹(shù)的線(xiàn)索化及遍歷線(xiàn)索二叉樹(shù)5.3二叉樹(shù)的遍歷及線(xiàn)索化第5章樹(shù)和二叉樹(shù)4．遍歷算法的應(yīng)用通過(guò)二叉樹(shù)的遍歷，可以得到一個(gè)二叉樹(shù)結(jié)點(diǎn)的線(xiàn)性序列，由于二叉樹(shù)的結(jié)點(diǎn)之間的邏輯關(guān)系是非線(xiàn)性的，在訪問(wèn)結(jié)點(diǎn)時(shí)就要進(jìn)行多種判斷，利用遍歷算法可以解決許多有關(guān)二叉樹(shù)上的操作要求。在高級(jí)語(yǔ)言的編譯程序中，經(jīng)常需要處理和計(jì)算一些表達(dá)式，例如對(duì)算術(shù)表達(dá)式或邏輯表達(dá)式進(jìn)行求值運(yùn)算。而對(duì)于任意一個(gè)表達(dá)式中的二元運(yùn)算符處理需要考慮運(yùn)算符的優(yōu)先級(jí)，而且大部分運(yùn)算符（二元運(yùn)算符）都有這樣的特點(diǎn)：一個(gè)運(yùn)算符對(duì)應(yīng)兩個(gè)操作數(shù)。故我們可以將二元運(yùn)算表示成圖5-19（a）所示的形式：5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)5.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，樹(shù)的存儲(chǔ)結(jié)構(gòu)有多種形式，既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但無(wú)論采用何種存儲(chǔ)方式，都要求存儲(chǔ)結(jié)構(gòu)不但能存儲(chǔ)各結(jié)點(diǎn)本身的數(shù)據(jù)信息，還要能唯一地反映樹(shù)中各結(jié)點(diǎn)之間的邏輯關(guān)系。

1．順序存儲(chǔ)結(jié)構(gòu)(1)．父親表示法(2)．左孩子結(jié)點(diǎn)/右兄弟表示法（孩子兄弟表示）5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)2．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上述兩種實(shí)現(xiàn)樹(shù)的方法使用數(shù)組存儲(chǔ)結(jié)點(diǎn)。我們接著嘗試將鏈表表示法擴(kuò)展到樹(shù)，即樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(1)．孩子鏈表表示法是對(duì)樹(shù)的每個(gè)結(jié)點(diǎn)建立一個(gè)兒子結(jié)點(diǎn)鏈表，由于各結(jié)點(diǎn)的兒子結(jié)點(diǎn)數(shù)目多少不一，所以常用單鏈表來(lái)實(shí)現(xiàn)兒子結(jié)點(diǎn)鏈表。5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)(2)．孩子兄弟表示法又稱(chēng)為二叉樹(shù)表示法或二叉鏈表表示法，即以二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)。具體含義是這樣的：在樹(shù)中每個(gè)結(jié)點(diǎn)除其數(shù)據(jù)域外，再增加兩個(gè)指針域，分別是指向該結(jié)點(diǎn)的第—個(gè)孩子結(jié)點(diǎn)的指針和下一個(gè)兄弟結(jié)點(diǎn)的指針。在這種表示法中，既用到了兒子指針又用到了兄弟指針，因此稱(chēng)這種表示法為兒子兄弟表示法。圖5-1的孩子兄弟表示法如圖5-25所示。5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)5.4.2樹(shù)、森林雨二叉樹(shù)的裝換從前面幾節(jié)的討論可知，相對(duì)于二叉樹(shù)來(lái)說(shuō)，樹(shù)的存儲(chǔ)結(jié)構(gòu)要復(fù)雜得多，主要是由于樹(shù)中每個(gè)結(jié)點(diǎn)的度可能相差很多，且沒(méi)有規(guī)律。更重要的是一般樹(shù)的基本運(yùn)算實(shí)現(xiàn)比較復(fù)雜，而對(duì)于二叉樹(shù)就有相應(yīng)的一系列實(shí)現(xiàn)簡(jiǎn)單而成熟的算法。同時(shí)由上一節(jié)可知，任何樹(shù)都可以采用孩子兄弟鏈表作為存儲(chǔ)結(jié)構(gòu)，那么樹(shù)或森林與二叉樹(shù)之間是否存著某種轉(zhuǎn)換關(guān)系呢？圖5-26直觀地給出了樹(shù)與二叉樹(shù)之間的對(duì)應(yīng)關(guān)系。5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)1．森林轉(zhuǎn)換為二叉樹(shù)設(shè)T＝{T1，T2，???，Tn}是一棵森林，那么T可以按如下方法轉(zhuǎn)換成一棵二叉樹(shù)BT。①如T為空，那么BT為空二叉樹(shù)；②如果T非空，那么BT的根結(jié)點(diǎn)為森林的第一棵樹(shù)T1的根，BT的左子樹(shù)為T(mén)1去掉根結(jié)點(diǎn)后的子樹(shù)組成的森林按此方法轉(zhuǎn)換成的二叉樹(shù)，BT的右子樹(shù)為森林{T2，???，Tn}按此方法轉(zhuǎn)換成的二叉樹(shù)?？梢宰C明，森林通過(guò)這種方法轉(zhuǎn)換后所得的二叉樹(shù)是唯一的。5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)2．二叉樹(shù)轉(zhuǎn)換成森林設(shè)BT＝{root，lbt，rbt}是一棵二叉樹(shù)，其中，root為二叉樹(shù)的根結(jié)點(diǎn)，lbt、rbt分別是root的左子樹(shù)和右子樹(shù)。那么BT可以按如下方法轉(zhuǎn)換成森林T={T1，T2，???，Tn}。①BT為空，那么T為空樹(shù)；②BT非空，那么森林T中第一棵樹(shù)T1的根為二叉樹(shù)BT的根結(jié)點(diǎn)root，T中第—棵樹(shù)T1的根的子樹(shù)森林為BT的左子樹(shù)lbt按此方法轉(zhuǎn)換成的森林，森林{T2，???，Tn}為BT的右子樹(shù)rbt按此方法轉(zhuǎn)換成的森林。5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)5.4.3樹(shù)及森林的遍歷與二叉樹(shù)類(lèi)似，遍歷是樹(shù)和森林的一種基本運(yùn)算。對(duì)于樹(shù)來(lái)說(shuō)仍有三種主要的遍歷方法，即先序(根)遍歷、后序遍歷和層次遍歷；而對(duì)于森林來(lái)說(shuō)，一般有前序遍歷和中序遍歷兩種方法。1．樹(shù)的遍歷①．先序遍歷若樹(shù)非空，則：(ⅰ)訪問(wèn)根結(jié)點(diǎn)；(ⅱ)按照從左到右依次先根序遍歷根的每棵子樹(shù)。5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)②．后序遍歷若樹(shù)非空，則：(ⅰ)先按照從左到右依次后根遍歷根的每棵子樹(shù)；(ⅱ)訪問(wèn)根結(jié)點(diǎn)。③．層次遍歷若樹(shù)非空，則先訪問(wèn)根結(jié)點(diǎn)，再按從左到右的順序訪問(wèn)第二層上的結(jié)點(diǎn)，依次按層訪問(wèn)，直到樹(shù)中的所有結(jié)點(diǎn)都被訪問(wèn)完為止。5.4樹(shù)和森林第5章樹(shù)和二叉樹(shù)2.森林的遍歷①．先序遍歷若森林非空，則(ⅰ)訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；(ⅱ)先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林；(ⅲ)先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。②．中序遍歷若森林非空，則(ⅰ)中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；(ⅱ)訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；(ⅲ)中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。5.5最優(yōu)二叉樹(shù)及哈夫曼編碼第5章樹(shù)和二叉樹(shù)在很多問(wèn)題的處理過(guò)程中，需要進(jìn)行大量的條件判斷，這些判斷結(jié)構(gòu)的設(shè)計(jì)直接影響著程序的執(zhí)行效率。例如，將百分制轉(zhuǎn)換成五級(jí)分制的程序流程圖如圖5-30（a）：5.5最優(yōu)二叉樹(shù)及哈夫曼編碼第5章樹(shù)和二叉樹(shù)5.5.1哈夫曼樹(shù)的基本概念及其構(gòu)造1．有關(guān)術(shù)語(yǔ)及哈夫曼樹(shù)的定義首先給出樹(shù)中的一些與哈夫曼樹(shù)有關(guān)的術(shù)語(yǔ)及哈夫曼樹(shù)的定義。(1)路徑叢樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支稱(chēng)為這兩個(gè)結(jié)點(diǎn)間的路徑。(2)路徑長(zhǎng)度路徑上的分支數(shù)目稱(chēng)為路徑長(zhǎng)度。(3)樹(shù)的路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度是指從樹(shù)根到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。完全二叉樹(shù)是路徑長(zhǎng)度最短的二叉樹(shù)。5.5最優(yōu)二叉樹(shù)及哈夫曼編碼第5章樹(shù)和二叉樹(shù)(4)樹(shù)結(jié)點(diǎn)的權(quán)將樹(shù)中的結(jié)點(diǎn)賦上一個(gè)有某種意義的實(shí)數(shù)，稱(chēng)此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)。如百分制轉(zhuǎn)換成五級(jí)分制中的學(xué)生比例是各等級(jí)的權(quán)值。(5)結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為此結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上的權(quán)的乘積。(6)樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。(7)哈夫曼樹(shù)哈夫曼樹(shù)（Huffman）又稱(chēng)最優(yōu)二叉樹(shù)。它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)。5.5最優(yōu)二叉樹(shù)及哈夫曼編碼第5章樹(shù)和二叉樹(shù)2．構(gòu)造哈夫曼樹(shù)那么，如果給定一組權(quán)值，如何才能構(gòu)造出一棵哈夫曼樹(shù)呢？哈夫曼在1952年提出了一種能很好地利用貪心法解決這個(gè)問(wèn)題的算法，俗稱(chēng)哈夫曼算法，其基本思路是：(1)對(duì)于給定的n個(gè)權(quán)值wl，w2，…，wn，構(gòu)成n棵二叉樹(shù)的集合F＝{T1,T2,…、Tn}，其中每棵二叉樹(shù)只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左、右子樹(shù)均為空；(2)在{T1，T2，…，Tn}中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，并置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；(3)在T中刪除這兩棵二叉樹(shù)，同時(shí)將新得到的二叉樹(shù)加入T中；(4)重復(fù)(2)和(3)，直到T只含一棵二叉樹(shù)為止。這棵二叉樹(shù)便是哈夫曼樹(shù)。5.5最優(yōu)二叉樹(shù)及哈夫曼編碼第5章樹(shù)和二叉樹(shù)5.5.2哈夫曼樹(shù)的應(yīng)用——哈夫曼編碼在利用計(jì)算機(jī)進(jìn)行文字信息通信時(shí)，信息是以二進(jìn)制的0、1序列進(jìn)行傳送的。發(fā)送的一方需要將傳送的文字信息轉(zhuǎn)換成二進(jìn)制的0、1序列即編碼(Encode)，而接收的一方又需要將接收到的0、1序列轉(zhuǎn)換為對(duì)應(yīng)的文字信息即譯碼(Decode)。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則：1．發(fā)送的二進(jìn)制編碼盡可能地短。下面我們介紹兩種編碼的方式。（1）等長(zhǎng)編碼假設(shè)所有代碼都等長(zhǎng)，則表示n個(gè)不同的代碼需要位，稱(chēng)為固定長(zhǎng)度編碼方法(afixed—1engthcodingscheme)。ASCII碼就是一種固定長(zhǎng)度編碼，它用即7位提供了128個(gè)不同的代碼來(lái)表示ASCII碼表中的128種字符。如果每個(gè)字符的使用頻率都相等，固定長(zhǎng)度編碼是空間效率最高的方法。但是，你可能注意到，并非每個(gè)字符的使用頻率都是一樣的。5.5最優(yōu)二叉樹(shù)及哈夫曼編碼第5章樹(shù)和二叉樹(shù)（2）不等長(zhǎng)編碼表5-2給出了在典型的含有1000個(gè)字母的英語(yǔ)文獻(xiàn)字母表中各個(gè)字母出現(xiàn)的相對(duì)頻率。通過(guò)這個(gè)表，可以看出字母“E”的出現(xiàn)頻率為“Z”的60倍。在等長(zhǎng)編碼中，單詞“deed”和“fuzz”的代碼長(zhǎng)度相同，而如果采用不等長(zhǎng)編碼，使