數(shù)據(jù)結(jié)構(gòu)樹和二叉樹文稿演示課件_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)樹和二叉樹文稿演示課件_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)樹和二叉樹文稿演示課件_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)樹和二叉樹文稿演示課件_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)樹和二叉樹文稿演示課件_第5頁(yè)
已閱讀5頁(yè),還剩96頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、數(shù)據(jù)結(jié)構(gòu)樹和二叉樹文稿演示數(shù)據(jù)結(jié)構(gòu)PPT樹和二叉樹6.1 樹的定義和基本術(shù)語(yǔ) 什么是樹?樹是由 n (n 0) 個(gè)結(jié)點(diǎn)的有限集合。如果 n = 0,稱為空樹;如果 n 0,則 有且僅有一個(gè)特定的稱之為根(Root)的結(jié)點(diǎn),它只有直接后繼,但沒有直接前驅(qū); 當(dāng)n 1,除根以外的其它結(jié)點(diǎn)劃分為 m (m 0) 個(gè)互不相交的有限集 T1, T2 , Tm,其中每個(gè)集合本身又是一棵樹,并且稱為根的子樹(SubTree)。T = A,B,C,D,E,F(xiàn),G,H,I,J,K,L,MA是根,其余結(jié)點(diǎn)可以劃分為3個(gè)互不相交的集合:T1= B,E,F(xiàn),K,L T2 = C,G T3 = D,H,I,J,M 這些

2、集合中的每一集合都本身又是一棵樹,它們是A的子樹。對(duì)于T1,B是根,其余結(jié)點(diǎn)可以劃分為2個(gè)互不相交的集合:T11 = E,K,L T12 = F T11,T12是B的子樹。HBAJFEDKLCMIG 樹的示例1. 樹中只有根結(jié)點(diǎn)沒有前趨;2. 除根外,其余結(jié)點(diǎn)都有且僅一個(gè)前趨;3. 樹的結(jié)點(diǎn),可以有零個(gè)或多個(gè)后繼;4. 除根外的其它結(jié)點(diǎn),都存在唯一條從根到該結(jié)點(diǎn)的路徑;5. 樹是一種分支結(jié)構(gòu)。HBAJFEDKLCMIG 樹的邏輯結(jié)構(gòu)特點(diǎn) 樹可表示具有分支結(jié)構(gòu)關(guān)系的對(duì)象例1. 家族族譜 設(shè)某家庭有13個(gè)成員A、B、C、D、E、F、G、H、I、J、K、L、M,他們之間的關(guān)系可如圖所示的樹表示。例2

3、. 單位行政機(jī)構(gòu)的組織關(guān)系HBAJFEDKLCMIG 樹的應(yīng)用 樹是常用的數(shù)據(jù)組織形式 有些應(yīng)用中數(shù)據(jù)元素之間并不存在分支結(jié)構(gòu)關(guān)系,但是為了便于管理和使用數(shù)據(jù),將它們用樹的形式來組織。例3. 計(jì)算機(jī)的文件系統(tǒng) 不論是DOS文件系統(tǒng)還是window文件系統(tǒng),所有的文件是用樹的形式來組織的。文件夾1文件夾2文件1文件2文件夾11文件夾11文件11文件12C 樹的應(yīng)用樹的結(jié)點(diǎn):包含一個(gè)數(shù)據(jù)元素的內(nèi)容及若干指向子樹的分支。孩子結(jié)點(diǎn):結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子;如E是B的孩子。雙親結(jié)點(diǎn):B結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子,則A結(jié)點(diǎn)是B結(jié)點(diǎn)的雙親;如B是E的雙親。兄弟結(jié)點(diǎn):同一雙親的孩子結(jié)點(diǎn);如H、I、J互為兄弟。

4、堂兄結(jié)點(diǎn):同一層上結(jié)點(diǎn);如G與E、F、H、I、J互為堂兄。祖先結(jié)點(diǎn):結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn); 如H的祖先為A、D。子孫結(jié)點(diǎn):以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫;如A的子孫為B、C、D、E、F、G、H、I、J、K、L、M。HBAJFEDKLCMIG 基本術(shù)語(yǔ)結(jié)點(diǎn)的度:結(jié)點(diǎn)子樹的個(gè)數(shù);如D的度為3。葉子結(jié)點(diǎn):也叫終端結(jié)點(diǎn),是度為0的結(jié)點(diǎn);如K、L、F、G、M、I、J。分支結(jié)點(diǎn):度不為0的結(jié)點(diǎn);如A、B、C、D結(jié)點(diǎn)層次:根結(jié)點(diǎn)的層定義為1,根的孩子為第二層結(jié)點(diǎn),依此類推。樹的高度:樹中結(jié)點(diǎn)的最大層次;如圖所示樹的高度為4。樹的度: 樹中各結(jié)點(diǎn)的度的最大值;如圖所示樹

5、的度為3。森林:m(m=0)棵互不相交的樹的集合;HBAJFEDKLCMIG 基本術(shù)語(yǔ) 線性結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素 (無前驅(qū)); 最后一個(gè)數(shù)據(jù)元素(無后繼); 其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)。 樹型結(jié)構(gòu) 根結(jié)點(diǎn)(無前驅(qū)); 多個(gè)葉子結(jié)點(diǎn) (無后繼); 其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)。 樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)對(duì)比6.2.1 二叉樹的定義 或?yàn)榭諛?,或由根及至多兩棵互不相交的左子樹、右子樹?gòu)成(即不存在度大于2的結(jié)點(diǎn)),并且左、右子樹本身也是二叉樹。說明:1. 二叉樹中每個(gè)結(jié)點(diǎn)最多有兩棵子樹,二叉樹每個(gè)結(jié)點(diǎn)度小于等于2;2. 左、右子樹不能顛倒有序樹;3. 二叉樹是遞歸結(jié)構(gòu),在二叉樹的

