樹的本質(zhì)

樹其實(shí)是一種非線性結(jié)構(gòu)，我們熟知的線性結(jié)構(gòu)，比如數(shù)組，隊(duì)列，鏈表，構(gòu)成線性結(jié)構(gòu)的每個(gè)元素至多存在一個(gè)直接前驅(qū)（或直接后繼）元素。所謂非線性結(jié)構(gòu)，是指在該結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素，有兩個(gè)或者兩個(gè)以上的直接前驅(qū)（或直接后繼）元素。天天走的大馬路，就是一種非線性結(jié)構(gòu)。

樹的概念

樹的定義
樹是n（n≥0）個(gè)有限數(shù)據(jù)元素的集合。當(dāng)n=0時(shí)，稱這棵樹為空樹。在一顆非空樹T中：
1）有一個(gè)特殊的數(shù)據(jù)元素成為樹的根節(jié)點(diǎn)，根節(jié)點(diǎn)是沒有前驅(qū)結(jié)點(diǎn)的。
2）若n>1，除根節(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分成m(m>0)個(gè)互不相交（重點(diǎn)加粗）的集合T1,T2,T3....Tm，其中每一個(gè)集合Ti（1≤ i ≤m）本身又是一棵樹，也都稱為這個(gè)根節(jié)點(diǎn)的子樹。

可以看出，在樹的定義中使用了遞歸概念，用樹來定義樹。

樹結(jié)構(gòu)

從上述定義和上圖的示例，我們可以看出，樹具有下面兩個(gè)特點(diǎn)：
1）樹的根節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)，除根節(jié)點(diǎn)之外的所有節(jié)點(diǎn)有且只有一個(gè)前驅(qū)節(jié)點(diǎn)。換句話來說，就是從根節(jié)點(diǎn)到子樹的某個(gè)節(jié)點(diǎn)，只能有一條路徑（樹的術(shù)語，后續(xù)有解釋）。
2）樹中所有節(jié)點(diǎn)可以有任意個(gè)后繼節(jié)點(diǎn)，當(dāng)然也可以沒有。
根據(jù)上述特點(diǎn)可知下圖所示的就都不是樹結(jié)構(gòu)。

非樹結(jié)構(gòu)

樹的相關(guān)術(shù)語

