前面講到的順序表盹憎、棧和隊(duì)列都是一對一的線性結(jié)構(gòu)敦姻，這節(jié)講一對多的線性結(jié)構(gòu)——樹∑缧樱「一對多」就是指一個元素只能有一個前驅(qū)镰惦，但可以有多個后繼。

一犬绒、基本概念

樹（tree）是n（n>=0）個結(jié)點(diǎn)的有窮集旺入。n=0時稱為空樹。在任意一個非空樹中：（1）每個元素稱為結(jié)點(diǎn)（node）凯力；（2）僅有一個特定的結(jié)點(diǎn)被稱為根結(jié)點(diǎn)或樹根（root）茵瘾。（3）當(dāng)n>1時，其余結(jié)點(diǎn)可分為m（m≥0）個互不相交的集合T1咐鹤，T2拗秘，……Tm，其中每一個集合Ti（1<=i<=m）本身也是一棵樹祈惶，被稱作根的子樹（subtree）雕旨。

注意：

n>0時，根節(jié)點(diǎn)是唯一的捧请。

m>0時凡涩，子樹的個數(shù)沒有限制，但它們一定是互不相交的血久。

結(jié)點(diǎn)擁有的子樹數(shù)被稱為結(jié)點(diǎn)的度（Degree）突照。度為0的結(jié)點(diǎn)稱為葉節(jié)點(diǎn)（Leaf）或終端結(jié)點(diǎn)，度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)氧吐。除根結(jié)點(diǎn)外讹蘑，分支結(jié)點(diǎn)也被稱為內(nèi)部結(jié)點(diǎn)。結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子（Child）筑舅，該結(jié)點(diǎn)稱為孩子的雙親或父結(jié)點(diǎn)座慰。同一個雙親的孩子之間互稱為兄弟。樹的度是樹中各個結(jié)點(diǎn)度的最大值翠拣。

結(jié)點(diǎn)的層次（Level）從根開始定義起版仔，根為第一層，根的孩子為第二層误墓。雙親在同一層的結(jié)點(diǎn)互為堂兄弟蛮粮。樹中結(jié)點(diǎn)的最大層次稱為樹的深度（Depth）或高度。如果將樹中結(jié)點(diǎn)的各個子樹看成從左到右是有次序的谜慌，不能互換的然想，則稱該樹為有序樹，否則稱為無序樹欣范。森林是m（m>=0）棵互不相交的樹的集合变泄。

樹的定義：

二令哟、樹的存儲結(jié)構(gòu)

由于樹中每個結(jié)點(diǎn)的孩子可以有多個，所以簡單的順序存儲結(jié)構(gòu)無法滿足樹的實(shí)現(xiàn)要求妨蛹。下面介紹三種常用的表示樹的方法：雙親表示法屏富、孩子表示法和孩子兄弟表示法。

1蛙卤、雙親表示法

由于樹中每個結(jié)點(diǎn)都僅有一個雙親結(jié)點(diǎn)（根節(jié)點(diǎn)沒有）狠半，我們可以使用指向雙親結(jié)點(diǎn)的指針來表示樹中結(jié)點(diǎn)的關(guān)系。這種表示法有點(diǎn)類似于前面介紹的靜態(tài)鏈表的表示方法表窘。具體做法是以一組連續(xù)空間存儲樹的結(jié)點(diǎn)典予，同時在每個結(jié)點(diǎn)中，設(shè)一個「游標(biāo)」指向其雙親結(jié)點(diǎn)在數(shù)組中的位置乐严。由于根結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)，我們約定根節(jié)點(diǎn)的parent域值為-1衣摩。樹的雙親表示法如下所示：

雙親表示法

這樣的存儲結(jié)構(gòu)昂验，我們可以根據(jù)結(jié)點(diǎn)的parent域在O(1)的時間找到其雙親結(jié)點(diǎn)，但是只能通過遍歷整棵樹才能找到它的孩子結(jié)點(diǎn)艾扮。一種解決辦法是在結(jié)點(diǎn)結(jié)構(gòu)中增加其孩子結(jié)點(diǎn)的域既琴，但若結(jié)點(diǎn)的孩子結(jié)點(diǎn)很多，結(jié)點(diǎn)結(jié)構(gòu)將會變的很復(fù)雜泡嘴。

2甫恩、孩子表示法

由于樹中每個結(jié)點(diǎn)可能有多個孩子，可以考慮用多重鏈表酌予，即每個結(jié)點(diǎn)有多個指針域磺箕，每個指針指向一個孩子結(jié)點(diǎn)，我們把這種方法叫多重鏈表表示法抛虫。它有兩種設(shè)計(jì)方案：

方案一：指針域的個數(shù)等于樹的度松靡。

對于上一節(jié)中的樹，樹的度為3建椰，其實(shí)現(xiàn)為：

方案一

顯然雕欺，當(dāng)樹中各結(jié)點(diǎn)的度相差很大時，這種方法對空間有很大的浪費(fèi)棉姐。

方案二屠列，每個結(jié)點(diǎn)指針域的個數(shù)等于該結(jié)點(diǎn)的度，取一個位置來存儲結(jié)點(diǎn)指針的個數(shù)伞矩。

對于上一節(jié)中的樹笛洛，這種方法的實(shí)現(xiàn)為：

方案二

這種方法克服了浪費(fèi)空間的缺點(diǎn)，但由于各結(jié)點(diǎn)結(jié)構(gòu)不同扭吁，在運(yùn)算上會帶來時間上的損耗撞蜂。

為了減少空指針的浪費(fèi)盲镶，同時又使結(jié)點(diǎn)相同。我們可以將順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)相結(jié)合蝌诡。具體做法是：把每個結(jié)點(diǎn)的孩子結(jié)點(diǎn)以單鏈表的形式鏈接起來溉贿，若是葉子結(jié)點(diǎn)則此單鏈表為空。然后將所有鏈表存放進(jìn)一個一維數(shù)組中浦旱。這種表示方法被稱為孩子表示法宇色。其結(jié)構(gòu)為：

孩子表示法

這種結(jié)構(gòu)對于查找某個結(jié)點(diǎn)的孩子結(jié)點(diǎn)比較容易，但若想要查找它的雙親或兄弟颁湖，則需要遍歷整棵樹宣蠕，比較麻煩∩啵可以將雙親表示法和孩子表示法相結(jié)合抢蚀，這種方法被稱為雙親孩子表示法。其結(jié)構(gòu)如下：

雙親孩子表示法

其代碼和孩子表示法的基本相同镰禾，只需在Node結(jié)點(diǎn)中增加parent域即可皿曲。

3笛园、孩子兄弟表示法

任意一棵樹像鸡，它的結(jié)點(diǎn)的第一個孩子如果存在則是唯一的割粮，它的右兄弟如果存在也是唯一的堰乔。因此虱肄，我們可以使用兩個分別指向該結(jié)點(diǎn)的第一個孩子和右兄弟的指針來表示一顆樹莉给。

其結(jié)構(gòu)如下：

孩子兄弟表示法

這個方法楷怒，可以方便的查找到某個結(jié)點(diǎn)的孩子垛吗，只需先通過firstChild找到它的第一個孩子织堂，然后通過rightSib找到它的第二個孩子叠艳，接著一直下去，直到找到想要的孩子捧挺。若要查找某個結(jié)點(diǎn)的雙親和左兄弟虑绵，使用這個方法則比較麻煩。

這個方法最大的好處是將一顆復(fù)雜的樹變成了一顆二叉樹闽烙。這樣就可以使用二叉樹的一些特性和算法了翅睛。