6、定義中又用到了二叉樹的概念。BADCFEG6.2 二叉樹 (a) (b) (c) (d) (e) (a) 空樹 (b) 只含根結(jié)點(diǎn) (c) 右子樹為空樹 (d) 左右子樹均不為空樹 (e) 左子樹為空樹LLRR 二叉樹的形態(tài)性質(zhì)1 在二叉樹的第 i 層上至多有 2i - 1個(gè)結(jié)點(diǎn)。(i 1) 證明用歸納法證明:當(dāng)i=1時(shí),只有根結(jié)點(diǎn),2 i-1=2 0=1。假設(shè)對(duì)所有j, 1ji,命題成立,即第j層上至多有2 j-1 個(gè)結(jié)點(diǎn)。由歸納假設(shè)第i-1 層上至多有 2i -2個(gè)結(jié)點(diǎn)。由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為2,故在第i層上的最大結(jié)點(diǎn)數(shù)為第i-1層上的最大結(jié)點(diǎn)數(shù)的2倍,即22i -2= 2 i-1

7、。6.2.2 二叉樹的性質(zhì)性質(zhì)2 深度為 k 的二叉樹至多有 2 k-1個(gè)結(jié)點(diǎn)(k 1)。證明:由性質(zhì)1可見,深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為 20 + 21 + + 2 k-1 = 2 k-16.2.2 二叉樹的性質(zhì)性質(zhì)3 對(duì)任何一棵二叉樹T,如果其葉結(jié)點(diǎn)數(shù)為 n0,度為2的結(jié)點(diǎn)數(shù)為 n2,則n0n21。證明:設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為n1,二叉樹中總結(jié)點(diǎn)數(shù)為: nn0n1n2 二叉樹中的分支數(shù),除根結(jié)點(diǎn)外,其余結(jié)點(diǎn)都有一個(gè)進(jìn)入分支,設(shè)B為二叉樹中的分支總數(shù), 則有:nB1。由于這些分支都是由度為1和2的結(jié)點(diǎn)射出的,所以有: Bn1+2 n2 ; nB1n12n21得到:n0n216.2.2

8、二叉樹的性質(zhì)滿二叉樹:深度為k的二叉樹,有2k-1個(gè)結(jié)點(diǎn)則稱為滿二叉樹;完全二叉樹:如果深度為k、由n個(gè)結(jié)點(diǎn)的二叉樹中個(gè)結(jié)點(diǎn)能夠與深度為k的順序編號(hào)的滿二叉樹從1到n標(biāo)號(hào)的結(jié)點(diǎn)相對(duì)應(yīng),則稱為完全二叉樹。完全二叉樹的特點(diǎn)是: 1. 所有的葉結(jié)點(diǎn)都出現(xiàn)在第k層或k1層。 2. 對(duì)任一結(jié)點(diǎn),如果其右子樹的最大層次為l ,則其左子樹的最大層次為 l 或 l 1。 兩種特殊的二叉樹6217543891011131415126217543891011122154367216543非完全二叉樹完全二叉樹滿二叉樹 兩種特殊的二叉樹性質(zhì) 4 :具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1。證明:設(shè)完全

9、二叉樹的深度為 k,則根據(jù)性質(zhì)2和完全二叉樹的定義有2k-1 - 1 n 2k- 1或 2k-1 n 2k取對(duì)數(shù) k-1 1,則其雙親是結(jié)點(diǎn) i/2 。 2. 如果2in,則結(jié)點(diǎn)i為葉子結(jié)點(diǎn),無左孩子;否則,其左孩子是結(jié)點(diǎn)2i。 3. 如果2i1n,則結(jié)點(diǎn)i無右孩子;否則,其右孩子是結(jié)點(diǎn)2i1。6.2.2 二叉樹的性質(zhì)證明:此性質(zhì)可采用數(shù)學(xué)歸納法證明。因?yàn)?與2、3是相對(duì)應(yīng)的,所以只需證明2和3。 當(dāng) i=1時(shí) ,根據(jù)結(jié)點(diǎn)編號(hào)方法可知,根的左、右孩子編號(hào)分別是2和3,結(jié)論成立。 假定i-1時(shí)結(jié)論成立,即結(jié)點(diǎn)i-1的左右孩子編號(hào)滿足: LCHILD(i-1)=2(i-1); RCHILD(i-1

10、)=2(i-1)+1 通過完全二叉樹可知,結(jié)點(diǎn) i 或者與結(jié)點(diǎn)i-1同層且緊靠其右,或者結(jié)點(diǎn)i-1在某層最右端,而結(jié)點(diǎn)i在其下一層最左端。但是,無論如何,結(jié)點(diǎn)i的左孩子的編號(hào)都是緊接著結(jié)點(diǎn)i-1的右孩子的編號(hào),故: LCHILD(i)=RCHILD(i-1)+1=2i; RCHILD(i)=LCHILD(i)+1=2i+1命題成立。 6.2.2 二叉樹的性質(zhì)分析:根據(jù)完全二叉樹的結(jié)構(gòu)和編號(hào)規(guī)則,在i的左孩子前面的兩個(gè)結(jié)點(diǎn)是結(jié)點(diǎn)i-1的左、右孩子,由歸納假設(shè)有:結(jié)點(diǎn)i-1的左孩子為2(i-1),右孩子為2(i-1)+1。.i與i+1同層.i-12(i-1)2(i-1)+1i2i2i+1.i與i+

