樹

【本節僅描述樹的定義、術語以及相關性質】

定義

樹是由若干個結點組成的有限集合。具有如下特征：

1. 有且僅有一個根結點；
2. 除根結點外，每個其它結點有且僅有一個直接的父結點；
3. 除根結點外，每個結點可以有零個或者多個子結點；
4. 結點之間通過邊連接，形成層級關系，且不存在環路。

當有限集合內的元素數大于1時，除根結點外的其余結點可以分為 m(m>0) 個互不相交的有限集，其中每個有限集合本身又是一棵樹，并且稱為根的子樹。

從遞歸角度來看：

• 一棵樹要么是空樹（沒有任何節點）；
• 要么由一個根節點和零個或多個子樹組成，而這些子樹本身又是樹。

術語

根節點 ：樹的起始節點，沒有父節點。

父節點，子節點 ：結點之間的直接上下級關系。

葉節點 ：沒有子節點的結點。葉節點的度為0。

分支節點：有子結點的結點稱為分支結點。度大于0。

度：一個結點的子節點個數。

層次、深度、高度 ：結點的層次從根開始定義，根結點為第1層，它的子結點為第2層，以此類推。結點的深度就是結點所在的層次。樹的高度或深度是樹中結點的最大層數。結點的高度是以該節點為根的子樹的高度。

子樹（subtree） ：以某個結點為根結點的樹。

路徑：樹中兩個結點之間的路徑是由這兩個結點之間所經過的結點序列構成的。

路徑長度：是路徑中所經過的邊的數目（即節點數減一）。

說法	含義
兩結點間的路徑長度	連接兩個結點路徑中的邊數
樹的路徑長度（內部路徑長度）	樹中所有結點到根節點路徑長度的總和
樹的直徑（最大路徑長度）	樹中兩個結點間最長路徑的邊數

樹的性質

1.樹的結點數n等于所有結點的度數之和加1
$$\begin{gathered} 令一棵樹的總結點數為n,那么總度數為n?1,不同度數的結點的數量為n_m,m為度數下標,那么 \\ n=n_0+n_1+n_2+...+n_m=\sum _{i=0}^m{n}_i \\ 再求每個不同度數的結點的總度數為m?n_m,那么 \\ n?1=1n_1+2n_2+3n_3+...+m{n}_m=\sum _{i=1}^{m}i{n}_i \\ 得到:n=\sum _{i=1}^{m}i{n}_i+1=\sum _{i=0}^m{n}_i \end{gathered}$$
由上述推導過程，可以看出，當計算樹的總度數的時候，葉節點（沒有子節點的結點）是沒有貢獻的，因為按照計算公式，葉結點的總度數為0。但是當計算總結點數的時候是有的。所以，可以借助最后推導出的公式來計算葉結點的結點數，計算如下：
$$\begin{gathered} 由于已知:\sum _{i=1}^{m}i{n}_i+1=\sum _{i=0}^m{n}_i \\ 然后對等號右邊部分提取出n_0,得到 \\ \sum _{i=0}^m{n}_i=n_0+\sum _{i=1}^m{n}_i,等效替換回原式得到 \\ \sum _{i=1}^{m}i{n}_i+1=n_0+\sum _{i=1}^m{n}_i \\ 化簡 \\ {n}_0=\sum _{i=1}^{m}i{n}_i?\sum _{i=1}^m{n}_i+1=\sum _{i=1}^m(i?1)n_i+1 \end{gathered}$$
2.度為 m 的樹中第 i 層上至多有m的（i - 1）次方個結點（i ≥ 1）

已知第一層只有一個結點為根結點；那么第2層至多就有 m 個結點，那么第3層至多就有 m2 個結點，歸納推導出
$$第i層的結點數\le m^{i?1},其中(i\ge 1)$$
3.高度為h的m叉樹至多有 (m^h - 1)/(m - 1) 個結點

如果要讓m叉樹的結點數達到最大，那么除第一層外，每層的結點數都應滿足 n_h = m^(h-1)，計算總結點數為
$$N=1+m^1+m^2+m^3+...+m^{h?1}=(m^h?1)/(m?1)$$
4.度為 m，具有 n 個結點的樹的最大高度 h 為 (n - m + 1)

因為已知度為m，那么樹中至少有一個結點的子結點數為m；要為了使樹的高度最大，度為m的結點的子結點位于同一層，其它層則只放置1個結點。

舉例：

1. 根結點 – 度數為1的子結點 – 度數為1的子結點 – … – 度數為m的子結點
2. 根結點 – 度數為1的子結點 – 度數為m的子結點 – … – 度數為1的子結點

5.度為 m、具有 n 個結點的樹的最小高度 h 為[ log_m (n * ( m - 1 ) + 1 ) ]

首先已知：要使一棵樹的高度盡量小，那么每層（除第一層和最后一層）的結點數都應滿足性質2。第一層是根結點，最后一層只要有結點就行，不一定要填滿。

再借助性質3可以推導出：
$$\begin{gathered} 當樹的高度取得最小高度h的時候: \\ 總的結點數 \\ 最多為(m^h?1)/(m?1) \\ 最少為(m^{h?1}?1)/(m?1)+1。 \\ 可得到下列不等式:(m^{h?1}?1)/(m?1)<n\le (m^h?1)/(m?1) \end{gathered}$$
然后要明確，求最小高度的位置應該是結點數最多的位置，防止錯誤的估計高度。因此得到如下臨界狀態
$$\begin{gathered} n=(m^h?1)/(m?1) \\ {h}_{min}是整數,向上取整取最小值，求解得： \\ {h}_{min}=?lo{g}_m(n(m?1)+1)? \end{gathered}$$

**森林中有k顆樹，總結點數為n，總邊數為e，那么 k = n - e。或者說森林中結點數不變，邊數減少 1，則森林中的樹的棵數增加 1 **

在一棵樹中，結點數為 n，邊數必然是 n?1。森林是若干棵樹的集合，因此森林中包含若干棵互不連通的子樹。設森林中結點數為 n，邊數為 e，樹的棵數為 k，則有：樹的棵數 k = n ? e。

推導：
$$\begin{gathered} 每棵樹單獨結點數為n_i，對應邊數為n_i?1 \\ 森林中所有樹的結點數和為:\sum _{i=1}^k{n}_i=n \\ 森林中所有樹的邊數和為:e=\sum _{i=1}^k(n_i?1)=\sum _{i=1}^k{n}_i?k=n?k \\ 所以森林中樹的棵樹k=n?e \end{gathered}$$