數(shù)據(jù)結(jié)構(gòu)課件：第六章 二叉樹

第六章二叉樹樹及二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲(chǔ)二叉樹的遍歷二叉樹的應(yīng)用樹的基本概念樹定義：樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合（用T表示）。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n>0時(shí)，該集合滿足如下條件：(1)其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。(2)其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m≥0）個(gè)互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，可有零個(gè)或多個(gè)直接后繼。

例如：一棵樹的邏輯結(jié)構(gòu)圖為：ABCDGFEHIJKLM從圖中可以看出它好象一棵倒栽的樹。樹的基本概念（續(xù)）樹的相關(guān)術(shù)語：結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)稱為此結(jié)點(diǎn)的度。葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，即無后繼的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。

分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依此類推。

樹的基本概念（續(xù)）樹的度：樹中所有結(jié)點(diǎn)的度的最大值。樹的深度：樹中所有結(jié)點(diǎn)的層次的最大值。雙親結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接前驅(qū)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。下圖中A是B、C、D的雙親。兄弟結(jié)點(diǎn)：同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。下圖中的結(jié)點(diǎn)B、C、D互為兄弟結(jié)點(diǎn)。

孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。如下圖的B、C、D是A的孩子。

我們常常借助人類家族的術(shù)語，以便于直觀理解結(jié)點(diǎn)間的層次關(guān)系。

ABCDGFEHIJKLM二叉樹的基本概念定義：我們把滿足以下兩個(gè)條件的樹型結(jié)構(gòu)叫做二叉樹（BinaryTree）：（1）每個(gè)結(jié)點(diǎn)的度都不大于2；（2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。下面給出二叉樹的五種基本形態(tài)：(a)空二叉數(shù)(c)只有左子樹的二叉樹(b)只有根結(jié)點(diǎn)的二叉樹(d)左右子樹均非空的二叉樹(e)只有右子樹的二叉樹性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1).性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k≥1).性質(zhì)3：對任意一棵二叉樹T，若終端結(jié)點(diǎn)數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1.二叉樹的性質(zhì)兩種特殊的二叉樹滿二叉樹：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。123456789101112131415滿二叉樹兩種特殊的二叉樹（續(xù)）完全二叉樹：1234567891011121314關(guān)系：滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1到n的位置序號分別與同深度的滿二叉樹的結(jié)點(diǎn)1到n的位置序號一一對應(yīng)，則為完全二叉樹

兩種特殊的二叉樹（續(xù)）滿二叉樹特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)完全二叉樹特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l或l+11231145891213671014151231145891267101234567123456√×√×完全二叉樹(性質(zhì)４)12第二節(jié)二叉樹具有n個(gè)結(jié)點(diǎn)的完全二叉樹,其深度為log2n+1設(shè)k為深度，由二叉樹性質(zhì)２，已知2k-1-1

<n≤2k-1即2k-1≤n<2k即k=log2n+1第６章樹與二叉樹621754389101112完全二叉樹(性質(zhì)５)13第二節(jié)二叉樹在完全二叉樹中，結(jié)點(diǎn)i的雙親為i/2結(jié)點(diǎn)i的左孩子LCHILD(i)=2i結(jié)點(diǎn)i的右孩子RCHILD(i)=2i+1第６章樹與二叉樹6217543891011122i+2i2i+32i+12ii+1i/2二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。一、二叉樹的順序存儲(chǔ)表示二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉樹的存儲(chǔ)結(jié)構(gòu)（續(xù)）1.順序存儲(chǔ)結(jié)構(gòu)：是用一組連續(xù)的存儲(chǔ)單元來存放二叉樹的數(shù)據(jù)元素。ABCDEFGHIJKLABCDEFGHIJKL二叉樹的順序存儲(chǔ)結(jié)構(gòu)從上到下從左到右二叉樹的存儲(chǔ)結(jié)構(gòu)（續(xù)）

對于一般的二叉樹，我們必須按照完全二叉樹的形式來存儲(chǔ)，就會(huì)造成空間的浪費(fèi)。單支樹就是一個(gè)極端情況。ABCDA^B^^^C^^^^^^^D單支樹二叉樹的存儲(chǔ)結(jié)構(gòu)（續(xù)）2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、左孩子域和右孩子域：

LChildDataRChild二叉鏈表DABCEFGABCDEFG二叉樹T二叉鏈表二叉樹遍歷指按一定規(guī)律對二叉樹中的每個(gè)結(jié)點(diǎn)進(jìn)行訪問且僅訪問一次。