11、1不同層6.2.2 二叉樹的性質(zhì)i2i2i+1i-12i-22i-1最后證明結(jié)論1。 當(dāng)i=1時(shí),顯然根結(jié)點(diǎn)無雙親;當(dāng)i1時(shí),結(jié)點(diǎn)i可能是其雙親x的左孩子,也可能是右孩子,若是左孩子,由結(jié)論2知,x的左孩子應(yīng)為2x,即2x=i,x=i/2;若是右孩子,由結(jié)論3知,x的右孩子應(yīng)為2x+1,即2x+1=i,x=(i-1)/2。故 i的雙親為i/2 證畢。6.2.2 二叉樹的性質(zhì) 順序存儲(chǔ)結(jié)構(gòu) 所謂順序存儲(chǔ)結(jié)構(gòu),就是用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素,結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。 二叉樹中結(jié)點(diǎn)之間的關(guān)系就是雙親結(jié)點(diǎn)與左右孩子結(jié)點(diǎn)間的關(guān)系。因此,必須把二叉樹的所有結(jié)點(diǎn)安

12、排成為一個(gè)恰當(dāng)?shù)男蛄?。具體定義如下: #define MAX-TREE-SIZE 100 TElemType SqBiTreeMAX-TREE-SIZE; 6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 通常是按照二叉樹結(jié)點(diǎn)從上至下、從左到右的順序存儲(chǔ),但這樣結(jié)點(diǎn)在存儲(chǔ)位置上的前驅(qū)后繼關(guān)系并不一定就是它們?cè)谶壿嬌系泥徑雨P(guān)系。依據(jù)二叉樹的性質(zhì),完全二叉樹和滿二叉樹采用順序存儲(chǔ)比較合適,樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系,這樣既能夠最大可能地節(jié)省存儲(chǔ)空間,又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置,以及結(jié)點(diǎn)之間的關(guān)系。 二叉樹的順序存儲(chǔ)結(jié)構(gòu)FBAGEDCHIJKL例如: bt3的雙親為3/2=

13、1,即在bt1中; 其左孩子在bt2i=bt6中; 其右孩子在bt2i+1=bt7中。如何反映結(jié)點(diǎn)之間的邏輯關(guān)系?A1B2C3D4E5F6G7H8I9J10K11L12 完全二叉樹的順序表示 一般二叉樹也按完全二叉樹形式存儲(chǔ),只有增添一些并不存在的空結(jié)點(diǎn)(用表示, 表示該處沒有元素存在,僅僅為了好理解),使之成為一棵完全二叉樹的形式,然后再用一維數(shù)組順序存儲(chǔ)。A1B2C3D45E6F7G8H910111213I14J15EBAFDCGHIJ例如對(duì)于B結(jié)點(diǎn)而言: bt2的雙親為1/2=1,即在bt1中(為A); 其左孩子在bt2i=bt4中(為D); 其右孩子在bt2i+1=bt5中(為 )。

14、一般二叉樹的順序表示 這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹,既不浪費(fèi)存儲(chǔ)空間,又能很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)的雙親和左右孩子的存放位置,但對(duì)一般二叉樹,可能造成存儲(chǔ)空間的浪費(fèi)。例如,深度為k,且只有k個(gè)結(jié)點(diǎn)的右單支樹(每個(gè)非葉結(jié)點(diǎn)只有右孩子),也需2k-1個(gè)單元,即有(2k-1)- k個(gè)單元被浪費(fèi)。12k 順序存儲(chǔ)的優(yōu)缺點(diǎn) 所謂鏈?zhǔn)酱鎯?chǔ)是指,用鏈表來表示一棵二叉樹,即用鏈來指示著元素的邏輯關(guān)系。通常采用二叉鏈表來存儲(chǔ)。 鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成,除了數(shù)據(jù)域外,還有兩個(gè)指針域,分別用來給出該結(jié)點(diǎn)左右孩子所在的結(jié)點(diǎn)的存儲(chǔ)地址。其定義如下: typedef struct BiTNode TElemT

15、ype data; struct BiTNode *lchild, *rchild; BiTNode,*BiTree; 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D A B C E F Tlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)BADCEF 二叉鏈表 A B C D E F G三叉鏈表圖示BACDEFG 三叉鏈表lchilddata結(jié)點(diǎn)結(jié)構(gòu)parentrchild6.3 遍歷二叉樹和線索二叉樹6.3.1 遍歷二叉樹定義:所謂遍歷二叉樹,就是遵從某種次序,訪問二叉樹中的所有結(jié)點(diǎn),使得每個(gè)結(jié)點(diǎn)僅被訪問一次。 這里所提的“訪問”的含義很廣,可以是查詢、修改、輸出某元素的值,以及對(duì)元素作某種運(yùn)算等等。但要求這種訪問不破壞它原來的

16、數(shù)據(jù)結(jié)構(gòu)。遍歷一個(gè)線性結(jié)構(gòu)很簡(jiǎn)單,只須從開始結(jié)點(diǎn)出發(fā),順序掃描每個(gè)結(jié)點(diǎn)即可。但對(duì)二叉樹這樣的非線性結(jié)構(gòu),每個(gè)結(jié)點(diǎn)可能有兩個(gè)后繼結(jié)點(diǎn),因此需要尋找一種規(guī)律來系統(tǒng)訪問樹中的各結(jié)點(diǎn)。如何訪問二叉樹的每個(gè)結(jié)點(diǎn)且每個(gè)結(jié)點(diǎn)僅被訪問一次? 由于二叉樹的定義是遞歸的,它是由三個(gè)基本單元組成,即根結(jié)點(diǎn)、左子樹和右子樹。因此,遍歷一棵非空二叉樹的問題可以分解為三個(gè)子問題:訪問根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹,只要依次遍歷這三部分,就可以遍歷整個(gè)二叉樹。 由于實(shí)際問題一般都是要求左子樹較右子樹先遍歷,分別稱為先序遍歷、中序遍歷和后序遍歷。 令L,R,D分別代表二叉樹的左子樹、右子樹、根結(jié)點(diǎn),則有DLR、LDR、LRD

