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

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

只有根結(jié)點(b)

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

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

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

其中2k-1≦

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

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

+1。其中符號：x表示不小于x的最小

整數(shù)。x

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

㏒2n

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

+1層)序自左至右進行編號,則對于編號為i（1≦i≦n)的結(jié)點：⑴若i=1：則結(jié)點i是二叉樹的根，無雙親結(jié)點；否則，若i>1，則其雙親結(jié)點編號是

i/2

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

abcdefghijkl

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

?

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

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

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

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

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

R?

A?D

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

CERADB

R?

A?D??C?

B?E?樹

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

R?

A?D??C?

B?E??C?

B?E?

R

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

FGRABCDEFGRABCDE(b)加虛線，去連線后

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

二叉樹的根結(jié)點沒有右子樹，只有左子樹；

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