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

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

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

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

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