17、三種遍歷規(guī)則。 遞歸實(shí)現(xiàn)方法若二叉樹非空,則: 1. 訪問根結(jié)點(diǎn) 2. 先序遍歷左子樹 3. 先序遍歷右子樹BADCD L RAD L RD L RBDCD L R得到的序列為:A B D C 先序遍歷二叉樹Status PreOrderTraverse( BiTree T ) /采用二叉鏈表存貯二叉樹 if (T) /若二叉樹不為空 Visit(T-data); /訪問根結(jié)點(diǎn) PreOrderTraverse(T-lchild); /先序遍歷T的左子樹 PreOrderTraverse(T-rchild); /先序遍歷T的右子樹 /PreOrderTraverse 先序遍歷二叉樹算法實(shí)現(xiàn)vi

18、od pre (bint T) if ( T ) visite(T-data); pre (T-lchild) ; pre (T-rchild); 先序遍歷二叉樹算法實(shí)現(xiàn)BADC主程序Pre(T)TAvisite(A);pre(T L);TBvisite(B);pre(T L);T返回pre(T R);TDvisite(D);pre(T L);T返回pre(T R);T返回pre(T R);TCvisite(C);pre(T L);T返回pre(T R);T返回先序序列:A B D C若二叉樹非空,則: 1. 中序遍歷左子樹 2. 訪問根結(jié)點(diǎn) 3. 中序遍歷右子樹BADCL D RBL D R

19、L D RADCL D R得到的序列為: B D A C 中序遍歷二叉樹若二叉樹非空,則: 1. 后序遍歷左子樹 2. 訪問根結(jié)點(diǎn) 3. 后序遍歷右子樹BADC L R DL R DL R DADCL R DB得到的序列為: D B C A 后序遍歷二叉樹*-bca 這一路線正是從根結(jié)點(diǎn)開始沿左子樹深入下去,當(dāng)深入到最左端,無法再深入下去時(shí),則返回,再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹,再進(jìn)行如此的深入和返回,直到最后從根結(jié)點(diǎn)的右子樹返回到根結(jié)點(diǎn)為止。先序遍歷是在深入時(shí)遇到結(jié)點(diǎn)就訪問,中序遍歷是在從左子樹返回時(shí)遇到結(jié)點(diǎn)訪問,后序遍歷是在從右子樹返回時(shí)遇到結(jié)點(diǎn)訪問。 在這一過程中,返回結(jié)點(diǎn)的順序

20、與深入結(jié)點(diǎn)的順序相反,即后深入先返回,正好符合棧結(jié)構(gòu)后進(jìn)先出的特點(diǎn)。因此,可以用棧來幫助實(shí)現(xiàn)這一遍歷路線。 三種遍歷過程示意圖例-*abc 先序遍歷:從二叉樹根結(jié)點(diǎn)開始,沿左子樹一直走到末端(左子樹為空)為止,在走的過程中,訪問所遇結(jié)點(diǎn),并依次把所遇結(jié)點(diǎn)進(jìn)棧,當(dāng)左子樹為空時(shí),從棧頂退出某結(jié)點(diǎn),并將指針指向該結(jié)點(diǎn)的右子樹。如此重復(fù),直到棧為空或指針為空止。 中序遍歷:從二叉樹根結(jié)點(diǎn)開始,沿左子樹一直走到末端(左子樹為空)為止,在走的過程中,把依次遇到的結(jié)點(diǎn)進(jìn)棧,待左子樹為空時(shí),從棧中退出結(jié)點(diǎn)并訪問,然后再轉(zhuǎn)向它的右子樹。如此重復(fù),直到??栈蛑羔槥榭罩埂?非遞歸實(shí)現(xiàn)方法status InOrder

