12. 有三個節點的樹，組成二元樹的個數最多為何?
(A) 3
(B) 4
(C) 5
(D) 6

【解題思路】

這題是經典的「有 n 個節點，可以組成幾種不同結構的二元樹？」
這不是排列組合，而是「Catalan（卡特蘭數）」，教材和考試都會考。

二元樹（Binary Tree）不同的「結構」數量，用 Catalan 公式：

Cₙ = (1 / (n+1)) × (2n choose n)

但考三個節點不需要公式，因為：

n = 3 時，不同的二元樹結構數＝5

這個結果是經典考點，必背。

【逐一破題（畫出 5 種結構）】

三個節點（不管節點名稱），最多可以組成以下 5 種不同二元樹：

類型 1：完全向左傾

ㅤㅤ

類型 2：完全向右傾

ㅤㅤ

類型 3：根有左子、左子有右子

ㅤㅤ

類型 4：根有右子、右子有左子

ㅤㅤ

類型 5：根有左右兩子（左右子樹都是 1 節點）

ㅤㅤ

總共：5 種

【為什麼其他選項不正確（逐一破題）】

(A) 3
→ 太少，三個節點可以組更多結構。

(B) 4
→ 也不夠，經典 Catalan n=3 的結果是 5。

(C) 5
→ 正確答案。

(D) 6
→ 超過可能的最大數量。

【延伸知識】

卡特蘭數（Catalan numbers）前幾項（必背小表）

n=3 時一定是 5，是所有教材、演算法、資料結構書都一致的內容。

【記憶技巧】

一句話：

三節點 → 5 種樹
四節點 → 14 種
Catalan number 必背

【常見錯誤】

1. 以為是 3! 或排列 → 完全不相關

2. 把「不同標號」當成不同結構 → 題目只問「結構」

3. 忘記左右子樹的不同組合也算不同樹