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

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

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

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

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