數(shù)據(jù)結(jié)構(gòu)第五章樹(shù)和二叉樹(shù)

數(shù)據(jù)結(jié)構(gòu)王向文1325300350@西北師范大學(xué)第五章樹(shù)和二叉樹(shù)1樹(shù)的基本概念2二叉樹(shù)3遍歷二叉樹(shù)4二叉搜索樹(shù)5樹(shù)與森林6Huffman樹(shù)1樹(shù)的基本概念樹(shù)的定義樹(shù)的基本術(shù)語(yǔ)1.1樹(shù)的定義樹(shù)(Tree)是n(n≧0)個(gè)結(jié)點(diǎn)的有限集合T，若n=0時(shí)稱(chēng)為空樹(shù)，否則：⑴有且只有一個(gè)特殊的稱(chēng)為樹(shù)的根(Root)結(jié)點(diǎn)；⑵若n>1時(shí)，其余的結(jié)點(diǎn)被分為m(m>0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集本身又是一棵樹(shù)，稱(chēng)其為根的子樹(shù)(Subtree)。1.1樹(shù)的定義AABDCEGFHIMJNKL(a)

只有根結(jié)點(diǎn)(b)

一般的樹(shù)1.2樹(shù)的基本術(shù)語(yǔ)⑴結(jié)點(diǎn)(node)：一個(gè)數(shù)據(jù)元素及其若干指向其子樹(shù)的分支。⑵結(jié)點(diǎn)的度(degree)、樹(shù)的度：結(jié)點(diǎn)所擁有的子樹(shù)的棵數(shù)稱(chēng)為結(jié)點(diǎn)的度。樹(shù)中結(jié)點(diǎn)度的最大值稱(chēng)為樹(shù)的度。⑶葉子(left)結(jié)點(diǎn)、非葉子結(jié)點(diǎn)：樹(shù)中度為0的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)(或終端結(jié)點(diǎn))。相對(duì)應(yīng)地，度不為0的結(jié)點(diǎn)稱(chēng)為非葉子結(jié)點(diǎn)(或非終端結(jié)點(diǎn)或分支結(jié)點(diǎn))。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)又稱(chēng)為內(nèi)部結(jié)點(diǎn)。1.2樹(shù)的基本術(shù)語(yǔ)⑷孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)(child)或子結(jié)點(diǎn)；相應(yīng)地，該結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)(parent)或父結(jié)點(diǎn)。⑸層次、堂兄弟結(jié)點(diǎn)：規(guī)定樹(shù)中根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加1。

若某結(jié)點(diǎn)在第l(l≧1)層，則其子結(jié)點(diǎn)在第l+1層。雙親結(jié)點(diǎn)在同一層上的所有結(jié)點(diǎn)互稱(chēng)為堂兄弟結(jié)點(diǎn)。1.2樹(shù)的基本術(shù)語(yǔ)⑹結(jié)點(diǎn)的層次路徑、祖先、子孫：從根結(jié)點(diǎn)開(kāi)始，到達(dá)某結(jié)點(diǎn)p所經(jīng)過(guò)的所有結(jié)點(diǎn)成為結(jié)點(diǎn)p的層次路徑(有且只有一條)。結(jié)點(diǎn)p的層次路徑上的所有結(jié)點(diǎn)（p除外）稱(chēng)為p的祖先(ancester)。以某一結(jié)點(diǎn)為根的子樹(shù)中的任意結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)(descent)。⑺樹(shù)的深度(depth)：樹(shù)中結(jié)點(diǎn)的最大層次值，又稱(chēng)為樹(shù)的高度。1.2樹(shù)的基本術(shù)語(yǔ)⑻有序樹(shù)和無(wú)序樹(shù)：對(duì)于一棵樹(shù)，若其中每一個(gè)結(jié)點(diǎn)的子樹(shù)（若有）具有一定的次序，則該樹(shù)稱(chēng)為有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)。⑼森林(forest)：是m(m≧0)棵互不相交的樹(shù)的集合。顯然，若將一棵樹(shù)的根結(jié)點(diǎn)刪除，剩余的子樹(shù)就構(gòu)成了森林。1.3樹(shù)的抽象數(shù)據(jù)類(lèi)型定義ADTTree{數(shù)據(jù)對(duì)象D：D是具有相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱(chēng)為空樹(shù)；

……基本操作：……}ADTTree2二叉樹(shù)二叉樹(shù)的定義二叉樹(shù)的基本形態(tài)二叉樹(shù)的性質(zhì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)2.1二叉樹(shù)的定義二叉樹(shù)(Binarytree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。若n=0時(shí)稱(chēng)為空樹(shù)，否則：⑴有且只有一個(gè)特殊的稱(chēng)為樹(shù)的根(Root)結(jié)點(diǎn)；⑵若n>1時(shí)，其余的結(jié)點(diǎn)被分成為二個(gè)互不相交的子集T1,T2，分別稱(chēng)之為左、右子樹(shù)，并且左、右子樹(shù)又都是二叉樹(shù)。2.2二叉樹(shù)的基本形態(tài)AAAA(a)(b)(c)(d)(e)(a)空二叉樹(shù)(b)單結(jié)點(diǎn)二叉樹(shù)(c)右子樹(shù)為空(d)左子樹(shù)為空(e)左、右子樹(shù)都不空二叉樹(shù)的基本形態(tài)2.3二叉樹(shù)的性質(zhì)性質(zhì)1：在非空二叉樹(shù)中，第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≧1)。性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k≧1)。性質(zhì)3：對(duì)任何一棵二叉樹(shù)，若其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。2.3二叉樹(shù)的性質(zhì)滿(mǎn)二叉樹(shù)：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)(FullBinaryTree)。滿(mǎn)二叉樹(shù)的特點(diǎn)：基本特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)總是最大結(jié)點(diǎn)數(shù)。滿(mǎn)二叉樹(shù)的所有的支結(jié)點(diǎn)都有左、右子樹(shù)?？蓪?duì)滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，若規(guī)定從根結(jié)點(diǎn)開(kāi)始，按“自上而下、自左至右”的原則進(jìn)行。2.3二叉樹(shù)的性質(zhì)完全二叉樹(shù)(CompleteBinaryTree)：如果深度為k，由n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)，該二叉樹(shù)稱(chēng)為完全二叉樹(shù)?；蛏疃葹閗的滿(mǎn)二叉樹(shù)中編號(hào)從1到n的前n個(gè)結(jié)點(diǎn)構(gòu)成了一棵深度為k的完全二叉樹(shù)。

