樹的本質(zhì)
樹其實是一種非線性結(jié)構(gòu)丙挽，我們熟知的線性結(jié)構(gòu)肺孵，比如數(shù)組，隊列颜阐，鏈表平窘，構(gòu)成線性結(jié)構(gòu)的每個元素至多存在一個直接前驅(qū)（或直接后繼）元素。所謂非線性結(jié)構(gòu)凳怨，是指在該結(jié)構(gòu)中至少存在一個數(shù)據(jù)元素瑰艘，有兩個或者兩個以上的直接前驅(qū)（或直接后繼）元素。天天走的大馬路肤舞，就是一種非線性結(jié)構(gòu)紫新。
樹的概念
樹的定義
樹是n（n≥0）個有限數(shù)據(jù)元素的集合。當(dāng)n=0時李剖，稱這棵樹為空樹芒率。在一顆非空樹T中：
1）有一個特殊的數(shù)據(jù)元素成為樹的根節(jié)點，根節(jié)點是沒有前驅(qū)結(jié)點的篙顺。
2）若n>1偶芍，除根節(jié)點之外的其余數(shù)據(jù)元素被分成m(m>0)個互不相交（重點加粗）的集合T1,T2,T3....Tm，其中每一個集合Ti（1≤ i ≤m）本身又是一棵樹德玫，也都稱為這個根節(jié)點的子樹匪蟀。
可以看出，在樹的定義中使用了遞歸概念宰僧，用樹來定義樹萄窜。
從上述定義和上圖的示例，我們可以看出，樹具有下面兩個特點：
1）樹的根節(jié)點沒有前驅(qū)節(jié)點查刻，除根節(jié)點之外的所有節(jié)點有且只有一個前驅(qū)節(jié)點。換句話來說凤类，就是從根節(jié)點到子樹的某個節(jié)點穗泵，只能有一條路徑（樹的術(shù)語，后續(xù)有解釋）谜疤。
2）樹中所有節(jié)點可以有任意個后繼節(jié)點佃延，當(dāng)然也可以沒有。
根據(jù)上述特點可知下圖所示的就都不是樹結(jié)構(gòu)夷磕。
樹的相關(guān)術(shù)語
1）結(jié)點
在樹中履肃，一個元素也稱做一個結(jié)點。
2）結(jié)點的度
結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度坐桩。
3）葉結(jié)點
度為0的結(jié)點稱為葉結(jié)點尺棋，或者稱為終端結(jié)點（我覺得可以叫沒孩子的結(jié)點）。
4）分支結(jié)點
與葉結(jié)點相反绵跷，度不為0的結(jié)點稱為分支結(jié)點膘螟，或者稱為非終端結(jié)點。一棵樹的結(jié)點除葉結(jié)點外碾局，其余的都是分支結(jié)點荆残。
5）孩子，雙親净当，兄弟
樹中一個結(jié)點的子樹的根節(jié)點稱為這個結(jié)點的孩子内斯；反過來，這個結(jié)點稱為它孩子結(jié)點的雙親像啼；具有同一個雙親的孩子結(jié)點互稱為兄弟俘闯。
6）路徑，路徑長度
如果一棵樹中的一串結(jié)點N1埋合，N2备徐，...，Nk有如下關(guān)系：結(jié)點Ni是Ni+1的父節(jié)點（1≤ i <k）甚颂，就把N1蜜猾，N2，...振诬，Nk稱為一條由N1到Nk的路徑蹭睡，這條路徑的長度就k-1。
7）祖先赶么，子孫
在樹中肩豁，如果有一條路徑從結(jié)點M到結(jié)點N，那M就稱為N的祖先，而N稱為M的子孫清钥。
8）結(jié)點的層數(shù)
規(guī)定樹的根節(jié)點的層數(shù)為1琼锋，其余結(jié)點的層數(shù)等于它的雙親的結(jié)點的層數(shù)加1。
9）樹的深度
樹中結(jié)點的最大層數(shù)稱為樹的深度祟昭。
10）樹的度
樹中各結(jié)點度的最大值稱為該樹的度缕坎。
11）有序樹和無序樹
如果一棵樹中結(jié)點的各子樹從左到右是有次序的，那么如果交換了某結(jié)點各子樹的相對位置篡悟，則會構(gòu)成不同的樹谜叹，這樣的樹稱為有序樹；反之搬葬，則稱為無序樹荷腊。
12）森林
零棵或有限棵不相交的樹的集合稱為森林。自然界中樹和森林是不同的概念急凰，但在數(shù)據(jù)結(jié)構(gòu)中女仰，樹和森林只有很小的區(qū)別。任何一棵樹香府，刪除根結(jié)點就變成了森林董栽。
樹的表示
話不多說，直接上圖企孩。
樹的基本操作
1）init（t）：初始化一顆空樹t锭碳。
2）root（x）：求結(jié)點x所在樹的根節(jié)點。
3）parent（t勿璃，x）：求樹t中結(jié)點x是雙親結(jié)點擒抛。
4）child（t，x补疑，i）：求樹t中結(jié)點x的第i個孩子結(jié)點歧沪。
5）rightSibling（t，x）：求樹t中結(jié)點x的第一個右邊兄弟結(jié)點莲组。
6）insert（t诊胞，x，i锹杈，s）：把以s為根結(jié)點的樹插入到樹t中作為結(jié)點x的第i棵子樹撵孤。
7）delete（t，x竭望，i）：在樹t中刪除結(jié)點x的第i棵子樹邪码。
8）tranverse（t）：樹的遍歷操作，即按某個方式訪問樹t中的每個結(jié)點咬清，且使每個結(jié)點只被訪問一次闭专。
樹的存儲
樹的存儲有多種方式奴潘，既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)影钉，但無論采用哪種存儲方式画髓，都要求存儲不但能夠存儲各結(jié)點本身的數(shù)據(jù)，還要能唯一地反映樹中各結(jié)點之間的邏輯關(guān)系斧拍，每種存儲方式都各有各的有點雀扶。常見的存儲方法有以下幾種。
1）雙親鏈表存儲方法
由樹的定義可以知道肆汹，樹中的每個節(jié)點都有唯一的一個雙親結(jié)點，根據(jù)這個特性予权，可以用一組連續(xù)的存儲空間存儲樹中的各個結(jié)點昂勉，每個節(jié)點除了存放本身的信息外還有其雙親結(jié)點存儲位置，樹的這種存儲方法稱為雙親鏈表表示法扫腺，如下所示岗照。
當(dāng)算法中需要在樹結(jié)構(gòu)中頻繁地查找某結(jié)點的父結(jié)點或者根節(jié)點時，使用雙親表示法最合適笆环。當(dāng)頻繁地訪問結(jié)點的孩子結(jié)點時攒至，雙親表示法就很麻煩，采用孩子鏈表表示法就很簡單躁劣。
2）孩子鏈表表示法
樹中每一個數(shù)據(jù)元素對應(yīng)一個結(jié)點迫吐，結(jié)點中有兩部分信息，一部分是其本身的數(shù)據(jù)信息账忘，另一部分是其孩子鏈表的頭指針志膀，即將每個數(shù)據(jù)元素的孩子們鏈接成一個孩子鏈表，將鏈表的頭指針和它們的雙親信息組成了一個結(jié)點鳖擒，再將這些結(jié)點順序存儲起來溉浙。
在用孩子鏈表方法存儲的樹中，查找雙親比較困難蒋荚，查找孩子卻十分方便戳稽，所以比較適用于對孩子操作多的應(yīng)用。由于前兩種表示法都有局限性期升，于是結(jié)合前兩種表示法惊奇，衍生出了雙親孩子鏈表表示法，優(yōu)點不言而喻了吓妆，具體存儲方法如下圖所示赊时。
3）孩子兄弟鏈表存儲方法
這是一種常用的存儲結(jié)構(gòu)。其方式是：在樹中每個元素對應(yīng)一個結(jié)點行拢，每個結(jié)點除其信息域外祖秒，有兩個指針，分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點。
仔細(xì)觀察不難發(fā)現(xiàn)竭缝，通過孩子兄弟鏈表存儲方法房维，普通樹轉(zhuǎn)化為了二叉樹，所以孩子兄弟表示法又被稱為“二叉樹表示法”或者“二叉鏈表表示法”抬纸。
樹的基本知識就介紹到這咙俩，下一篇將介紹樹和森林與二叉樹之間的轉(zhuǎn)換規(guī)則，樹和森林的遍歷方式湿故，以及對應(yīng)的算法實現(xiàn)阿趁。
