一 、樹是什麼？

1.1 樹的基本概念

• 樹(Tree) 是n （n>=0）個結點的有限集。
• n=0 時稱爲空樹。
• 在任意一顆非空樹中 :

1. 有且僅又一個特定的成爲根（root）的節點
2. 當 n>1 是其餘節點可分爲m（m>0）個互不相交的有限集T1、T2、...... 、Tm ,其中每一個集合本身又是一顆樹，並且成爲根的子樹（SubTree）

                              

圖 6-2-1 中的子樹T1 和子樹T2 就是根節點A 的子樹 。

 

• n>0時，根結點是唯一的，不可能存在多個根結點，別和現實中的大樹混在一現實中的樹有很多根鬚，那是真實的樹，數據結構中的樹是隻能有一個根結點。
• m>0 時，子樹的個數沒有限制，但他們一定是互不相交的。

1.2 樹的節點定義？

• 樹的結點包含一個數據元素及若干指向其子樹的分支。結點擁有的子樹數稱爲結點的度(Degree)。

1. 度爲0的結點稱爲葉結點（leaf）或終端結點.度不爲0的結點稱爲非終端結點或分支結點。
2. 除根結點之外，分支結點也稱爲內部結點。樹的度是樹內各結點的度的最大值。如圖b-2-4所示，因爲這棵樹結點的度的最大值是結點D的度，爲3,所以樹的度也爲3。

1.2 樹的節點間的關係是什麼？

• 節點的子樹的根是該節點的孩子（child）,相應地，該節點稱爲孩子的雙親（parent） 。
• 同一個雙親的孩子之間互成爲兄弟（Sibling）。
• 結點的祖先是從根到該節點所經分支上的所有及節點。
• 以某節點爲根的子樹中的任一節點都成爲該節點的子孫。

     如圖 6-2-5所示

1.4 樹的其他相關概念

• 線性結構與樹結構比較：

 

二、樹的存儲結構是怎樣的？

三種表示方法：雙親表示法、孩子表示法、孩子兄弟表示法

2.1 雙親表示法

2.2 孩子表示法

孩子表示法產生前奏：

在孩子表示法產生之前，由於樹中每個結點可能有多顆子樹，可以考慮用多重鏈表，即每個結點有多個指針域，其中每個指針指向一顆子樹的根結點，我們把這種方法叫做多重鏈表表示法。不過，樹的每個結點的度，也就是它的孩子個數是不同的。所以可以設計兩種方案來解決

• 方案一：

存在缺陷：有很多節點的指針域是空的，浪費了大量空間。

•   方案二

 

存在缺陷：各個節點的鏈表結構並不一致，在運算上會消耗過多時間。

孩子表示法：把每個結點的孩子結點排列起來，以單鏈表作存儲結構，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表爲空。然後n個頭指針又組成一個線性表，採用順序存儲結構，存放進一個一維數組中，如圖6-4-4所示

雙親孩子表示法 ：

將雙親與孩子結構結合到表中

2.3 孩子兄弟表示法