其中2k-1≦

n≦2k-1。完全二叉樹(shù)是滿(mǎn)二叉樹(shù)的一部分，而滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的特例。2.3二叉樹(shù)的性質(zhì)完全二叉樹(shù)的特點(diǎn)：

若完全二叉樹(shù)的深度為k，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第k層或k-1層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹(shù)的最大層次為l，則其左子樹(shù)的最大層次為l或l+1。894101151213614157213894101152112673(a)滿(mǎn)二叉樹(shù)(b)完全二叉樹(shù)1362455674213(c)非完全二叉樹(shù)特殊形態(tài)的二叉樹(shù)2.3二叉樹(shù)的性質(zhì)性質(zhì)4：n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為：㏒2n

+1。其中符號(hào)：x表示不小于x的最小

整數(shù)。x

表示不大于x的最大整數(shù)。2.3二叉樹(shù)的性質(zhì)性質(zhì)5：若對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)(深度為

㏒2n

+1)的結(jié)點(diǎn)按層（從第1層到第㏒2n

+1層)序自左至右進(jìn)行編號(hào),則對(duì)于編號(hào)為i（1≦i≦n)的結(jié)點(diǎn)：⑴若i=1：則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親結(jié)點(diǎn)；否則，若i>1，則其雙親結(jié)點(diǎn)編號(hào)是

i/2

。⑵如果2i>n：則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無(wú)左孩子；否則，其左孩子結(jié)點(diǎn)編號(hào)是2i。⑶如果2i+1>n：則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子結(jié)點(diǎn)編號(hào)是2i+1。性質(zhì)6：給定N個(gè)節(jié)點(diǎn)，能構(gòu)成CN種不同的二叉樹(shù)，其中為卡塔蘭數(shù)（Catalan）。2.4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：用一組地址連續(xù)的存儲(chǔ)單元依次“自上而下、自左至右”存儲(chǔ)完全二叉樹(shù)的數(shù)據(jù)元素。對(duì)于完全二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組的下標(biāo)值為i-1的分量中。對(duì)于一般的二叉樹(shù)，將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組中。最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的單支樹(shù)需要長(zhǎng)度為2k-1的一維數(shù)組。abcdhiejklfg(a)完全二叉樹(shù)(b)非完全二叉樹(shù)abcdefgh???123456789101112

abcdefghijkl

(c)完全二叉樹(shù)的順序存儲(chǔ)形式1234567891011abcde?h?

?

