樹：計算機科學中的重要概念#

在計算機科學中，樹是一種抽象的數據結構，模仿自然界中樹的特點——有根、有枝幹、有末端的葉子。

樹的嚴格定義（遞歸定義）#

• 一個單獨的節點本身是一棵樹
• 任何一棵樹都有一個根節點，根節點下面有一些子樹，每棵子樹也是一棵樹，這些子樹的根節點是整棵樹根節點的子節點

樹的基本術語#

• 度（Degree）：一個節點的子節點數量
• 葉節點：沒有子樹的節點（度為 0）
• 父節點與子節點：若節點 x 是節點 y 的子節點，則 y 是 x 的父節點
• 祖先與後代：父節點和子節點的推廣

樹的三個重要特徵#

1. 每個節點有唯一的父節點（根節點除外）
2. 連通性：樹內部的節點通過子節點和父節點的關係彼此相連
3. 不帶有環：這是由父節點唯一性保證的

2.2.1 二叉樹及其遍歷#

二叉樹是計算機算法中最常用的一種特殊的樹——每個節點的子樹不超過兩棵（左子樹和右子樹）。

為什麼二叉樹用得最多？#

• 結構簡單，子節點少
• 符合日常的邏輯判斷（是/否、左/右）
• 符合計算機的二進制

二叉樹的遞歸定義#

1. 一個空節點是一棵二叉樹
2. 一棵二叉樹有一個根節點，根節點可以有左、右子樹，而子樹本身也是二叉樹

任何樹和二叉樹都是等價的，可以互相轉化（詳見附錄三）。

二叉樹的遍歷方法#

深度優先遍歷（Depth First）——沿著一條路走到底，再回頭：

• 三條簡單規則：
  1. 從上到下順序訪問
  2. 先左後右（或先右後左）
  3. 走到盡頭就掉頭
• 根據處理根節點的時機不同，分為：
  • 先序遍歷：先處理根節點，再遍歷左、右子樹
  • 中序遍歷：先遍歷左子樹，再處理根節點，最後遍歷右子樹
  • 後序遍歷：先遍歷左、右子樹，最後處理根節點

廣度優先遍歷（Breadth First）——一層一層橫向掃描：

• 將二叉樹從上到下分層，逐層掃描
• 每一層從左到右掃描

2.2.2 使用遞歸思想實現二叉樹的遍歷#

深度優先遍歷的遞歸實現非常簡潔：

DepthFirstTraverseTree(BinaryTree tree) {
    if (tree = NIL) return;  // 空樹直接返回
    DepthFirstTraverseTree(tree.left_subtree);   // 遍歷左子樹
    PrintNode();  // 處理當前節點
    TraverseTree(tree.right_subtree);  // 遍歷右子樹
}

如果你接受了遞歸的思維方式，就會覺得深度優先遍歷非常簡單。但如果停留在由淺入深的循環思維方式上，這個算法理解起來會有點困難。要想在計算機科學領域做到隨心所欲，必須轉換思維方式。

程序的執行過程#

• 算法實際上是層層調用，從根節點開始，一直走到葉節點
• 到達葉節點後再逐一返回，直到根節點
• 這個過程需要一個特殊的數據結構來支撐——堆棧

要點回顧#

• 樹是計算機科學中非常重要的數據結構，其嚴格定義本身就是遞歸的
• 二叉樹是最常用的樹結構，遍歷算法是最基本、最重要的操作
• 深度優先遍歷用遞歸實現極為簡潔