數(shù)據(jù)結(jié)構(gòu)（從概念到算法）課件

第5章樹與二叉樹01020304目錄CONTENTS05樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)樹、森林與二叉樹的轉(zhuǎn)換06哈夫曼樹07應(yīng)用實例08本章小結(jié)01PART樹的邏輯結(jié)構(gòu)5.1.1樹的定義與基本術(shù)語樹（Tree）是由n（n≥0）個結(jié)點構(gòu)成的有限集合，可表示為T。當(dāng)n=0時，T為空樹；而任一非空樹必滿足：（1）有唯一的特定結(jié)點，其稱為樹

T

的根（Root）；（2）當(dāng)n>1時，T中除根之外的n-1個結(jié)點分為m（m>0）個互不相交的有限集T1,T2,…,Tm，其中每個集合

Ti

（1≤i≤m）又是一棵樹，且稱為根的子樹（SubTree）。如右圖所示，Ta為只有根結(jié)點的樹，Tb為含16個結(jié)點的樹，其根結(jié)點為A，Tc不符合樹的定義，它是一種非樹結(jié)構(gòu)。樹的邏輯結(jié)構(gòu)5.1.1樹的定義與基本術(shù)語為了進一步描述樹結(jié)構(gòu)的特征和方便后續(xù)應(yīng)用，下面引入幾個典型的術(shù)語。結(jié)點的度（DegreeofNode）：某個結(jié)點所含子樹的棵數(shù)稱為該結(jié)點的度。樹的度（Degree

of

Tree）：樹中各結(jié)點度的最大值稱為該樹的度。葉子（Leaf）：指度為0的結(jié)點，也稱為終端結(jié)點（Terminal

Node）。分支結(jié)點（Branch

Node）：指度不為

0

的結(jié)點，也稱為非終端結(jié)點。孩子結(jié)點（ChildrenNode）：稱某結(jié)點

P

子樹的根結(jié)點

C

為其孩子結(jié)點；相應(yīng)地，該結(jié)點

P稱為孩子結(jié)點

C

的雙親結(jié)點（ParentNode）；具有相同雙親的結(jié)點之間互稱為兄弟結(jié)點（SiblingsNode）。結(jié)點的祖先（Ancestors）結(jié)點：指從根結(jié)點到該結(jié)點所經(jīng)分支路徑上的所有結(jié)點。結(jié)點的子孫（Descendants）結(jié)點：指以該結(jié)點為根的子樹中的所有結(jié)點。結(jié)點的層（Level）：根結(jié)點為第一層；任意非根結(jié)點的層數(shù)比其雙親結(jié)點的層數(shù)多一。樹的邏輯結(jié)構(gòu)5.1.1樹的定義與基本術(shù)語樹的深度（Depth）：指樹中所有結(jié)點的最大層數(shù)。在樹中，其雙親結(jié)點處于同一層的結(jié)點互稱為堂兄弟結(jié)點。如果樹中結(jié)點的各子樹之間具有次序性，稱這種樹為有序樹，否則就為無序樹。對于有序樹，交換某結(jié)點子樹間的次序之后則變成另一棵不同的有序樹。森林（Forest）：指

m（m≥0）棵互不相交樹的集合。下表給出了線性結(jié)構(gòu)與樹結(jié)構(gòu)的區(qū)別。線性結(jié)構(gòu)樹結(jié)構(gòu)第一個數(shù)據(jù)元素（無前驅(qū)）根結(jié)點（無雙親）最后一個數(shù)據(jù)元素（無后繼）多個葉子結(jié)點（無孩子）其他數(shù)據(jù)元素（一個直接前驅(qū)、一個直接后繼）其他結(jié)點（一個雙親、多個孩子）樹的邏輯結(jié)構(gòu)5.1.2樹的抽象數(shù)據(jù)類型定義樹中表示的數(shù)據(jù)對象是某種具有相同特性數(shù)據(jù)元素的集合。樹的抽象數(shù)據(jù)類型定義如下。02PART樹的存儲結(jié)構(gòu)5.2.1雙親表示法樹的雙親表示法利用數(shù)組存儲每個結(jié)點及其雙親位置信息，即采用結(jié)構(gòu)體數(shù)組實現(xiàn)，該表示法也叫作數(shù)組表示法。樹的結(jié)點對應(yīng)的結(jié)構(gòu)體包含數(shù)據(jù)元素data與雙親結(jié)點位置parent兩個成員，如下圖所示。下圖給出了一棵樹及其雙親表示法示意圖，其根結(jié)點對應(yīng)的下標(biāo)r=0及結(jié)點總數(shù)n=7為兩個總體信息。樹的存儲結(jié)構(gòu)5.2.2孩子表示法為方便訪問當(dāng)前結(jié)點的孩子結(jié)點，此時需要直接存儲其孩子結(jié)點的位置信息。基于鏈?zhǔn)酱?/p>