fg(d)非完全二叉樹(shù)的順序存儲(chǔ)形式2.4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈表結(jié)點(diǎn)。有三個(gè)域：一個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(jié)點(diǎn)的指針域。三叉鏈表結(jié)點(diǎn)。除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域，用來(lái)指向結(jié)點(diǎn)的父結(jié)點(diǎn)。LchilddataRchildLchilddataparentRchild(a)二叉鏈表結(jié)點(diǎn)(b)三叉鏈表結(jié)點(diǎn)鏈表結(jié)點(diǎn)結(jié)構(gòu)形式2.4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(a)二叉樹(shù)afedcbg(c)三叉鏈表

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

d?e?g??f?T3遍歷二叉樹(shù)遍歷二叉樹(shù)(TraversingBinaryTree)：是指按指定的規(guī)律對(duì)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)訪(fǎng)問(wèn)一次且僅訪(fǎng)問(wèn)一次。先(根)序遍歷中(根)序遍歷后(根)序遍歷3.1先序遍歷二叉樹(shù)若二叉樹(shù)為空，則遍歷結(jié)束；否則⑴訪(fǎng)問(wèn)根結(jié)點(diǎn)；⑵先序遍歷左子樹(shù)(遞歸調(diào)用本算法)；⑶先序遍歷右子樹(shù)(遞歸調(diào)用本算法)。3.1先序遍歷二叉樹(shù)voidPreorderTraverse(BTNode*T){if(T!=NULL){visit(T->data);/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}3.2中序遍歷二叉樹(shù)若二叉樹(shù)為空，則遍歷結(jié)束；否則⑴中序遍歷左子樹(shù)(遞歸調(diào)用本算法)；⑵訪(fǎng)問(wèn)根結(jié)點(diǎn)；⑶中序遍歷右子樹(shù)(遞歸調(diào)用本算法)。3.2中序遍歷二叉樹(shù)voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/InorderTraverse(T->Rchild);}}3.3后序遍歷二叉樹(shù)若二叉樹(shù)為空，則遍歷結(jié)束；否則⑴后序遍歷左子樹(shù)(遞歸調(diào)用本算法)；⑵后序遍歷右子樹(shù)(遞歸調(diào)用本算法)；⑶訪(fǎng)問(wèn)根結(jié)點(diǎn)。3.3后序遍歷二叉樹(shù)voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*訪(fǎng)問(wèn)根結(jié)點(diǎn)*/}}3.4根據(jù)遍歷結(jié)果構(gòu)建二叉樹(shù)二叉樹(shù)遍歷的結(jié)果是將一個(gè)非線(xiàn)性結(jié)構(gòu)中的數(shù)據(jù)通過(guò)訪(fǎng)問(wèn)排列到一個(gè)線(xiàn)性序列中。前序序列：abdce特點(diǎn)是第一個(gè)訪(fǎng)問(wèn)的a一定是樹(shù)根，只要左子樹(shù)非空，后面緊跟的b一定是根的左子女，…中序序列：bdaec特點(diǎn)是樹(shù)根a把整個(gè)中序分成兩部分，a左側(cè)子序列是根的左子樹(shù)上的結(jié)點(diǎn)數(shù)據(jù)，右側(cè)子序列是根的右子樹(shù)上的結(jié)點(diǎn)數(shù)據(jù)。abcde3.4根據(jù)遍歷結(jié)果構(gòu)建二叉樹(shù)由二叉樹(shù)的前序序列和中序序列可唯一地確定一棵二叉樹(shù)。例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},構(gòu)造二叉樹(shù)過(guò)程如下：HBDFEKCGAEKCGABHDF3.4根據(jù)遍歷結(jié)果構(gòu)建二叉樹(shù)KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG3.5層次遍歷二叉樹(shù)層次遍歷二叉樹(shù)，是從根結(jié)點(diǎn)開(kāi)始遍歷，按層次次序“自上而下，從左至右”訪(fǎng)問(wèn)樹(shù)中的各結(jié)點(diǎn)。這種遍歷需要使用一個(gè)先進(jìn)先出的隊(duì)列，在處理上一層時(shí)，將其下一層的結(jié)點(diǎn)直接進(jìn)到隊(duì)列（的隊(duì)尾）。在上一層結(jié)點(diǎn)遍歷完后，下一層結(jié)點(diǎn)正好處于隊(duì)列的隊(duì)頭，可以繼續(xù)訪(fǎng)問(wèn)它們。4二叉搜索樹(shù)二叉排序樹(shù)（BinarySortTree）又稱(chēng)二叉查找樹(shù)（BinarySearchTree），亦稱(chēng)二叉搜索樹(shù)。二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：（1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；（3）左、右子樹(shù)也分別為二叉排序樹(shù)；（4）沒(méi)有鍵值相等的節(jié)點(diǎn)。4.1二叉搜索樹(shù)的查找若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹(shù)。若大于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹(shù)。若子樹(shù)為空，查找不成功。4.2二叉搜索樹(shù)的插入在插入之前，先使用搜索算法在樹(shù)中檢查要插入元素有還是沒(méi)有。如果搜索成功，說(shuō)明樹(shù)中已經(jīng)有這個(gè)元素，不再插入；如果搜索不成功，說(shuō)明樹(shù)中原來(lái)沒(méi)有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}4.3二叉搜索樹(shù)的刪除刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。被刪結(jié)點(diǎn)右子樹(shù)為空，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左子樹(shù)為空，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左、右子樹(shù)都不為空，可以在它的右子樹(shù)中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來(lái)處理這個(gè)結(jié)點(diǎn)的刪除問(wèn)題。4.3二叉搜索樹(shù)的刪除被刪結(jié)點(diǎn)右子樹(shù)為空：4.3二叉搜索樹(shù)的刪除被刪結(jié)點(diǎn)左子樹(shù)為空：4.3二叉搜索樹(shù)的刪除被刪結(jié)點(diǎn)左、右子樹(shù)都不為空：5樹(shù)與森林樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)與二叉樹(shù)的轉(zhuǎn)換5.1樹(shù)的存儲(chǔ)結(jié)構(gòu)以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類(lèi)型定義如下：typedefstructCSnode{ElemTypedata;structCSnode*firstchild,*nextsibing;}CSNode;樹(shù)及孩子兄弟存儲(chǔ)結(jié)構(gòu)(b)樹(shù)

