樹作為圖的一種特殊形式

2.1 樹的基本組成部分

樹 是一種特殊的圖，它是 無環的 和 連通的。在樹中，任何兩個節點之間只有唯一的路徑，使其結構變得 階層式。

樹的基本組成部分：

1. 節點：

• 樹的基本元素，包含數據。
• 例如，圖中的每個圓圈代表一個節點。

2. 根節點：

• 沒有父節點的節點。它是樹的起點。
• 例如，圖中的頂部節點。

3. 葉子：

• 沒有子節點的節點。它們位於樹的“末端”。
• 例如，圖下方的節點。

4. 邊：

• 節點之間的連接。它們定義了節點之間的父子關係。
• 例如，圖中連接節點的線。

5. 子樹：

• 由一個節點及其所有後代組成的任何樹的子集。
• 例如，從一個節點發出的樹的分支。

樹的重要特徵：

1. 樹的高度：

• 從根到最遠葉子的路徑長度。
• 例如，圖中的層數。

2. 節點的深度：

• 從根節點到指定節點的路徑長度。
• 例如，從根到特定節點的層數。

2.2 二叉樹

不同類型的樹可以被區分。我們從最簡單的開始。

二叉樹 是每個節點最多有兩個子節點的樹，稱為左和右子節點。

二叉樹示例：

特別類型的二叉樹：

完全二叉樹：

除了最後一層外，樹的所有層都完全填滿，且最後一層的所有節點盡可能地靠左排列。

完美二叉樹：

所有內部節點都有正好兩個子節點，所有葉子在同一層。

平衡二叉樹：

任何節點的子樹高度差不超過1。

二叉搜尋樹：

對於任何節點，其左子樹只包含小於該節點的值，右子樹只包含大於該節點的值。

2.3 n階樹

n階樹是每個節點最多可以有 n 個子節點的樹。

特別類型的 n階樹：

1. 三叉樹 (Ternary Tree)：

每個節點最多有三個子節點。

2. k階樹 (k-ary Tree)：

每個節點最多有 k 個子節點。

三叉樹示例（每個節點最多有三個子節點）：

2.4 樹的應用示例

1. 文件系統

樹的應用：在操作系統中表示文件和文件夾的層次結構。

根節點表示根目錄，內部節點表示文件夾，葉子表示文件。操作包括創建、刪除和移動文件和文件夾。

2. 決策樹

樹的應用：用于決策的分析和機器學習。

內部節點表示問題或條件，分支表示可能的回應，葉子表示最終的決策或行動。例如，基於症狀的醫療診斷。

3. XML/HTML 文檔

樹的應用：以 XML 或 HTML 格式的結構化數據表示。

根節點表示整個文檔，內部節點表示標籤和元素，葉子表示文本節點和屬性。這有助於解析和操控文檔內容。

4. 組織結構

樹的應用：表示組織和公司中的層次結構。

根節點表示首席執行官，內部節點表示經理和部門，葉子表示員工。這有助於可視化和管理組織結構。

5. 西洋棋遊戲

樹的應用：表示遊戲中的可能步驟。

根節點表示遊戲的初始狀態，內部節點表示可能的步驟，葉子表示遊戲的最終狀態。這有助於規劃策略和在西洋棋程序中做出決策。