儲結(jié)構(gòu)，可以在結(jié)點結(jié)構(gòu)中設(shè)置指針，直接指向其孩子結(jié)點。我們可采用以下兩種方式實現(xiàn)這種表示。第一種方式是采用多重鏈表，即在每個結(jié)點中設(shè)置若干指針域，分別指向其孩子結(jié)點，結(jié)點指針域的個數(shù)等于該結(jié)點的度。由于樹中不同結(jié)點的孩子結(jié)點個數(shù)可能不同，因此結(jié)點的指針域個數(shù)也可能不同，結(jié)點大小不固定。多重鏈表結(jié)點結(jié)構(gòu)如下圖所示。在多重鏈表表示法中，結(jié)點大小不固定。如果樹中每個結(jié)點的指針域個數(shù)都按樹的度統(tǒng)一設(shè)置，則所有結(jié)點大小一致，此時多重鏈表中可能存在許多空指針域。樹的存儲結(jié)構(gòu)5.2.2孩子表示法下圖給出了一棵樹及其多重鏈表表示法示意圖，指針root指向樹的根結(jié)點A。樹的存儲結(jié)構(gòu)5.2.2孩子表示法第二種方式是采用單鏈表，即每個結(jié)點的所有孩子結(jié)點排列而成的一個單鏈表，稱為該結(jié)點的孩子鏈表；n

個結(jié)點的樹共有

n

個孩子鏈表（其中葉子結(jié)點的孩子鏈表為空鏈表），我們可以把對應(yīng)的n個孩子鏈表頭指針組織成線性表，并用順序結(jié)構(gòu)實現(xiàn)而構(gòu)成表頭數(shù)組，這種表示法稱為樹的孩子鏈表表示法。在該表示法中，有兩類結(jié)點：一類是表頭結(jié)點，由結(jié)點值/數(shù)據(jù)元素data

與對應(yīng)的孩子鏈表頭指針

firstchild

構(gòu)成（見圖（a））；另一類是孩子結(jié)點，由孩子位置

child

與指向下一個孩子結(jié)點的指針

next

構(gòu)成（見圖（b））。樹的存儲結(jié)構(gòu)5.2.2孩子表示法下圖給出了一棵樹及其孩子鏈表表示法示意圖，其根結(jié)點對應(yīng)的下標(biāo)r=0及結(jié)點總數(shù)n=11為對應(yīng)的兩個總體信息。樹的存儲結(jié)構(gòu)5.2.2孩子表示法在樹的孩子鏈表表示法中，易于訪問當(dāng)前結(jié)點的孩子結(jié)點，但不便于訪問當(dāng)前結(jié)點的雙親

結(jié)點，這與雙親表示法相反。因此，我們可以將這兩種表示法相結(jié)合，即在孩子鏈表表示法的基礎(chǔ)上，將其表頭結(jié)點增加一個雙親位置域，形成一種帶雙親的孩子鏈表表示法，其表頭結(jié)點結(jié)構(gòu)如下圖所示。樹的存儲結(jié)構(gòu)5.2.3孩子兄弟表示法樹的孩子兄弟表示法又稱為二叉鏈表表示法，即樹的鏈表結(jié)點結(jié)構(gòu)中，除了結(jié)點數(shù)據(jù)域data之外，還包含兩個指針域：指向該結(jié)點的第一個孩子結(jié)點（左孩子）的指針firstchild與下一個兄弟結(jié)點（右兄弟）的指針nextsibling。樹的孩子兄弟表示法結(jié)點結(jié)構(gòu)如下圖所示。樹的存儲結(jié)構(gòu)5.2.3孩子兄弟表示法對于下圖（a）的樹，其孩子兄弟表示法示意圖如圖（b）或圖（c）所示。孩子兄弟表示法易于實現(xiàn)樹的主要操作，例如，訪問當(dāng)前結(jié)點C的全部孩子：先通過C的firstchild指針訪問到其第一個孩子結(jié)點D，然后從D開始，不斷沿著結(jié)點的nextsibling指針可依次訪問結(jié)點E與F。03PART二叉樹的邏輯結(jié)構(gòu)5.3.1二叉樹的定義二叉樹（BinaryTree）是由

