《數(shù)據(jù)結(jié)構(gòu)a》第章

數(shù)據(jù)結(jié)構(gòu)DataStructuresinC++南京郵電大學(xué)計算機(jī)學(xué)院2006年9月第5章樹5.1

樹的基本概念5.2

二叉樹5.3

二叉樹的遍歷5.4

二叉樹遍歷的非遞歸算法5.5

樹和森林5.6

堆和優(yōu)先權(quán)隊列5.7

哈夫曼樹和哈夫曼編碼5.8

并查集和等價關(guān)系南京郵電大學(xué)計算機(jī)學(xué)院2006年9月5.1樹的基本概念

樹形結(jié)構(gòu)是元素之間有著分層關(guān)系的結(jié)構(gòu)，它類似于自然界中的樹。這是一類很重要的非線性數(shù)據(jù)結(jié)構(gòu)。一方面，計算機(jī)應(yīng)用中，常常出現(xiàn)嵌套的數(shù)據(jù)，樹結(jié)構(gòu)提供了對該類數(shù)據(jù)的自然表示。另一方面利用樹結(jié)構(gòu)，我們可以有效地解決一些算法問題。南京郵電大學(xué)計算機(jī)學(xué)院2006年9月圖5-1西歐語言譜系圖原始印歐語古意大利語日耳曼語西日耳曼語拉丁語西班牙語法語意大利語希臘語北日耳曼語冰島語瑞典語挪威語英語荷蘭語德語古希臘語南京郵電大學(xué)計算機(jī)學(xué)院陳慧南5.1.1樹的定義定義5.1樹是包括n個結(jié)點(diǎn)的有限非空集合D，R是D中元素的序偶的集合，R滿足以下特性：（1）有且僅有一個結(jié)點(diǎn)rD，不存在任何結(jié)點(diǎn)vD，vr，使得<v,r>R，稱r為樹的根；（2）除根r以外的所有結(jié)點(diǎn)uD，都有且僅有一個結(jié)點(diǎn)vD，vu，使得<v,u>R。這樣定義的樹也稱有根樹，簡稱樹。

南京郵電大學(xué)計算機(jī)學(xué)院陳慧南定義5.2樹是包括n個結(jié)點(diǎn)的有限非空集合T，其中，一個特定的結(jié)點(diǎn)r稱為根，其余結(jié)點(diǎn)T-{r}劃分成m（m0）個互不相交的子集T1,T2,,Tm，其中，每個子集都是樹，被稱為樹根r的子樹。

南京郵電大學(xué)計算機(jī)學(xué)院陳慧南5.1.2基本術(shù)語

樹中元素常稱為結(jié)點(diǎn)。根和它的子樹根（如果存在）之間形成一條邊。如果從某個結(jié)點(diǎn)沿著樹中的邊可到達(dá)另一個結(jié)點(diǎn)，則稱這兩個結(jié)點(diǎn)間存在一條路徑。南京郵電大學(xué)計算機(jī)學(xué)院陳慧南

若一個結(jié)點(diǎn)有子樹，那么該結(jié)點(diǎn)稱為子樹根的雙親，子樹的根是該結(jié)點(diǎn)的孩子。有相同雙親的結(jié)點(diǎn)互為兄弟。一個結(jié)點(diǎn)的所有子樹上的任何結(jié)點(diǎn)都是該結(jié)點(diǎn)的后裔。從根結(jié)點(diǎn)到某個結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先。南京郵電大學(xué)計算機(jī)學(xué)院陳慧南一個結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度。度為零的結(jié)點(diǎn)稱為葉子，其余結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。樹中結(jié)點(diǎn)的最大的度稱為樹的度。樹是層次結(jié)構(gòu)的，規(guī)定根結(jié)點(diǎn)的層次為1，其結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加1。樹中結(jié)點(diǎn)的最大層次稱為該樹的高度。南京郵電大學(xué)計算機(jī)學(xué)院陳慧南如果敗樹中召結(jié)點(diǎn)貢的各纖子樹誰之間攜的次槳序是售不重晴要的喘，可像以交桑換位紀(jì)置，者這樣席的樹懼稱為無序診樹。也就燦是我粘們通蟲常所蠢說的浩樹。祖如果王將樹犯中結(jié)暗點(diǎn)的床各棵勾子樹回看成障是從擁左到討右有葵次序他的，室則稱扁該樹董為有序郊樹。從左令到右滅，可蕉分別氣稱這指些子饑樹為率第一搶子樹袖，第淚二子揭樹等形等。森林