樹的介紹

---

---

樹是一種離散結構，它表示各個元素或節點之間層次結構的關係。其中父節點最多隻有兩個子節點的樹稱為二叉樹。

樹及其性質

定義 - 樹是一個連通的無環無向圖。圖G中每對頂點之間都存在唯一路徑。具有N個頂點的樹包含(N-1)條邊。度數為0的頂點稱為樹的根。度數為1的頂點稱為樹的葉子節點，內部節點的度數至少為2。

示例 - 下面是一個樹的例子：

樹的中心和雙中心

樹的中心是具有最小離心率的頂點。樹G中頂點X的離心率是頂點X與樹中任何其他頂點之間的最大距離。最大離心率是樹的直徑。如果一棵樹只有一箇中心，則稱為中心樹；如果一棵樹有多箇中心，則稱為雙中心樹。每棵樹要麼是中心樹，要麼是雙中心樹。

查詢樹的中心和雙中心的演算法

步驟1 - 從給定的樹中刪除所有度數為1的頂點及其關聯邊。

步驟2 - 重複步驟1，直到剩下單個頂點或由一條邊連線的兩個頂點。如果剩下單個頂點，則它是樹的中心；如果剩下由一條邊連線的兩個頂點，則它們是樹的雙中心。

問題1

找出以下樹的中心/雙中心：

解答

首先，我們將刪除所有度數為1的頂點及其關聯邊，得到以下樹：

再次，我們將刪除所有度數為1的頂點及其關聯邊，得到以下樹：

最終我們得到單個頂點“c”，演算法停止。由於只有一個頂點，這棵樹有一箇中心“c”，並且這棵樹是中心樹。

問題2

找出以下樹的中心/雙中心：

解答

首先，我們將刪除所有度數為1的頂點及其關聯邊，得到以下樹：

再次，我們將刪除所有度數為1的頂點及其關聯邊，得到以下樹：

最終，我們剩下兩個頂點“c”和“d”，因此演算法停止。由於剩下由一條邊連線的兩個頂點，這棵樹的雙中心是“cd”，這棵樹是雙中心樹。

帶標籤的樹

定義 - 帶標籤的樹是指其頂點被賦予從1到n的唯一數字的樹。我們可以手動計算n值較小的此類樹的數量，以便推測出一個通式。n個頂點的帶標籤樹的數量為n^n-2。如果兩個帶標籤樹的圖同構，並且兩棵樹的對應點具有相同的標籤，則這兩個帶標籤樹是同構的。

示例

不帶標籤的樹

定義 - 不帶標籤的樹是指其頂點未被賦予任何數字的樹。n個頂點的帶標籤樹的數量為$\frac {(2n)!}{ (n+1)!n! }$（第n個卡塔蘭數）

示例

有根樹

有根樹G是一個連通的無環圖，它有一個特殊的節點，稱為樹的根，並且每條邊都直接或間接地起源於根。有序有根樹是有根樹，其中每個內部頂點的子節點是有序的。如果一個有根樹的每個內部頂點最多有m個子節點，則它被稱為m元樹。如果一個有根樹的每個內部頂點恰好有m個子節點，則它被稱為完全m元樹。如果m=2，則有根樹稱為二叉樹。

二叉搜尋樹

二叉搜尋樹是一種滿足以下性質的二叉樹：

• 頂點V的左子樹中的X，Value(X) ≤ Value(V)
• 頂點V的右子樹中的Y，Value(Y) ≥ Value(V)

因此，內部節點V的左子樹的所有頂點的值都小於或等於V，內部節點V的右子樹的所有頂點的值都大於或等於V。從根節點到最深節點的連結數是二叉搜尋樹的高度。

示例

在BST中搜索鍵的演算法

BST_Search(x, k) 
if ( x = NIL or k = Value[x] ) 
   return x; 
if ( k < Value[x]) 
   return BST_Search (left[x], k); 
else  
   return BST_Search (right[x], k)  

二叉搜尋樹的複雜度