n（n≥0）個結(jié)點構(gòu)成的有限集。它或者為空二叉樹（n=0），或者由一個根結(jié)點以及兩棵互不相交的、分別被稱為根的左子樹與右子樹的二叉樹組成。二叉樹具有如下特征。（1）每個結(jié)點至多有兩棵子樹，因此在二叉樹中不存在度大于2的結(jié)點。（2）二叉樹的子樹有左、右之分，且其次序不能任意顛倒。根據(jù)二叉樹的上述特點，二叉樹可分為5種形態(tài)：空二叉樹、僅有根結(jié)點的二叉樹、右子樹為空的二叉樹（如圖中結(jié)點C的右子樹）、左子樹為空的二叉樹（如結(jié)點A

的右子樹）、根的左右子樹均非空的二叉樹（如結(jié)點A

的左子樹）。二叉樹的邏輯結(jié)構(gòu)5.3.2二叉樹的性質(zhì)性質(zhì)

5.1

在二叉樹的第

i

層上至多有

2i-1

個結(jié)點（i≥1）

。性質(zhì)5.2在深度為k的二叉樹中，最多有2k-1個結(jié)點。性質(zhì)5.3在一棵非空二叉樹中，若其葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有n0=n2+1。滿二叉樹（Full

BinaryTree）：對于深度為

k

的二叉樹，如果其結(jié)點數(shù)為

2k-1，即達到最大值，則稱其為滿二叉樹。下圖分別為深度從1到4的4棵滿二叉樹。二叉樹的邏輯結(jié)構(gòu)5.3.2二叉樹的性質(zhì)完全二叉樹（Complete

Binary

Tree）：一棵深度為

k

有

n

個結(jié)點的二叉樹，對其全部結(jié)點從根開始，按層序從上至下、從左至右進行連續(xù)編號，如果編號為i（1≤i≤n）的結(jié)點與同深度的滿二叉樹中編號為i（1≤i≤n）的結(jié)點在二叉樹中的位置完全相同，則稱這棵二叉樹為完全二叉樹。下圖為不同深度的完全二叉樹。二叉樹的邏輯結(jié)構(gòu)5.3.2二叉樹的性質(zhì)完全二叉樹的特點是：①葉子結(jié)點只可能出現(xiàn)在最下兩層，如果刪除最下層的葉子結(jié)點，則變成滿二叉樹；②對任意結(jié)點i，其左、右子樹的深度分別表示為Lhi與Rhi，則Lhi-Rhi=0或1；③至多有一個度為1的結(jié)點，且度為1的結(jié)點只有左孩子結(jié)點。性質(zhì)

5.4具有

n

個結(jié)點完全二叉樹的深度為

ê?log2

nú?

+1。性質(zhì)

5.5對一棵含n

個結(jié)點的完全二叉樹，按層序自上至下、從左至右，由1

開始連續(xù)編號，則對序號為

i（1≤i≤n）的結(jié)點（稱為結(jié)點

i），有：（1）若

i=1，則該結(jié)點是二叉樹的根，無雙親結(jié)點，否則，結(jié)點

ê?i

/

2ú?

為其雙親結(jié)點；（2）若2i>n，則結(jié)點i無左孩子（為葉子）結(jié)點，否則，結(jié)點2i為其左孩子結(jié)點；（3）若2i+1>n，則結(jié)點i無右孩子結(jié)點，否則，結(jié)點2i+1為其右孩子結(jié)點。二叉樹的邏輯結(jié)構(gòu)5.3.3二叉樹的操作與抽象數(shù)據(jù)類型定義二叉樹的邏輯結(jié)構(gòu)5.3.3二叉樹的操作與抽象數(shù)據(jù)類型定義04PART二叉樹的存儲結(jié)構(gòu)5.4.1二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)是用一維數(shù)組來存儲二叉樹的結(jié)點及其相互關(guān)系，其中結(jié)點的存儲位置（數(shù)組下標(biāo)）蘊含著結(jié)點間的邏輯關(guān)系，即雙親結(jié)點與孩子結(jié)點的關(guān)系（簡稱父子關(guān)系）。首先考慮完全二叉樹的順序存儲，把完全二叉樹的結(jié)點按層序方式自上至下、從左至右進行編號（根結(jié)點編號為

