二元樹

簡介

二元樹 (Binary Tree) 是一種樹狀結構，每個節點最多只能有兩個子節點，分別為左子節點 (Left Child) 與右子節點 (Right Child)。也因為有一些比較特殊的性質，因此特別拿出來介紹。

走訪方式

其中一個特點就是二元樹的 DFS 方式分成前序、中序和後序三種。

前序走訪就是指先處理目前節點然後再拜訪子節點，所以具體來說順序長這樣：

1. 處理目前節點
2. 拜訪左子節點
3. 拜訪右子節點

中序走訪的順序：

1. 拜訪左子節點
2. 處理目前節點
3. 拜訪右子節點

後序走訪的順序：

1. 拜訪左子節點
2. 拜訪右子節點
3. 處理目前節點

現在考慮這張圖，以 1 為根節點開始走訪：

前序走訪的結果是：1 3 4 2 5 7 6
中序走訪的結果是：3 1 4 7 5 2 6
後序走訪的結果是：3 4 7 5 6 2 1

這樣的走訪方式其實也可以套用在一般的樹上（先走訪子節點還是先處理目前節點），不過二元樹的特性讓這些走訪方式更有意義。

陣列中的二元樹

許多資料結構都是二元樹的變化版，因次我們需要知道如何儲存一顆二元樹，雖然可以直接用存圖的作法儲存，但實際上有更方便的作法！

首先我們可以想像一下一顆完美二元樹，根節點的編號是 1，接下來每一層都由左至右從小到大編號：

有發現什麼性質嗎？

可以觀察到，對於任意一個編號 $n$ 的節點：

• 左子節點的編號都是 $2n$
• 右子節點的編號都是 $2n + 1$

於是我們其實可以利用這個性質將二元樹直接存在陣列中！

const MAXN = 2e5 + 10;

int tree[MAXN * 4];

int get_right_child(int n) {
    return n * 2 + 1;
}

int get_left_child(int n) {
    return n * 2;
}

可注意到上面開陣列時我們使用的大小是總節點數量的四倍，這是為了確保存取時不要超出陣列範圍。