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

只有根結點(b)

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

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

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

其中2k-1≦

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

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

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

整數。x

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

㏒2n

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

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

i/2

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

abcdefghijkl

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

?

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

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

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

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

FGRABCDE(c)孩子兄弟存儲結構

R?

A?D

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

CERADB

R?

A?D??C?

B?E?樹

RABCDE對應關系

R?

A?D??C?

B?E??C?

B?E?

R

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

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

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

二叉樹的根結點沒有右子樹，只有左子樹；

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