1），然后按編號順序?qū)⒔Y(jié)點依次存儲到一維數(shù)組中。圖（a）的完全二叉樹T1可以用數(shù)組按圖（b）中的形式存儲。二叉樹的存儲結(jié)構(gòu)5.4.1二叉樹的順序存儲結(jié)構(gòu)對于一般二叉樹，如果直接按層序方式對結(jié)點進行編號，然后按編號順序存儲到一維數(shù)組中，此時結(jié)點的存儲位置不能表示結(jié)點間的邏輯關(guān)系。為此，在二叉樹中添加虛結(jié)點，使之成為完全二叉樹的形態(tài)，再按層序?qū)Y(jié)點進行編號并按順序存儲到一維數(shù)組中。下圖二叉樹T2添加了5個虛結(jié)點，在數(shù)組中用0表示。順序存儲結(jié)構(gòu)對于完全二叉樹較為適用，對一般二叉樹存儲效率不一定高，且插入、刪除操作不便。二叉樹的存儲結(jié)構(gòu)5.4.2二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，為表示結(jié)點與其雙親、左孩子、右孩子結(jié)點間的關(guān)系，可設(shè)置相應(yīng)的指針來實現(xiàn)。除了表示結(jié)點信息的數(shù)據(jù)域data外，鏈表結(jié)點還需設(shè)置左、右孩子兩個指針域lchild與

rchild，稱二叉樹的這種鏈?zhǔn)酱鎯Y(jié)構(gòu)為二叉鏈表（BinaryLinkedList）。為方便訪問當(dāng)前結(jié)點的雙親結(jié)點，我們可增設(shè)一個雙親指針域parent，二叉樹的這種含3個指針域的鏈表結(jié)構(gòu)稱為三叉鏈表（TridentLinkedList）。圖（a）與圖（b）分別為二叉鏈表、三叉鏈表的結(jié)點結(jié)構(gòu)示意圖。二叉樹的存儲結(jié)構(gòu)5.4.2二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)下圖為二叉樹T1及其二叉鏈表、三叉鏈表存儲結(jié)構(gòu)示意圖。其中root為指向根結(jié)點的指針，它可被視為鏈表頭指針。性質(zhì)5.6在含n個結(jié)點二叉樹對應(yīng)的二叉鏈表中，共有n+1個空指針域。二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷先序遍歷二叉樹：若二叉樹為空則執(zhí)行空操作并返回，否則執(zhí)行下述步驟：（1）訪問根結(jié)點。（2）先序遍歷根的左子樹。（3）先序遍歷根的右子樹。中序遍歷二叉樹：若二叉樹為空則執(zhí)行空操作并返回，否則執(zhí)行下述步驟：（1）中序遍歷根的左子樹。（2）訪問根結(jié)點。（3）中序遍歷根的右子樹。后序遍歷二叉樹：若二叉樹為空則執(zhí)行空操作并返回，否則執(zhí)行下述步驟：（1）后序遍歷根的左子樹。（2）后序遍歷根的右子樹。（3）訪問根結(jié)點。層序遍歷二叉樹：若二叉樹為空，則執(zhí)行空操作并返回，否則從第一層（根結(jié)點）開始，從上至下逐層遍歷，同一層按從左到右的順序依次訪問每個結(jié)點。

二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷1．先序遍歷遞歸算法：假定二叉樹有n個結(jié)點，估計上述算法的時間復(fù)雜度T(n)時，先考慮根的左、右子樹結(jié)點均衡分布的特殊情況，n充分大時有如下近似關(guān)系：T(n)=O(1)+2T(n/2)?？赏频肨(n)=O(n)；另外，當(dāng)二叉樹為一般形態(tài)時，我們也可以分析推得同樣的結(jié)果。遞歸處理需要用到遞歸工作棧，算法的空間復(fù)雜度在最好與最壞情況下分別為O(logn)、O(n)。二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷2．中序遍歷遞歸算法：算法如下所示。二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷3．后序遍歷遞歸算法：算法如下所示。二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷4．遞歸遍歷算法分析：在二叉樹的先序、中序與后序遍歷過程中，雖然所得的結(jié)點遍歷序列可能不同，但它們的搜索路徑實際是一致的。在遍歷時，搜索總是始于根結(jié)點，也終于根結(jié)點。任意結(jié)點在遍歷過程中都會被遇到3次：第一次遇到后，遞歸地進入其左子樹并對左子樹遍歷；當(dāng)左子樹遍歷完，遞歸處理返回到該結(jié)點時，第二次再遇到它，然后又遞歸地進入其右子樹并對右子樹進行遍歷；當(dāng)右子樹遍歷完遞歸處理再次返回到該結(jié)點時，第三次又遇到該結(jié)點。3種遍歷的不同之處在于，搜索中結(jié)點訪問的時機與先后順序不同。對于一個結(jié)點，先序遍歷是在第一次遇到該結(jié)點時就對其訪問；中序遍歷是在第二次遇到它時對其訪問；后序遍歷則是在第三次又遇到該結(jié)點時才訪問。二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷5．中序遍歷非遞歸算法：遞歸算法雖然簡明、精煉，但一般其執(zhí)行效率不高。因此，有時需要將