先序遍歷過程：①訪問根結(jié)點(diǎn)；②按先序遍歷左子樹；③按先序遍歷右子樹。RChildDataLChildDataLChildLChildRChild中序遍歷過程：①按中序遍歷左子樹；②訪問根結(jié)點(diǎn)；③按中序遍歷右子樹。后序遍歷過程：①按后序遍歷左子樹；②按后序遍歷右子樹；③訪問根結(jié)點(diǎn)遍歷二叉樹如果規(guī)定先左子樹后右子樹，則共有三種組合1.DLR[先序遍歷]2.LDR[中序遍歷]3.LRD[后序遍歷]ＤLR二叉樹遍歷（續(xù)）先序遍歷二叉樹算法：1.若二叉樹為空，則返回；否則：2.訪問根節(jié)點(diǎn)(D)3.先序遍歷左子樹(L)4.先序遍歷右子樹(R)ＤLR二叉樹遍歷（續(xù)）二叉樹遍歷（續(xù)）例：給出下面二叉樹的三種遍歷序列ABCDEFGIH先序遍歷：ABDEHICFG中序遍歷：DBHEIAFCG后序遍歷：DHIEBFGCA先序遍歷二叉樹算法(舉例)：1.若二叉樹為空，則返回；否則：2.訪問根節(jié)點(diǎn)(D)3.先序遍歷左子樹(L)4.先序遍歷右子樹(R)輸出結(jié)果：ABDEGCFADBFCGE二叉樹遍歷（續(xù)）先序遍歷二叉樹算法(C語言實(shí)現(xiàn))：voidPreOrderTraverse(BinTreeT){if(T){cout<<T->data;PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);}}二叉樹遍歷（續(xù)）中序遍歷二叉樹算法：1.若二叉樹為空，則返回；否則：2.中序遍歷左子樹(L)3.訪問根節(jié)點(diǎn)(D)4.中序遍歷右子樹(R)ＤLR二叉樹遍歷（續(xù)）中序遍歷二叉樹算法(舉例)：1.若二叉樹為空，則返回；否則：2.中序遍歷左子樹(L)3.訪問根節(jié)點(diǎn)(D)4.中序遍歷右子樹(R)輸出結(jié)果：DBGEAFCADBFCGE二叉樹遍歷（續(xù)）三、中序遍歷二叉樹算法(C語言實(shí)現(xiàn))：voidInOrderTraverse(BinTreeT){if(T){ InOrderTraverse(T->lChild); cout<<T->data;InOrderTraverse(T->rChild);}}二叉樹遍歷（續(xù)）后序遍歷二叉樹算法：1.若二叉樹為空，則返回；否則：2.后序遍歷左子樹(L)3.后序遍歷右子樹(R)4.訪問根節(jié)點(diǎn)(D)ＤLR二叉樹遍歷（續(xù)）后序遍歷二叉樹算法(舉例)：1.若二叉樹為空，則返回；否則：2.訪問根節(jié)點(diǎn)(D)3.后序遍歷左子樹(L)4.后序遍歷右子樹(R)輸出結(jié)果：DGEBFCAADBFCGE二叉樹遍歷（續(xù)）后序遍歷二叉樹算法(C語言實(shí)現(xiàn))：voidPostOrderTraverse(BinTreeT){if(T){ PostOrderTraverse(T->lChild); PostOrderTraverse(T->rChild); cout<<T->data;}}二叉樹遍歷（續(xù)）什么是線索二叉樹？類似與單向鏈表發(fā)展到雙向鏈表線索二叉樹有什么用途？線索二叉樹一、增加新指針最簡單的方法是在每個(gè)結(jié)點(diǎn)中，增加前驅(qū)(fwd)和后繼(bkwd)指針在做二叉樹遍歷（前、中、后序），將每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼信息添入fwd和bkwd域中fwdlChilddatarChildbkwd線索二叉樹二、利用空指針在有n個(gè)結(jié)點(diǎn)的二叉樹中，必定存在n+1個(gè)空鏈域因?yàn)槊總€(gè)結(jié)點(diǎn)有兩個(gè)鏈域（左、右孩子指針），因此共有2n個(gè)鏈域除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)分支相連，即n-1個(gè)鏈域被使用線索二叉樹（續(xù)）二、利用空指針在結(jié)點(diǎn)中增加兩個(gè)標(biāo)記位（LTag,RTag)LTag=0,lChild域指示結(jié)點(diǎn)的左孩子

LTag=1,lChild域指示結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)RTag=0,rChild域指示結(jié)點(diǎn)的右孩子

RTag=1,rChild域指示結(jié)點(diǎn)的后繼結(jié)點(diǎn)LTaglChilddatarChildRTag線索二叉樹（續(xù)）一、樹的存儲(chǔ)結(jié)構(gòu)1.雙親表示法采用一組連續(xù)的存儲(chǔ)空間ABCDEFG-10001130123456AEBGDFC樹和森林一、樹的存儲(chǔ)結(jié)構(gòu)2.孩子表示法可以采用多重鏈表，即每個(gè)結(jié)點(diǎn)有多個(gè)指針最大缺點(diǎn)是空鏈域太多

[(d-1)n+1個(gè)]AEBGDFC

datachild1child2child3childd樹與森林一、樹的存儲(chǔ)結(jié)構(gòu)2.孩子表示法將每個(gè)結(jié)點(diǎn)的孩子排列起來，用單鏈表表示將每個(gè)結(jié)點(diǎn)排列成一個(gè)線性表AEBGDFCABCDEFG0123456Root123^45^6^樹與森林（續(xù)）一、樹的存儲(chǔ)結(jié)構(gòu)3.孩子兄弟表示法采用二叉鏈表左邊指針指向第一個(gè)孩子，右邊指針指向兄弟AEBGDFC