FGRABCDE(c)孩子兄弟存儲(chǔ)結(jié)構(gòu)

R?

A?D

C??G?B?F??E?孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchilddatanextsibing(a)結(jié)點(diǎn)結(jié)構(gòu)5.2樹(shù)與二叉樹(shù)的轉(zhuǎn)換由于二叉樹(shù)和樹(shù)都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，對(duì)比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可以導(dǎo)出樹(shù)和二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。從物理結(jié)構(gòu)來(lái)看，樹(shù)和二叉樹(shù)的二叉鏈表是相同的，只是對(duì)指針的邏輯解釋不同而已。從樹(shù)的二叉鏈表表示的定義可知，任何一棵和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)一定為空。樹(shù)與二叉樹(shù)的對(duì)應(yīng)關(guān)系二叉樹(shù)

CERADB

R?

A?D??C?

B?E?樹(shù)

RABCDE對(duì)應(yīng)關(guān)系

R?

A?D??C?

B?E??C?

B?E?

R

A?D?存儲(chǔ)解釋存儲(chǔ)解釋5.2樹(shù)與二叉樹(shù)的轉(zhuǎn)換樹(shù)轉(zhuǎn)換成二叉樹(shù)：⑴加虛線(xiàn)。在樹(shù)的每層按從“左至右”的順序在兄弟結(jié)點(diǎn)之間加虛線(xiàn)相連。⑵去連線(xiàn)。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與所有其它子結(jié)點(diǎn)的連線(xiàn)都去掉。⑶旋轉(zhuǎn)。將樹(shù)順時(shí)針旋轉(zhuǎn)450，原有的實(shí)線(xiàn)左斜。⑷整型。將旋轉(zhuǎn)后樹(shù)中的所有虛線(xiàn)改為實(shí)線(xiàn)，并向右斜。5.2樹(shù)與二叉樹(shù)的轉(zhuǎn)換樹(shù)向二叉樹(shù)的轉(zhuǎn)換過(guò)程(a)一般的樹(shù)

FGRABCDEFGRABCDE(b)加虛線(xiàn)，去連線(xiàn)后

(C)轉(zhuǎn)換后的二叉樹(shù)FGRACDBE5.2樹(shù)與二叉樹(shù)的轉(zhuǎn)換轉(zhuǎn)換后的二叉樹(shù)的特點(diǎn)是：

二叉樹(shù)的根結(jié)點(diǎn)沒(méi)有右子樹(shù)，只有左子樹(shù)；