其轉(zhuǎn)換為非遞歸算法。非遞歸算法采用循環(huán)結(jié)構(gòu)，算法思想可描述如下。初始化指針棧S，根指針T進棧，棧不空時循環(huán)執(zhí)行以下操作：①讀取棧頂指針，若指針非空，從所指結(jié)點沿左鏈域搜索至最左下結(jié)點，搜索路徑上的結(jié)點指針依次入棧S；②最左下結(jié)點指針退棧，訪問該結(jié)點；③將訪問結(jié)點的右孩子指針入棧，開始對其右子樹進行遍歷。對于含n個結(jié)點的二叉樹，利用非遞歸算法進行中序遍歷，每個結(jié)點分別進、出棧各一次，且執(zhí)行訪問操作一次，故算法的時間復(fù)雜度為O(n)，空間復(fù)雜度為O(MAX_TREE_SIZE)或O(n)。二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷6．層序遍歷算法：由二叉樹層序遍歷操作的定義可知，在進行層次遍歷時，當(dāng)對某一層結(jié)點訪問后，需按這些結(jié)點訪問的次序?qū)Ω鱾€結(jié)點在下層的左、右孩子進行順序訪問，即滿足先訪問的結(jié)點其左、右孩子也要先訪問。顯然，隊列先進先出的特性能滿足這一要求。利用隊列實現(xiàn)層序遍歷的算法思想如下。初始化指針隊列Q，非空根指針T進隊，隊列不空時循環(huán)執(zhí)行以下操作：①隊頭結(jié)點出隊，并訪問該結(jié)點；②將訪問結(jié)點的非空左、右孩子指針依次進隊。含n個結(jié)點的二叉樹在層序遍歷過程中，每個結(jié)點分別進、出隊各一次，且執(zhí)行訪問操作一次，故算法的時間復(fù)雜度O(n)，空間復(fù)雜度為O(MAX_TREE_SIZE)或O(n)。二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷7．創(chuàng)建二叉樹算法：創(chuàng)建二叉樹，即通過二叉樹的某種定義信息生成對應(yīng)的二叉樹并建立其

二叉鏈表存儲結(jié)構(gòu)。雖然只給出二叉樹的先序序列不能定義一棵二叉樹，但如果在先序遍歷序列中插入空格符，則由帶空格符的先序遍歷序列可唯一確定一棵二叉樹。例如，給定先序遍歷序列ADFEFFFGFFBFCFF（其中F為空格符，它表示對應(yīng)的結(jié)點為空（虛結(jié)點）），其附帶虛結(jié)點的

二叉樹如圖（a）所示，其對應(yīng)的二叉樹如圖（b）所示，而該二叉樹對應(yīng)的二叉鏈表示意圖如圖（c）所示。創(chuàng)建二叉樹可以分為3步：①生成根結(jié)點；②創(chuàng)建根的左子樹；③創(chuàng)建根的右子樹。二叉樹的存儲結(jié)構(gòu)5.4.3基于二叉鏈表的二叉樹遍歷8．銷毀二叉樹算法：二叉鏈表是基于動態(tài)內(nèi)存分配而建立的。當(dāng)二叉樹處理完后，我們需銷毀對應(yīng)的二叉樹，釋放其二叉鏈表的存儲空間。銷毀二叉樹可分為3步：①銷毀根的左子樹；②銷毀根的右子樹；③釋放根結(jié)點。這與二叉樹的后序遍歷處理邏輯一致。二叉樹的存儲結(jié)構(gòu)5.4.4線索鏈表與線索二叉樹1．線索鏈表存儲結(jié)構(gòu)：在遍歷所得的結(jié)點線性序列中，一個結(jié)點存在唯一的直接前驅(qū)與直接后繼結(jié)點，但是二叉鏈表并沒有表示這種關(guān)系，而是只保存左、右孩子指針信息。如果在二叉鏈表結(jié)點中直接增設(shè)指向前驅(qū)與后繼結(jié)點的指針域，則會顯著降低存儲效率?？紤]到n個結(jié)點的二叉鏈表中有n+1個空鏈域，若某結(jié)點無左孩子結(jié)點，此時可令其lchild域指向其前驅(qū)；若某結(jié)點無右孩子結(jié)點，此時可令其rchild域指向其后繼。為區(qū)分結(jié)點鏈域究竟是指向左、右孩子還是前驅(qū)、后繼，需在二叉鏈表結(jié)點中增設(shè)兩個標(biāo)志位LTag與Rtag，形成含有5個域的結(jié)點結(jié)構(gòu)，如下圖所示。二叉樹的存儲結(jié)構(gòu)5.4.4線索鏈表與線索二叉樹以上述這種結(jié)點結(jié)構(gòu)構(gòu)成的二叉鏈表稱為二叉樹的線索鏈表（Threaded