21、Traverse(BiTree T) InitStack(S); Push(S,T); /根結(jié)點(diǎn)進(jìn)棧 while(!StackEmpty(S) while(GetTop(S,p) & p) Push(S,p-lchild); Pop(S,p); /空指針退棧 if (!StackEmpty(S) Pop(S,p); Visit(p-data); Push(S,p-rchild); return OK; 中序遍歷的非遞歸算法 中序遍歷的非遞歸算法演示ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2) 中序遍歷的非遞歸算法演示ABCDEFGpiP-AP-BP-C(3)p=NULLA

22、BCDEFGiP-AP-B訪問:C(4) 中序遍歷的非遞歸算法演示pABCDEFGiP-A訪問:C B(5)ABCDEFGiP-AP-D訪問:C Bp(6) 中序遍歷的非遞歸算法演示ABCDEFGiP-AP-DP-E訪問:C Bp(7)ABCDEFGiP-AP-D訪問:C B Ep(8) 中序遍歷的非遞歸算法演示ABCDEFGiP-AP-DP-G訪問:C B EP=NULL(9)ABCDEFGiP-AP-D訪問:C B E Gp(10) 中序遍歷的非遞歸算法演示ABCDEFGiP-A訪問:C B E G Dp(11)ABCDEFGiP-AP-F訪問:C B E G Dp(12) 中序遍歷的非遞

23、歸算法演示ABCDEFGiP-A訪問:C B E G D Fp=NULL(13)ABCDEFGi訪問:C B E G D F Ap(14) 中序遍歷的非遞歸算法演示ABCDEFGi訪問:C B E G D F Ap=NULL(15) 后序遍歷:利用棧來實(shí)現(xiàn)二叉樹的后序遍歷要比先序和中序遍歷復(fù)雜得多,在后序遍歷中,當(dāng)搜索指針指向某一個(gè)結(jié)點(diǎn)時(shí),不能馬上進(jìn)行訪問,而先要遍歷左子樹,所以此結(jié)點(diǎn)應(yīng)先進(jìn)棧保存,當(dāng)遍歷完它的左子樹后,再次回到該結(jié)點(diǎn),還不能訪問它,還需先遍歷其右子樹,所以該結(jié)點(diǎn)還必須再次進(jìn)棧,只有等它的右子樹遍歷完后,再次退棧時(shí),才能訪問該結(jié)點(diǎn)。為了區(qū)分同一結(jié)點(diǎn)的兩次進(jìn)棧,引入一個(gè)棧次數(shù)的標(biāo)

24、志,元素第一次進(jìn)棧標(biāo)志為1,第二次進(jìn)標(biāo)志為2,當(dāng)退出的元素標(biāo)志為2時(shí),訪問結(jié)點(diǎn)。 非遞歸實(shí)現(xiàn)方法void leaf( BiTree T ) /采用二叉鏈表存貯二叉樹,n為全局變量,用于累加二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù),本算法在先序遍歷二叉樹的過程中,統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù),初始化n=0if( T ) if( T-lchild=NULL&T-rchild=NULL) n+=1; /若T所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)則計(jì)數(shù) leaf(T-lchild); leaf(T-rchild); /if /leaf例1 編寫求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)的算法void leaf( BiTree T ) If (T) if( T-lchil

25、d=NULL&T-rchild=NULL) n+=1; leaf(T-lchild); leaf(T-rchild); /if /leafStatus PreOrderTraverse( BiTree T ) if (T) Visit(T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); /PreOrderTraverse訪問結(jié)點(diǎn)時(shí)統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)訪問結(jié)點(diǎn)時(shí)調(diào)用visit( )比較先序遍歷和計(jì)算葉子結(jié)點(diǎn)算法相同點(diǎn)和不同點(diǎn) 分析:本算法要借用隊(duì)列來完成,其基本思想是,若二叉樹非空,先將根結(jié)點(diǎn)進(jìn)隊(duì)列。然后進(jìn)入循環(huán):只要隊(duì)

26、列不空,就出隊(duì)列,遍歷該結(jié)點(diǎn),然后判斷出隊(duì)列的結(jié)點(diǎn)是否有左孩子和右孩子,如有就讓左、右孩子進(jìn)隊(duì)列。 例2 按層次遍歷二叉樹的算法void layorder (BiTree T) InitQueue (Q) /隊(duì)列初始化 if(T!=NULL) EnQueue (Q, T); /入隊(duì)列 while (not QueueEmpty (Q) ) /若隊(duì)列非空 DeQueue (Q, p) ; /出隊(duì) visite( p-data); if (p-lchild!=NULL) EnQueue (Q, p-lchild); /入隊(duì)列 if (p-rchild!=NULL) EnQueue (Q, p-rc

27、hild); /入隊(duì)列 例2 按層次遍歷二叉樹的算法輸入:二叉樹的先序序列結(jié)果:二叉樹的二叉鏈表問題:遍歷操作訪問二叉樹的每個(gè)結(jié)點(diǎn),而且每個(gè)結(jié)點(diǎn)僅被訪問一次。是否可利用遍歷,建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接?基本思想:輸入在空子樹處添加字符的二叉樹的按先序遍歷的順序,建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)鏈接。BADCEF在空子樹處添加的二叉樹的先序序列:A B D F E C 例3 建立二叉鏈表Status CreateBiTree( BiTree &T ) /輸入(在空子樹處添加字符的二叉樹的)先序序列(設(shè)元素均為字符) scanf ( &ch ); if ( ch= = ) T=

28、NULL; /若ch= = 則表示空子樹 else if (! (T=( BiTNode * )malloc( sizeof( BiTNode ) ) ) ) exit(OVERFLOW); T-data= ch; /建立(根)結(jié)點(diǎn) CreateBiTree(T-lchild); /遞歸構(gòu)造左子樹鏈表 CreateBiTree(T-rchild); /遞歸構(gòu)造右子樹鏈表 return OK; /CreateBiTree 建立二叉鏈表算法 建立二叉鏈表算法BACDA B C D ABCDATBCD分析:由先序序列和中序序列的定義可知,先序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn),而在中序序列中,根結(jié)點(diǎn)剛好是左

29、、右子樹的分界點(diǎn),因此,可按如下方法建立二叉樹: 1. 用先序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn); 2. 在中序序列中查找根結(jié)點(diǎn)的位置,并以此為界將中序序列劃分為左、右兩個(gè)序列(左、右子樹); 3. 根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù),將先序序列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列,它們分別是左、右子樹的先序序列; 4. 對(duì)左、右子樹的先序序列和中序序列遞歸地實(shí)施同樣方法,直到所得左、右子樹為空。例4 由二叉樹先序和中序序列建立一個(gè)唯一二叉樹 如一棵二叉樹的先序序列為ABDGHCEFI,中序序列為GDHBAECIF ,試建立該二叉樹。構(gòu)造過程:由先序可知A為根結(jié)點(diǎn),再根據(jù)中序序列知:由GDHB是左

