從一條線到一根枝
陣列、鏈結串列、堆疊、佇列——到目前為止每一種結構都是線性的：每個元素後面最多只有一個元素。但現實裡許多東西並不排成一隊。一個資料夾裝著好幾個資料夾，每個裡面又裝著更多。公司的組織架構有一個老闆，下面是幾名直接下屬，再下面是他們的下屬。一本書分成章，章又分成節。這一切底下的形狀，就是 [[tree|樹]]：一個節點指向好幾個*孩子*，而每個孩子本身又是一棵更小的樹的頂端。
注意計算機科學裡這個有趣的顛倒：我們把樹畫成倒過來的。那個唯一的起點節點坐在最上面，叫作根；枝條朝*下*生長，伸向葉子。就是這樣——樹不過是用邊連起來的一堆節點，頂上有一個特殊節點，而且任何地方都沒有環（順著邊往下走，你永遠回不到出發點）。
(1) <- root
/ \
(2) (3)
/ \ \
(4) (5) (6) <- leaves: 4, 5, 6
edges go DOWNWARD; 1 is the parent of 2 and 3.你會用到的詞
樹自帶一套小小的親屬詞彙，值得現在就釘牢，因為後面每一篇導讀都要靠它。
- 根 — 頂端那個唯一的節點，是唯一沒有父節點的。
- 父 / 子 — 若有一條邊從 A 向下連到 B，則 A 是 B 的*父*，B 是 A 的*子*。除根以外，每個節點都恰好有一個父節點。
- 葉 — 沒有孩子的節點；枝條的末端。
- 節點的深度 — 它距離根有幾條邊（根的深度為 0）。
- 樹的高度 — 它最深那片葉子的深度；整棵樹有幾層那麼高。
二元樹：最多兩個孩子
一般的樹允許一個節點有任意多個孩子，但貫穿這一整級台階的主力是 [[binary-tree|二元樹]]：每個節點最多有兩個孩子，整整齊齊地叫作*左*和*右*。這個俐落的限制讓二元樹既易於儲存，又（如後面幾篇所示）在查找和排優先級上強得驚人。在 C++ 裡，一個節點不過是個小小的結構體，裝著一個值和兩個指針——而某個孩子是 `nullptr`，只表示「這邊沒有枝」。
struct Node {
int value;
Node* left = nullptr; // child on the left, or nullptr
Node* right = nullptr; // child on the right, or nullptr
};
// build a tiny tree: (1)
// / \
// (2) (3)
Node* root = new Node{1};
root->left = new Node{2};
root->right = new Node{3};用遞迴走遍這棵樹
你要怎麼*訪問樹裡的每一個節點*？這正是上一級學的 [[dsa-recursion|遞迴]] 大放異彩的地方。關鍵洞見：二元樹本身就是*遞迴定義*的——它是一個節點，加上一棵左子樹，加上一棵右子樹，而每棵子樹本身又是一棵二元樹。於是程式碼恰好照著這個形狀寫。要處理一棵樹，你就處理這個節點，再遞迴進入每個孩子；基準情形是空樹（`nullptr`），這時你什麼也不做、直接返回。
唯一要選的，是你*在什麼時候*處理這個節點——相對於它的孩子而言。在孩子之前處理 → *前序*。在左、右之間 → *中序*。在兩個孩子之後 → *後序*。同樣的三行，只是換了順序——而每種順序各有用處（下一篇你會看到，中序能把一棵搜索樹按有序讀出來）。
void inOrder(Node* n) {
if (n == nullptr) return; // base case: empty subtree
inOrder(n->left); // 1. all of the left subtree
std::cout << n->value << ' '; // 2. then THIS node
inOrder(n->right); // 3. then all of the right subtree
}
// pre-order: visit node BEFORE the two recursive calls
// post-order: visit node AFTER the two recursive calls
// for the tree (2) in-order -> 1 2 3
// / \ pre-order -> 2 1 3
// (1) (3) post-order-> 1 3 2