Linked

List），指向結(jié)點前驅(qū)與后繼的指針稱為線索（Thread），加上線索的二叉樹則稱為線索二叉樹（Threaded

BinaryTree）。線索信息只有通過遍歷二叉樹才可以確定，對二叉樹按某種方式遍歷使其變成線索二叉樹的過程稱為二叉樹的線索化。圖（a）為二叉樹T，其中序遍歷序列為B,D,C,E,A,F,G，對應(yīng)的中序線索二叉樹與中序線索鏈表分別如圖（b）和圖（c）所示。二叉樹的存儲結(jié)構(gòu)5.4.4線索鏈表與線索二叉樹由于在二叉樹的遍歷序列中首結(jié)點無前驅(qū)、尾結(jié)點無后繼、對應(yīng)的兩個線索懸空，因此在中序線索鏈表中設(shè)置一個頭結(jié)點，使之成為首結(jié)點的前驅(qū)、尾結(jié)點的后繼。右圖為空二叉樹的線索鏈表，頭結(jié)點指針為thrt。一棵二叉樹可以有多種方式的線索化，如利用先序遍歷與后序遍歷可得到先序線索二叉樹與后序線索二叉樹，也可以在線索二叉樹中只設(shè)置一種線索，如在后序線索二叉樹中只設(shè)置后繼線索，稱其為后序后繼線索二叉樹。二叉樹的存儲結(jié)構(gòu)5.4.4線索鏈表與線索二叉樹2．線索鏈表的基本操作：二叉樹的線索鏈表可以被看作是一個雙向線索鏈表，該表既允許從遍歷序列首結(jié)點出發(fā)來沿后繼線索進行遍歷，又允許從遍歷序列的尾結(jié)點出發(fā)來沿前驅(qū)線索對二叉樹進行逆向遍歷?；谙刃蚓€索鏈表的二叉樹遍歷。其算法思想為：①通過T->lchild訪問首結(jié)點，即二叉樹根結(jié)點；②循環(huán)訪問后繼結(jié)點，若指針p指向當(dāng)前已訪問結(jié)點，如它有左孩子結(jié)點，即p->LTag=0，則左孩子p->lchild為其訪問的后繼結(jié)點；若p結(jié)點無左孩子結(jié)點，無論p->RTag=0或1，p->rchild指向右孩子結(jié)點或表線索，均指示其訪問的后繼結(jié)點。二叉樹的存儲結(jié)構(gòu)5.4.4線索鏈表與線索二叉樹基于中序線索鏈表的二叉樹遍歷。其算法思想是：①搜索首結(jié)點，該結(jié)點處于二叉樹最左下，算法可從根結(jié)點出發(fā)，不斷沿著左孩子指針（此時LTag=0）搜索，直至LTag=1，便達到最左下結(jié)點，設(shè)p指向該結(jié)點；②訪問p結(jié)點；③訪問后繼結(jié)點，若p->RTag=1，則p->rchild為其后繼結(jié)點，訪問該結(jié)點，p移向該結(jié)點，并重復(fù)這一過程直至p->RTag=0，此時p->rchild非線索，而是指向p的右孩子結(jié)點，這時，p結(jié)點的后繼是p右子樹的最左下結(jié)點，于是，回到①進行搜索，開始下一輪循環(huán)。上述中序遍歷算法雖然時間復(fù)雜度仍為O(n)，但比基于二叉鏈表的中序遍歷非遞歸算法計算量少，且無須使用棧。二叉樹的存儲結(jié)構(gòu)5.4.4線索鏈表與線索二叉樹中序線索鏈表的建立?？梢岳枚鏄涞闹行虮闅v遞歸處理邏輯設(shè)計二叉樹的中序線索化過程：①建立頭結(jié)點；②左子樹線索化；③處理根結(jié)點，如修改標(biāo)記域與線索；④右子樹線索化。如果不考慮頭結(jié)點，上述步驟②～步驟④與中序遍歷遞歸處理完全一致，只是訪問結(jié)點的處理在于修改當(dāng)前結(jié)點及其前驅(qū)結(jié)點的標(biāo)記域與線索域。若p指向當(dāng)前訪問結(jié)點，pre指向其剛訪問的前驅(qū)結(jié)點，則結(jié)點處理任務(wù)可具體描述如下，即每次只可能修改前驅(qū)結(jié)點的右指針（后繼）和當(dāng)前結(jié)點的左指針（前驅(qū)）。。（1）若p->lchild=NULL，則{p->Ltag=1;p->lchild=pre;}（2）若pre->rchild=NULL，則{pre->Rtag=1;pre->rchild=p;}05PART樹、森林與二叉樹的轉(zhuǎn)換5.5.1樹與二叉樹的轉(zhuǎn)換1．樹轉(zhuǎn)換成二叉樹根據(jù)樹的二叉鏈表特征，我們可以按以下規(guī)則把一棵樹轉(zhuǎn)換成二叉樹。（1）加線：在樹的相鄰兄弟結(jié)點之間依次加一連線。（2）抹線：對每個結(jié)點（除了其最左孩子結(jié)點外）抹去它與其余孩子結(jié)點之間的連線。（3）旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將樹按順時針旋轉(zhuǎn)45°，使其成為二叉樹層次結(jié)構(gòu)。下圖為一棵樹轉(zhuǎn)換成二叉樹的處理過程?？梢园l(fā)現(xiàn)，在轉(zhuǎn)換后的二叉樹中根結(jié)點的右子樹一定為空；結(jié)點與其右分支上的各結(jié)點原來在樹中是兄弟關(guān)系。5.5.1樹與二叉樹的轉(zhuǎn)換2．二叉樹轉(zhuǎn)換成樹對樹轉(zhuǎn)換成二叉樹過程中的加線、抹線進行逆操作便可以將二叉樹轉(zhuǎn)換成樹。（1）加線：若某結(jié)點是雙親結(jié)點的左孩子結(jié)點，則將該結(jié)點的右孩子結(jié)點、右孩子的右孩子結(jié)點以及沿分支找到的所有右孩子結(jié)點都與雙親結(jié)點用線連起來。（2）抹線：抹掉原二叉樹中所有的雙親與右孩子結(jié)點之間的連線。（3）調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)。下圖為將一棵二叉樹轉(zhuǎn)換成樹的處理過程。樹、森林與二叉樹的轉(zhuǎn)換5.5.2森林與二叉樹的轉(zhuǎn)換1．森林轉(zhuǎn)換成二叉樹（1）把森林中各棵樹分別轉(zhuǎn)換成二叉樹。（2）把每棵二叉樹的根結(jié)點用線相連。（3）把連成整體的結(jié)構(gòu)以第一棵樹根結(jié)點為二叉樹的根，再以該根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹結(jié)構(gòu)。右圖為將含3棵樹的森林轉(zhuǎn)換成一棵二叉樹的處理過程?？梢钥吹?，二叉樹的根及其左子樹源于第一棵樹；根結(jié)點及其右分支上根結(jié)點個數(shù)就是森林中樹的棵數(shù)。樹、森林與二叉樹的轉(zhuǎn)換5.5.2森林與二叉樹的轉(zhuǎn)換2．二叉樹轉(zhuǎn)換成森林（1）連線、抹線：把二叉樹中根結(jié)點與其右孩子結(jié)點連線，并將沿右分支搜索到的所有右孩子結(jié)點間連線全部抹掉，使其分割成若干棵孤立的二叉樹。（2）還原：利用二叉樹轉(zhuǎn)換成樹的規(guī)則分別把孤立的二叉樹還原成樹，從而形成森林。樹、森林與二叉樹的轉(zhuǎn)換5.5.3樹與森林的遍歷1．樹的遍歷（1）先根遍歷規(guī)則：若樹為空，則執(zhí)行空操作，返回，否則執(zhí)行以下步驟。①訪問樹的根結(jié)點。②依次先根遍歷根的每棵子樹。（2）后根遍歷規(guī)則：若樹為空，則執(zhí)行空操作，返回，否則執(zhí)行以下步驟。①依次后根遍歷根的每棵子樹。②訪問樹的根結(jié)點。其中，樹的遍歷可轉(zhuǎn)換為對樹所對應(yīng)的二叉樹進行先序遍歷或中序遍歷。樹、森林與二叉樹的轉(zhuǎn)換5.5.3樹與森林的遍歷2．森林的遍歷（1）先序遍歷規(guī)則：若森林為空，則執(zhí)行空操作，返回，否則執(zhí)行以下步驟。①訪問第一棵樹的根結(jié)點。②先序遍歷第一棵樹中根結(jié)點的子樹森林。③先序遍歷除去第一棵樹后余下的樹構(gòu)成的森林。（2）中序遍歷規(guī)則：若森林為空，則執(zhí)行空操作，返回，否則執(zhí)行以下步驟。①中序遍歷第一棵樹根結(jié)點的子樹森林。②訪問第一棵樹的根結(jié)點。③中序遍歷除第一棵樹后余下的樹構(gòu)成的森林。其中，森林的遍歷可轉(zhuǎn)換為對森林所對應(yīng)的二叉樹進行先序遍歷或中序遍歷。樹、森林與二叉樹的轉(zhuǎn)換06PART5.6.1哈夫曼樹與哈夫曼算法