30、子樹,ECIF是右子樹。 A為根結(jié)點(diǎn)A BDGH CEFIGDHB A ECIF B為左子樹的根結(jié)點(diǎn)B DGHGDH B 一直進(jìn)行下去AG,D,H,B組成左子樹E,C,I,F組成右子樹 示例分析a b c d e f gc b d a e g faab bccddeeffggabcdefg先序序列中序序列遍歷是二叉樹最基本最常用的操作。1. 對(duì)二叉樹所有結(jié)點(diǎn)做某種處理可在遍歷過程中實(shí)現(xiàn);2. 查找二叉樹某個(gè)結(jié)點(diǎn),可通過遍歷實(shí)現(xiàn);與線性表相比,對(duì)二叉樹的遍歷存在如下問題:1. 遍歷算法要復(fù)雜的多,費(fèi)時(shí)的多;2. 為查找二叉樹中某結(jié)點(diǎn)在某種遍歷下的后繼,必須從根開始遍歷,直到找到該結(jié)點(diǎn)及后繼; 如

31、果能將二叉樹線性化,就可以減化遍歷算法,提高遍歷速度。6.3.2 線索二叉樹定義:當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí),只能找到結(jié)點(diǎn)的左右孩子的信息,而不能直接得到結(jié)點(diǎn)的任一序列的前驅(qū)與后繼信息,這種信息只有在遍歷的動(dòng)態(tài)過程中才能得到,為了能保存所需的信息,可增加標(biāo)志域。 0 lchild 域指示結(jié)點(diǎn)的左孩子 1 lchild 域指示結(jié)點(diǎn)的前驅(qū) 0 rchild 域指示結(jié)點(diǎn)的右孩子 1 rchild 域指示結(jié)點(diǎn)的后繼 以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu),叫做線索鏈表,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線索。加上線索的二叉樹稱之為線索二叉樹。LTag=RTag= 一、線索二叉樹定義 利用現(xiàn)有的空指

32、針域 ,每個(gè)n個(gè)結(jié)點(diǎn)的二叉鏈表,有n+1個(gè)空指針域,故可利用這些的空指針域存放結(jié)點(diǎn)的前趨和后繼指針。(n個(gè)結(jié)點(diǎn)共有2n個(gè)鏈域,而每個(gè)結(jié)點(diǎn)(除根結(jié)點(diǎn)外)都有一個(gè)分支指向,則共有n-1個(gè)分支,其中每個(gè)分支占有一個(gè)鏈域,所以空鏈域?yàn)?n -(n-1)=n+1。) 若結(jié)點(diǎn)有左子樹,則左指針lchild指示其左孩子(LTag=0);否則,令左指針指示其前驅(qū)(LTag=1); 若結(jié)點(diǎn)有右子樹,則右指針rchild指示其右孩子(RTag=0);否則,令右指針指示其后繼(RTag=1)。 二、如何保存遍歷過程中得到的信息?typedef enum PointerTeg Link, Thread ; / Lin

33、k=0:指針,Thread=1:線索typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerTeg LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree; 三、線索鏈表的類型描述lchildLTagdataRTagrchild(以中序遍歷為例) 查找任意結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 如果該結(jié)點(diǎn)的左標(biāo)志為1,那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn);如果該結(jié)點(diǎn)的左標(biāo)志為0,表明該結(jié)點(diǎn)有左孩子,根據(jù)中序遍歷的定義,它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子為根結(jié)點(diǎn)的子樹的最

34、右結(jié)點(diǎn),即沿著其左子樹的右指針鏈向下查找,當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時(shí),它就是所要找的前驅(qū)結(jié)點(diǎn)。中序線索二叉樹中序:DBGJEACHLKFI 四、 如何找結(jié)點(diǎn)的前驅(qū)和后繼BACEFDGJHIKL中序線索二叉樹中序:DBGJEACHLKFI 四、如何找結(jié)點(diǎn)的前驅(qū)和后繼 (續(xù))(以中序遍歷為例) 查找任意結(jié)點(diǎn)的后繼結(jié)點(diǎn) 對(duì)任意結(jié)點(diǎn)p,若右標(biāo)志為1 ,則rchild指向該結(jié)點(diǎn)的后繼;若右標(biāo)志為0 ,則rchild指向該結(jié)點(diǎn)的右孩子,此時(shí),應(yīng)從右孩子開始,沿左指針前進(jìn),直到找到?jīng)]有左孩子的結(jié)點(diǎn)s(Ltag=1),則s就是p的后繼,即后繼是中序遍歷右子樹時(shí),訪問的第一個(gè)結(jié)點(diǎn)。BACEFDGJHIKL 按不同的

35、方式遍歷二叉樹所得到的線索二叉樹是不相同的。BADCE 五、遍歷線索二叉樹 A B D C ET先序序列:ABCDE先序線索二叉樹0000111111 A B D C ET中序序列:BCAED中序線索二叉樹0000111111 A B D C ET后序序列:CBEDA后序線索二叉樹0000111111BADCE A B D C ET0000111111 01中序序列:BCAED中序線索二叉樹 五、遍歷線索二叉樹 (續(xù)) 帶頭結(jié)點(diǎn)的線索二叉樹 在存儲(chǔ)線索二叉樹時(shí)往往增設(shè)一頭結(jié)點(diǎn),其數(shù)據(jù)域不存放信息,其左指針域指向二叉樹的根結(jié)點(diǎn),右指針域指向某種遍歷時(shí)訪問的最后一個(gè)結(jié)點(diǎn)。而原二叉樹在某序遍歷下的第

