什么是樹

樹（Tree）是一種抽象數(shù)據(jù)類型，用來模擬實(shí)現(xiàn)具有樹狀類型結(jié)構(gòu)的數(shù)據(jù)集合。它具有n（n>=0）個有層次的有限結(jié)點(diǎn)。當(dāng)n=0時，稱為空樹；n>0時，其余結(jié)點(diǎn)分為m個互斥的有限集合T1，T2，T3，每個集合分別稱為子樹。

與棧、隊列和鏈表不同，樹是一種非線性數(shù)據(jù)結(jié)構(gòu)。一顆樹只有一個根結(jié)點(diǎn)。擁有多顆根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是樹的集合，稱之為森林

1.樹的性質(zhì)

結(jié)點(diǎn)數(shù)n>0的樹滿足以下性質(zhì)：

1. 每個結(jié)點(diǎn)存在有限個子結(jié)點(diǎn)或無子結(jié)點(diǎn)；

2. 沒有父結(jié)點(diǎn)的結(jié)點(diǎn)稱之為根結(jié)點(diǎn)；

3. 每個非根結(jié)點(diǎn)有且只有一個父結(jié)點(diǎn)；

4. 除了根節(jié)點(diǎn)外，每個子節(jié)點(diǎn)可以分為多個不相交的子樹；

5. 樹中不存在環(huán)。

2.樹中涉及到的基本術(shù)語：

1.結(jié)點(diǎn)的度：

結(jié)點(diǎn)擁有子樹的個數(shù)稱為該結(jié)點(diǎn)的度。如上圖中B的度為2，C的度為1。度為0的結(jié)點(diǎn)稱之為葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)，度不為0的結(jié)點(diǎn)稱之為分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱之為內(nèi)部結(jié)點(diǎn)。

2.樹的度：

樹的度是樹內(nèi)各個結(jié)點(diǎn)度的最大值。

3.子女節(jié)點(diǎn)：

若結(jié)點(diǎn)x存在子樹，則子樹的根結(jié)點(diǎn)稱之為結(jié)點(diǎn)x的子女結(jié)點(diǎn)。

4.父結(jié)點(diǎn)：

若結(jié)點(diǎn)x有子女結(jié)點(diǎn)，則它為其子女結(jié)點(diǎn)的父結(jié)點(diǎn)。

5.兄弟結(jié)點(diǎn)：

同一父結(jié)點(diǎn)的子女互稱兄弟。如上圖中B、C、D互稱兄弟。

6.祖先結(jié)點(diǎn)：

從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)所經(jīng)歷的所有結(jié)點(diǎn)稱為目標(biāo)結(jié)點(diǎn)的祖先結(jié)點(diǎn)，如圖中E的祖先結(jié)點(diǎn)為A、B。

7.子孫結(jié)點(diǎn)：

某一結(jié)點(diǎn)的子女，以及這些子女的子女均為該節(jié)點(diǎn)的子孫結(jié)點(diǎn)。

8.層次與深度：

根結(jié)點(diǎn)所處的層次為第1層，其子女所屬的層次為第2層。以此類推，若某結(jié)點(diǎn)所處的層次為第i層，其子女所處的層次為第i+1層。樹中結(jié)點(diǎn)的最大層次稱之為樹的深度或高度。上圖中樹的深度為4。

9.有序樹與無序樹：

樹的有序或無序由結(jié)構(gòu)定義。如果將樹中結(jié)點(diǎn)的子樹規(guī)定了從左至右的次序，且不能互換，稱該樹為有序樹，否則為無序樹。

10.二叉樹：

每個節(jié)點(diǎn)最多含有兩個子樹的樹稱為二叉樹；

11.完全二叉樹：

若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹

12.滿二叉樹：

"除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)的二叉樹。

13.哈夫曼樹：

帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；

3.樹的存儲方式

順序存儲和鏈?zhǔn)酱鎯Χ疾荒芎芎玫胤从吵鰳涞倪壿嬯P(guān)系，故需采用順序和鏈?zhǔn)较嘟Y(jié)合的方式。樹的存儲方式主要有以下三種：

1.雙親表示法

雙親表示法采用順序表（也就是數(shù)組）存儲普通樹，其實(shí)現(xià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)位置的變量通常置為 -1。

?

2.孩子表示法

使用順序加鏈?zhǔn)降拇鎯Ψ绞健Ｊ紫葧⒁粋€順序表存儲樹中的各個結(jié)點(diǎn)，此外，孩子表示法還會在每個結(jié)點(diǎn)后配備一個鏈表，用于存儲它的子女結(jié)點(diǎn)。無子女結(jié)點(diǎn)的結(jié)點(diǎn)對應(yīng)的是空鏈表。

孩子兄弟表示法采用的是鏈?zhǔn)酱鎯Φ姆绞?。從樹的根結(jié)點(diǎn)開始，依次使用鏈表存儲各個結(jié)點(diǎn)的孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)。該鏈表中的結(jié)點(diǎn)分為三部分：孩子結(jié)點(diǎn)、數(shù)據(jù)域、兄弟結(jié)點(diǎn)。