哈夫曼樹5.6.1哈夫曼樹與哈夫曼算法哈夫曼樹（HuffmanTree）：在具有

n

個相同葉子的各二叉樹中，帶權(quán)路徑長度

WPL

最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹（Optimal

BinaryTree）。例如，二叉樹有4個葉子結(jié)點a、b、c、d，其權(quán)值分別為8、5、1、3，下圖給出了3個不同形態(tài)的二叉樹，它們具有不同的帶權(quán)路徑長度。其中，第一棵是完全二叉樹，但它并非是哈夫曼樹；第三棵的WPL

最小，它剛好是一棵哈夫曼樹。在葉子結(jié)點給定的前提下，哈夫曼樹并不唯一，但所有哈夫曼樹的WPL

都一定相等且達到最小值。哈夫曼樹5.6.1哈夫曼樹與哈夫曼算法哈夫曼算法給出了哈夫曼樹的構(gòu)造方法，它是一種貪心算法。其算法思想描述如下。（1）由給定的n個權(quán)值{w1,w2,…,wn}構(gòu)造n棵二叉樹，并構(gòu)成一個二叉樹的集合F={T1,T2,…,Tn}，每棵二叉樹

Ti僅有一個結(jié)點，即根結(jié)點（權(quán)值為

wi，i=1,2,…,n）。（2）在F中選取兩棵根結(jié)點權(quán)值最小的二叉樹作為左、右子樹構(gòu)造一棵新二叉樹，并且置新二叉樹根結(jié)點權(quán)值為左、右子樹上根結(jié)點的權(quán)值之和。（3）從F中刪除這兩棵二叉樹，同時將新二叉樹加入F中。（4）重復(fù)（2）和（3），直到