datafirstChildnextSiblingBCDGFEA樹與森林（續(xù)）二、樹與二叉樹的對應(yīng)關(guān)系樹與二叉樹都可以采用二叉鏈表作存儲(chǔ)結(jié)構(gòu)任意給定一棵樹，可以找到一個(gè)唯一的二叉樹(沒有右子樹)AEBGDFCBCDGFEAABGDFCE樹對應(yīng)的二叉樹樹與森林（續(xù)）三、森林與二叉樹的對應(yīng)關(guān)系如果把森林中的第二棵樹的根結(jié)點(diǎn)看作是第一棵樹的根結(jié)點(diǎn)的兄弟，則可找到一個(gè)唯一的二叉樹與之對應(yīng)三棵樹的森林對應(yīng)的二叉樹T1T2T3AFHBCDGIJEKABCEDHIKFGJ樹與森林（續(xù)）森林轉(zhuǎn)為二叉樹(算法)如果F={T1,T2,…,Tn}是森林，B＝（root，LB，RB）是二叉樹（1）若F為空，即n＝0，則B是空樹；（2）若F非空，則B的根root即為F中第一棵樹T1的根root（T1）；B的左子樹LB是從T1中根結(jié)點(diǎn)的子樹森林F1={T11,T12,…,T1m}轉(zhuǎn)換而成的二叉樹；B的右子樹RB是從F2={T2,…,Tn}轉(zhuǎn)換而成的二叉樹；樹與森林（續(xù)）二叉樹轉(zhuǎn)為森林(算法)如果F={T1,T2,…,Tn}是森林，B＝（root，LB，RB）是二叉樹（1）若B為空，則F是空；（2）若B非空，則F中第一棵樹T1的根root（T1）即為B的根root；T1中根結(jié)點(diǎn)的子樹森林F1是由B的左子樹LB轉(zhuǎn)換而成的森林；F中除T1外，其他樹組成的森林F2={T2,…,Tn}是從B的右子樹RB轉(zhuǎn)換而成的森林；樹與森林（續(xù)）四、樹的遍歷對樹的遍歷主要有兩種：1.先根（次序）遍歷2.后根（次序）遍歷AEBGDFC樹與森林（續(xù)）四、樹的遍歷1.先根（次序）遍歷當(dāng)樹非空時(shí)訪問根結(jié)點(diǎn)依次先根遍歷根的各棵子樹輸出結(jié)果：ABEFCDGAEBGDFC樹與森林（續(xù)）四、樹的遍歷2.后根（次序）遍歷當(dāng)樹非空時(shí)依次后根遍歷根的各棵子樹訪問根結(jié)點(diǎn)輸出結(jié)果：EFBCGDAAEBGDFC樹與森林（續(xù)）一、最優(yōu)二叉樹路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑路徑長度：路徑上的分支數(shù)目樹的路徑長度：從樹根到每個(gè)結(jié)點(diǎn)的路徑長度之和右樹路徑長度為：

2*1+3*2+1*3=11ADBFCGE赫夫曼樹及其應(yīng)用（續(xù)）一、最優(yōu)二叉樹帶權(quán)路徑長度：從結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積樹的帶權(quán)路徑長度(WPL)：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和WPL=2*5+3*3+2*4=27ADBFCGE5３４赫夫曼樹及其應(yīng)用（續(xù)）一、最優(yōu)二叉樹最優(yōu)二叉樹：假設(shè)二叉樹有n個(gè)葉子，其每個(gè)葉子結(jié)點(diǎn)帶權(quán)wi，則帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹赫夫曼(Huffman)樹就是一棵最優(yōu)二叉樹WPL=1*5+2*3+2*4=19ADBCE5３４赫夫曼樹及其應(yīng)用（續(xù)）二、Huffman樹(構(gòu)造)在Huffman樹中，權(quán)值最大的結(jié)點(diǎn)離根最近權(quán)值最小的結(jié)點(diǎn)離根最遠(yuǎn)ADBCE5３４赫夫曼樹及其應(yīng)用（續(xù)）二、Huffman樹(算法)1.根據(jù)給定的n個(gè)權(quán)值(w1,w2,…,wn)構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹Ti中只有一個(gè)帶樹為Ti的根結(jié)點(diǎn)2.在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置其根結(jié)點(diǎn)的權(quán)值為其左右子樹權(quán)值之和3.在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中4.重復(fù)2,3，直到F只含一棵樹為止赫夫曼樹及其應(yīng)用（續(xù)）二、Huffman樹(舉例)F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}7524初始合并{2}{4}75246F:{18}1175246合并{5}{6}5合并{7}{11}27461118赫夫曼樹及其應(yīng)用（續(xù)）三、Huffman編碼設(shè)給出一段報(bào)文：GOOD_GOOD_GOODGODG字符集合是{O,G,_,D}，各個(gè)字符出現(xiàn)的頻度(次數(shù))是W＝{7,5,2,4}。若給每個(gè)字符以等長編