1）結(jié)點(diǎn)
在樹中，一個(gè)元素也稱做一個(gè)結(jié)點(diǎn)。
2）結(jié)點(diǎn)的度
結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。
3）葉結(jié)點(diǎn)
度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)（我覺得可以叫沒孩子的結(jié)點(diǎn)）。
4）分支結(jié)點(diǎn)
與葉結(jié)點(diǎn)相反，度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。一棵樹的結(jié)點(diǎn)除葉結(jié)點(diǎn)外，其余的都是分支結(jié)點(diǎn)。
5）孩子，雙親，兄弟
樹中一個(gè)結(jié)點(diǎn)的子樹的根節(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子；反過來，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親；具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。
6）路徑，路徑長度
如果一棵樹中的一串結(jié)點(diǎn)N1，N2，...，Nk有如下關(guān)系：結(jié)點(diǎn)Ni是Ni+1的父節(jié)點(diǎn)（1≤ i <k），就把N1，N2，...，Nk稱為一條由N1到Nk的路徑，這條路徑的長度就k-1。
7）祖先，子孫
在樹中，如果有一條路徑從結(jié)點(diǎn)M到結(jié)點(diǎn)N，那M就稱為N的祖先，而N稱為M的子孫。
8）結(jié)點(diǎn)的層數(shù)
規(guī)定樹的根節(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親的結(jié)點(diǎn)的層數(shù)加1。
9）樹的深度
樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的深度。
10）樹的度
樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。
11）有序樹和無序樹
如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，那么如果交換了某結(jié)點(diǎn)各子樹的相對位置，則會(huì)構(gòu)成不同的樹，這樣的樹稱為有序樹；反之，則稱為無序樹。
12）森林
零棵或有限棵不相交的樹的集合稱為森林。自然界中樹和森林是不同的概念，但在數(shù)據(jù)結(jié)構(gòu)中，樹和森林只有很小的區(qū)別。任何一棵樹，刪除根結(jié)點(diǎn)就變成了森林。

樹的表示

話不多說，直接上圖。

樹表示法

樹的基本操作

1）init（t）：初始化一顆空樹t。
2）root（x）：求結(jié)點(diǎn)x所在樹的根節(jié)點(diǎn)。
3）parent（t，x）：求樹t中結(jié)點(diǎn)x是雙親結(jié)點(diǎn)。
4）child（t，x，i）：求樹t中結(jié)點(diǎn)x的第i個(gè)孩子結(jié)點(diǎn)。
5）rightSibling（t，x）：求樹t中結(jié)點(diǎn)x的第一個(gè)右邊兄弟結(jié)點(diǎn)。
6）insert（t，x，i，s）：把以s為根結(jié)點(diǎn)的樹插入到樹t中作為結(jié)點(diǎn)x的第i棵子樹。
7）delete（t，x，i）：在樹t中刪除結(jié)點(diǎn)x的第i棵子樹。
8）tranverse（t）：樹的遍歷操作，即按某個(gè)方式訪問樹t中的每個(gè)結(jié)點(diǎn)，且使每個(gè)結(jié)點(diǎn)只被訪問一次。

樹的存儲(chǔ)

樹的存儲(chǔ)有多種方式，既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但無論采用哪種存儲(chǔ)方式，都要求存儲(chǔ)不但能夠存儲(chǔ)各結(jié)點(diǎn)本身的數(shù)據(jù)，還要能唯一地反映樹中各結(jié)點(diǎn)之間的邏輯關(guān)系，每種存儲(chǔ)方式都各有各的有點(diǎn)。常見的存儲(chǔ)方法有以下幾種。
1）雙親鏈表存儲(chǔ)方法
由樹的定義可以知道，樹中的每個(gè)節(jié)點(diǎn)都有唯一的一個(gè)雙親結(jié)點(diǎn)，根據(jù)這個(gè)特性，可以用一組連續(xù)的存儲(chǔ)空間存儲(chǔ)樹中的各個(gè)結(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)除了存放本身的信息外還有其雙親結(jié)點(diǎn)存儲(chǔ)位置，樹的這種存儲(chǔ)方法稱為雙親鏈表表示法，如下所示。

一棵樹及其雙親靜態(tài)鏈表存儲(chǔ)示意圖

當(dāng)算法中需要在樹結(jié)構(gòu)中頻繁地查找某結(jié)點(diǎn)的父結(jié)點(diǎn)或者根節(jié)點(diǎn)時(shí)，使用雙親表示法最合適。當(dāng)頻繁地訪問結(jié)點(diǎn)的孩子結(jié)點(diǎn)時(shí)，雙親表示法就很麻煩，采用孩子鏈表表示法就很簡單。
2）孩子鏈表表示法
樹中每一個(gè)數(shù)據(jù)元素對應(yīng)一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)中有兩部分信息，一部分是其本身的數(shù)據(jù)信息，另一部分是其孩子鏈表的頭指針，即將每個(gè)數(shù)據(jù)元素的孩子們鏈接成一個(gè)孩子鏈表，將鏈表的頭指針和它們的雙親信息組成了一個(gè)結(jié)點(diǎn)，再將這些結(jié)點(diǎn)順序存儲(chǔ)起來。

一棵樹及其孩子鏈表存儲(chǔ)示意圖

在用孩子鏈表方法存儲(chǔ)的樹中，查找雙親比較困難，查找孩子卻十分方便，所以比較適用于對孩子操作多的應(yīng)用。由于前兩種表示法都有局限性，于是結(jié)合前兩種表示法，衍生出了雙親孩子鏈表表示法，優(yōu)點(diǎn)不言而喻了，具體存儲(chǔ)方法如下圖所示。

一棵樹及其雙親孩子鏈表存儲(chǔ)示意圖

3）孩子兄弟鏈表存儲(chǔ)方法
這是一種常用的存儲(chǔ)結(jié)構(gòu)。其方式是：在樹中每個(gè)元素對應(yīng)一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)除其信息域外，有兩個(gè)指針，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。

一棵樹及其孩子兄弟鏈表存儲(chǔ)示意圖

仔細(xì)觀察不難發(fā)現(xiàn)，通過孩子兄弟鏈表存儲(chǔ)方法，普通樹轉(zhuǎn)化為了二叉樹，所以孩子兄弟表示法又被稱為“二叉樹表示法”或者“二叉鏈表表示法”。

樹的基本知識就介紹到這，下一篇將介紹樹和森林與二叉樹之間的轉(zhuǎn)換規(guī)則，樹和森林的遍歷方式，以及對應(yīng)的算法實(shí)現(xiàn)。