F中只含一棵二叉樹為止，這棵樹就是Huffman樹。哈夫曼樹5.6.1哈夫曼樹與哈夫曼算法下圖給出從5個權(quán)值按哈夫曼算法構(gòu)造一棵哈夫曼樹的過程。哈夫曼樹5.6.1哈夫曼樹與哈夫曼算法從哈夫曼算法中可以看出，哈夫曼樹中不存在度為1的結(jié)點，因此含n個葉子的哈夫曼樹共有2n-1個結(jié)點。在哈夫曼樹的應(yīng)用中，常需要訪問當(dāng)前結(jié)點的雙親結(jié)點，因此哈夫曼樹一般采用三叉鏈表表示，且以靜態(tài)鏈表的方式實現(xiàn)。鏈表結(jié)點除了parent、lchild、rchild3個指針域外，還設(shè)置一個權(quán)值域weight。下面給出哈夫曼樹的存儲結(jié)構(gòu)定義。哈夫曼樹5.6.1哈夫曼樹與哈夫曼算法給出基于上述存儲結(jié)構(gòu)的哈夫曼樹構(gòu)造算法。哈夫曼樹5.6.1哈夫曼樹與哈夫曼算法其中，上述算法中的Select函數(shù)可自行編寫。哈夫曼樹5.6.2哈夫曼編碼對文本數(shù)據(jù)的傳輸與壓縮通常需要使用編碼技術(shù)。文本數(shù)據(jù)可以被看作是字符序列，把每個字符轉(zhuǎn)換成一個二進制位串，稱為編碼（Coding）；當(dāng)每個字符都編碼為長度相同的二進制位串時，我們稱這種編碼為等長編碼（Equal-length

Code）；每個字符編碼后對應(yīng)二進制位串的長度稱為碼長（Code

Length）。當(dāng)每個字符在文本中出現(xiàn)的頻率相同時，等長編碼具有最高的編碼效率（文本經(jīng)編碼后，其二進制串長整體最短）。編碼后，當(dāng)不同字符的碼長不都相等時，稱為不等長編碼（Unequal-length

Code）。當(dāng)文本中字符出現(xiàn)的頻率不均等時，采用不等長編碼使頻率高的字符碼長短、頻率低的字符碼長稍長，這樣可以提高編碼效率