左子結(jié)點(diǎn)仍然是原來(lái)樹(shù)中相應(yīng)結(jié)點(diǎn)的左子結(jié)點(diǎn)，而所有沿右鏈往下的右子結(jié)點(diǎn)均是原來(lái)樹(shù)中該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。5.2樹(shù)與二叉樹(shù)的轉(zhuǎn)換二叉樹(shù)轉(zhuǎn)換成樹(shù)：⑴加虛線(xiàn)。若某結(jié)點(diǎn)i是其父結(jié)點(diǎn)的左子樹(shù)的根結(jié)點(diǎn)，則將該結(jié)點(diǎn)i的右子結(jié)點(diǎn)以及沿右子鏈不斷地搜索所有的右子結(jié)點(diǎn)，將所有這些右子結(jié)點(diǎn)與i結(jié)點(diǎn)的父結(jié)點(diǎn)之間加虛線(xiàn)相連。⑵去連線(xiàn)。去掉二叉樹(shù)中所有父結(jié)點(diǎn)與其右子結(jié)點(diǎn)之間的連線(xiàn)。⑶規(guī)整化。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛線(xiàn)變成實(shí)線(xiàn)。5.2樹(shù)與二叉樹(shù)的轉(zhuǎn)換二叉樹(shù)向樹(shù)的轉(zhuǎn)換過(guò)程(C)還原后的樹(shù)FGRABCDE(b)去連線(xiàn)后(a)加虛線(xiàn)后FGRACDBECFGRADBE5.3二叉樹(shù)與森林的轉(zhuǎn)換森林轉(zhuǎn)換成二叉樹(shù)：(1)將F={T1,T2,?,Tn}中的每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)。(2)按給出的森林中樹(shù)的次序，從最后一棵二叉樹(shù)開(kāi)始，每棵二叉樹(shù)作為前一棵二叉樹(shù)的根結(jié)點(diǎn)的右子樹(shù)，依次類(lèi)推，則第一棵樹(shù)的根結(jié)點(diǎn)就是轉(zhuǎn)換后生成的二叉樹(shù)的根結(jié)點(diǎn)。5.3二叉樹(shù)與森林的轉(zhuǎn)換ACBDGMLHK(a)森林森林轉(zhuǎn)換成二叉樹(shù)的過(guò)程(b)森林中每棵樹(shù)對(duì)應(yīng)的二叉樹(shù)ABCDGLKHM(c)森林對(duì)應(yīng)的二叉樹(shù)ABCDGLKHM5.3二叉樹(shù)與森林的轉(zhuǎn)換二叉樹(shù)轉(zhuǎn)換成森林：(1)去連線(xiàn)。將二叉樹(shù)B的根結(jié)點(diǎn)與其右子結(jié)點(diǎn)以及沿右子結(jié)點(diǎn)鏈方向的所有右子結(jié)點(diǎn)的連線(xiàn)全部去掉，得到若干棵孤立的二叉樹(shù)，每一棵就是原來(lái)森林F中的樹(shù)依次對(duì)應(yīng)的二叉樹(shù)。(2)二叉樹(shù)的還原。將各棵孤立的二叉樹(shù)按二叉樹(shù)還原為樹(shù)的方法還原成一般的樹(shù)。5.3二叉樹(shù)與森林的轉(zhuǎn)換二叉樹(shù)還原成森林的過(guò)程ACBDMGLHK(c)還原成森林(a)二叉樹(shù)ABCDGLKHM(b)去連線(xiàn)后ABCDMGLKH5.4樹(shù)與森林的遍歷樹(shù)的遍歷：先序遍歷：先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后依次先序遍歷完每棵子樹(shù)。后序遍歷：先依次后序遍歷完每棵子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)。樹(shù)的先序遍歷實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉樹(shù)后對(duì)二叉樹(shù)的先序遍歷相同。樹(shù)的后序遍歷實(shí)質(zhì)上與將樹(shù)轉(zhuǎn)換成二叉樹(shù)后對(duì)二叉樹(shù)的中序遍歷相同。5.4樹(shù)與森林的遍歷先序遍歷的次序是：ABCDEFGIJHK后序遍歷的次序是：CDBFGIJHEKAABDCKGJIFHE5.4樹(shù)與森林的遍歷森林的遍歷：先序遍歷：按先序遍歷樹(shù)的方式依次遍歷森林中的每棵樹(shù)。中序遍歷：按后序遍歷樹(shù)的方式依次遍歷森林中的每棵樹(shù)。6Huffman樹(shù)基本概念Huffman樹(shù)的構(gòu)造6.1基本概念結(jié)點(diǎn)路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。路徑長(zhǎng)度：結(jié)點(diǎn)路徑上的分支數(shù)目稱(chēng)為路徑長(zhǎng)度。樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)的到樹(shù)的根結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)(值)的乘積。6.1基本概念