36、一個(gè)結(jié)點(diǎn)的前驅(qū)線索和最后一個(gè)結(jié)點(diǎn)的后繼線索都指向該頭結(jié)點(diǎn)。注:可從第一個(gè)結(jié)點(diǎn)起順后繼進(jìn)行遍歷,也可以從最后一個(gè)結(jié)點(diǎn)起順前驅(qū)進(jìn)行遍歷。 找遍歷的第一個(gè)結(jié)點(diǎn) 左子樹上處于“最左下”(沒有左子樹)的結(jié)點(diǎn)。 不斷地找遍歷到的結(jié)點(diǎn)的后繼結(jié)點(diǎn),直到樹中各結(jié)點(diǎn)都遍歷到為止,結(jié)束 若無右子樹,則為后繼線索所指結(jié)點(diǎn);否則為對(duì)其右子樹進(jìn)行中序遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)。 遍歷線索二叉樹步驟(以中序遍歷為例)void InOrderTraverse_Thr(BiThrTree T) p = T-lchild; while (p != T) while (p-LTag=0) p = p-lchild; Visit(p-d

37、ata); while (p-RTag=1 & p-rchild!=T) p = p-rchild; Visit(p-data); p = p-rchild; / InOrderTraverse_Thr中序線索二叉樹中序:DBGJEACHLKFI 中序遍歷線索二叉樹算法實(shí)現(xiàn)TBACEFDGJHIKL 建立線索二叉樹,或者說對(duì)二叉樹線索化,實(shí)質(zhì)上是遍歷一棵二叉樹。在遍歷過程中訪問結(jié)點(diǎn)操作visit()是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空,如果為空,將空的lchild改為結(jié)點(diǎn)的直接前驅(qū),將空的rchild改為結(jié)點(diǎn)的直接后繼。而對(duì)于非空指針,仍然指向孩子結(jié)點(diǎn)。 為了記下遍歷過程中訪問結(jié)點(diǎn)的先后關(guān)系,

38、附設(shè)指針pre始終指向剛剛被訪問過的結(jié)點(diǎn), 若p指針指向當(dāng)前訪問的結(jié)點(diǎn),則pre指向它的前驅(qū)。 六、如何建立線索二叉樹?Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode) ) exit (OVERFLOW); Thrt-LTag = 0; Thrt-RTag =1; Thrt-rchild = Thrt; / 添加頭結(jié)點(diǎn) if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt;

39、 InThreading(T); pre-rchild = Thrt; / 處理最后一個(gè)結(jié)點(diǎn) pre-RTag = 1; Thrt-rchild = pre; return OK; / InOrderThreadingThrt 01LR 算法實(shí)現(xiàn)(1):void leaf( BiTree T ) if (T) leaf(T-lchild); if( T-lchild=NULL&T-rchild=NULL) n+=1; leaf(T-rchild); Status PreOrderTraverse( BiTree T ) if (T) PreOrderTraverse(T-lchild); Vi

40、sit(T-data); PreOrderTraverse(T-rchild); 算法實(shí)現(xiàn)(2):void InThreading(BiThrTree p) if (p) InThreading(p-lchild); / 左子樹線索化 if (!p-lchild) / 建前驅(qū)線索 p-LTag = 1; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-RTag = 1; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驅(qū) InThreading(p-rchild); / 右子樹線索化 / if / InThreadin

41、g相當(dāng)于遍歷算法中的visit( ) 算法實(shí)現(xiàn)(2):6.4.1 樹的存貯結(jié)構(gòu)一、雙親表示法:以一組連續(xù)的空間存儲(chǔ)樹的結(jié)點(diǎn),通過保存每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的位置,表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。其類型定義如下:#define MAX_TREEE_SIZE 100typedef struct PTNode ElemType data; int parent; /雙親位置域 PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int n; /結(jié)點(diǎn)數(shù) Ptree; 特點(diǎn):找雙親容易,找孩子難ARDCFEGBHKA0B0C0D1E1F3G6H6R-1K601234

42、56789數(shù)組下標(biāo)6.4 樹和森林 通過保存每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)的位置,表示樹中結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。 多重鏈表:每個(gè)結(jié)點(diǎn)有多個(gè)指針域,分別指向其子樹的根。 結(jié)點(diǎn)同構(gòu):結(jié)點(diǎn)的指針個(gè)數(shù)相等,為樹的度d。 結(jié)點(diǎn)不同構(gòu):結(jié)點(diǎn)指針個(gè)數(shù)不等,為該結(jié)點(diǎn)的度d。datachild1child2childddatadegreechild1child2childd二、孩子表示法 孩子鏈表:其主體是一個(gè)與結(jié)點(diǎn)個(gè)數(shù)一樣大小的一維數(shù)組,數(shù)組的每一個(gè)元素有兩個(gè)域組成,一個(gè)域用來存放結(jié)點(diǎn)信息,另一個(gè)用來存放指針,該指針指向由該結(jié)點(diǎn)孩子組成的單鏈表的首位置。單鏈表的結(jié)構(gòu)也由兩個(gè)域組成,一個(gè)存放孩子結(jié)點(diǎn)在一維數(shù)組中的序號(hào),另一個(gè)

43、是指針域,指向下一個(gè)孩子。每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ),再用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表。二、孩子表示法ARDCFEGBHKABCDEFGHRK0123456789數(shù)組下標(biāo)125437896特點(diǎn):找孩子容易,找雙親難 孩子鏈表表示法圖示typedef struct CTNode /孩子結(jié)點(diǎn) int child; struct CTNode *next; *ChildPtr;typedef struct ElemType data; ChildPtr firstchild; /孩子鏈表頭指針 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;

