樹(shù)是一種重要的線性結(jié)構(gòu)

1、樹(shù)是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹(shù)中稱(chēng)為結(jié)點(diǎn)）按分支關(guān)系組織起來(lái)的結(jié)構(gòu)，很象自然界中的樹(shù)那樣。樹(shù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類(lèi)社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹(shù)形象表示。樹(shù)在計(jì)算機(jī)領(lǐng)域中也得到廣泛應(yīng)用，如在編譯源程序如下時(shí)，可用樹(shù)表示源源程序如下的語(yǔ)法結(jié)構(gòu)。又如在數(shù)據(jù)庫(kù)系統(tǒng)中，樹(shù)型結(jié)構(gòu)也是信息的重要組織形式之一。一切具有層次關(guān)系的問(wèn)題都可用樹(shù)來(lái)描述。一、樹(shù)的概述樹(shù)結(jié)構(gòu)的特點(diǎn)是：它的每一個(gè)結(jié)點(diǎn)都可以有不止一個(gè)直

2、接后繼，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨。以下具體地給出樹(shù)的定義及樹(shù)的數(shù)據(jù)結(jié)構(gòu)表示。（一）樹(shù)的定義樹(shù)是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合，其中：⒈必有一個(gè)特定的稱(chēng)為根(ROOT)的結(jié)點(diǎn)；⒉剩下的結(jié)點(diǎn)被分成ｎ=0個(gè)互不相交的集合T1、T2、......Tn，而且，這些集合的每一個(gè)又都是樹(shù)。樹(shù)T1、T2、......Tn被稱(chēng)作根的子樹(shù)(Subtree)。樹(shù)的遞歸定義如下：（1）至少有一個(gè)結(jié)點(diǎn)（稱(chēng)為根）（2）其它是互不相交的子樹(shù)1.樹(shù)的

3、度——也即是寬度，簡(jiǎn)單地說(shuō)，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹(shù)各結(jié)點(diǎn)中最大的度作為該樹(shù)的度，如上圖的樹(shù)，其度為3樹(shù)中度為零的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹(shù)中度不為零的結(jié)點(diǎn)稱(chēng)為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱(chēng)為內(nèi)部結(jié)點(diǎn)。2.樹(shù)的深度——組成該樹(shù)各結(jié)點(diǎn)的最大層次，如上圖，其深度為4；3.森林——指若干棵互不相交的樹(shù)的集合，如上圖，去掉根結(jié)點(diǎn)A，其原來(lái)的二棵子樹(shù)T1、T2、T3的集合T1T2T3就為森林；4.有序樹(shù)——指樹(shù)中同層結(jié)點(diǎn)從左

4、到右有次序排列，它們之間的次序不能互換，這樣的樹(shù)稱(chēng)為有序樹(shù)，否則稱(chēng)為無(wú)序樹(shù)。5.樹(shù)的表示樹(shù)的表示方法有許多，常用的方法是用括號(hào)：先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹(shù)由左至右的順序放入括號(hào)中，而對(duì)子樹(shù)也采用同樣的方法處理；同層子樹(shù)與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，同層子樹(shù)之間用逗號(hào)隔開(kāi)，最后用閉括號(hào)括起來(lái)。如上圖可寫(xiě)成如下形式：則N0=N21；(4)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為int（log2n）1(5)有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)各結(jié)點(diǎn)如