44、int n , r ; /結(jié)點(diǎn)數(shù)和根的位置CTree; 孩子鏈表表示法類型定義 用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu),鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。 特點(diǎn):操作容易,但破壞了樹的層次。 孩子兄弟表示法類型定義: typedef struct CSNode ElemType data; struct CSNode *firstchild , *nextsibling; CSNode , *CSTree;三、孩子兄弟表示法ARDCFEGBHKRAD B EC F G H K 利用樹的孩子兄弟鏈表這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)各種樹的操作。例如找某結(jié)點(diǎn)的第i個(gè)孩子,則只要先從左指針域

45、中找到第1個(gè)孩子結(jié)點(diǎn)上,然后沿著孩子結(jié)點(diǎn)的next域連續(xù)走i-1步便可找到第i個(gè)孩子。如增加一個(gè)parent域,則也能方便實(shí)現(xiàn)求雙親的操作。 三、孩子兄弟表示法一. 樹轉(zhuǎn)變?yōu)槎鏄?加線:在兄弟之間加一連線; 抹線:對(duì)每個(gè)結(jié)點(diǎn),除了其左孩子外,去除其與其余孩子之間的關(guān)系; 旋轉(zhuǎn):以樹的根結(jié)點(diǎn)為軸心,將整樹順時(shí)針轉(zhuǎn)45。6.4.2 樹、森林與二叉樹轉(zhuǎn)換BAEDGHCFIBAEDGHCFIBAEDGHCFIBAEDGHCFIBAEDGHCFI 由上面的轉(zhuǎn)換可以看出,在二叉樹中,左分支上的各結(jié)點(diǎn)在原來的樹中是父子關(guān)系,而右分支上的各結(jié)點(diǎn)在原來的樹中是兄弟關(guān)系。由于樹的根結(jié)點(diǎn)沒有兄弟,所以變換后的二叉

46、樹的根結(jié)點(diǎn)的右孩子必為空。 樹轉(zhuǎn)變?yōu)槎鏄鋵?shí)現(xiàn)過程 由森林的概念可知,森林是若干棵樹的集合,只要將森林中各棵樹的根視為兄弟,每棵樹又可以用二叉樹表示,這樣,森林也同樣可以用二叉樹表示。具體的方法如下: 將各棵樹分別轉(zhuǎn)換成二叉樹; 將每棵樹的根結(jié)點(diǎn)用線相連; 以第一棵樹根結(jié)點(diǎn)為二叉樹的根,再以根結(jié)點(diǎn)為軸心,順時(shí)針旋轉(zhuǎn),構(gòu)成二叉樹型結(jié)構(gòu)。二、森林轉(zhuǎn)換成二叉樹HIGJBADCEFHIGJBADCEFHIGJBADCEFHIGMBADCEF 森林轉(zhuǎn)變?yōu)槎鏄鋵?shí)現(xiàn)過程 加線:若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子,則將p的右孩子,右孩 子的右孩子,沿分支找到的所有右孩子,都與p 的雙親用線連起來; 抹線:抹掉原二叉

47、樹中雙親與右孩子之間的連線; 調(diào)整:將結(jié)點(diǎn)按層次排列,形成樹結(jié)構(gòu)。BAEDGHCFIBAEDGHCFIBAEDGHCFI注:該二叉樹的右子樹為空三、二叉樹轉(zhuǎn)換成樹 抹線:將二叉樹中根結(jié)點(diǎn)與其右孩子連線,及沿右分支搜索到的所有右孩子間連線全部抹掉,使之變成孤立的二叉樹。 還原:將孤立的二叉樹還原成樹。HIGMBADCEFHIGJBADCEF注:該二叉樹的右子樹一定不為空四、二叉樹轉(zhuǎn)換成森林在樹和森林中,一個(gè)結(jié)點(diǎn)可能有兩棵以上的子樹,所以不宜討論它們的中序遍歷, 即樹和森林只有先序遍歷和后序遍歷。1. 樹的先序遍歷若樹非空,則先訪問根結(jié)點(diǎn),然后依次先序遍歷各子樹。先序遍歷:ABEFIGCDHJKL

48、NOM2. 樹的后序遍歷若樹非空,則依次后序遍歷各子樹,最后訪問根結(jié)點(diǎn)。后序遍歷:EIFGBCJKNOLMHDA6.4.3 樹和森林的遍歷ACBDEFGIHJKLMNO3. 森林的先序遍歷若森林非空,則先訪問森林中第一棵樹的根結(jié)點(diǎn),再先序遍歷第一棵樹各子樹,接著先序遍歷第二棵樹、第三棵樹、直到最后一棵樹。 遍歷結(jié)果:ABCDEFGHIJ4. 森林的后序遍歷按順序后序遍歷森林中的每一棵樹。遍歷結(jié)果:BCDAFEHJIG6.4.3 樹和森林的遍歷HIGJBADCEF 一、基本概念 路徑和路徑長(zhǎng)度: 在一棵樹中,從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路,稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1,則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。 結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度: 若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值,則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積稱為結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。6.6 赫夫曼樹及其應(yīng)用一、基本概念(續(xù)) 樹的帶權(quán)路徑長(zhǎng)度: 樹的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和,記為其中n 為葉子結(jié)點(diǎn)數(shù)目,wi為第i 個(gè)葉子結(jié)點(diǎn)的權(quán)值,li 為第i

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論