43. 請問使用三個節點（Node）可以建立幾種二元樹（Binary tree）？
(A) 1 種
(B) 8 種
(C) 4 種
(D) 5 種

電腦科學中，計算給定節點數可以建立多少種不同的二元樹（Binary tree）形狀是一個經典問題，其答案由**卡特蘭數（Catalan numbers）**給出。

對於 n 個節點，可以建立的不同二元樹的數量由第 n 個卡特蘭數 C_n 表示。其公式為： C_n=frac1n+1binom2nn=frac(2n)(n+1)n

在這個問題中，我們有三個節點，所以 n=3。

讓我們計算 C_3： C_3=frac13+1binom2times33 C_3=frac14binom63

首先計算組合數 binom63： binom63=frac63(6−3)=frac633=frac6times5times4times3times2times1(3times2times1)(3times2times1)=frac7206times6=frac72036=20

然後將結果代回卡特蘭數公式： C_3=frac14times20 C_3=5

因此，使用三個節點可以建立 5 種不同的二元樹。

這 5 種不同的二元樹結構如下圖所示：

1. 左傾斜樹 (Left-skewed tree)

   根 / 節點 / 節點

2. 根節點有左子樹，左子樹有右子樹

   根 / 節點 \ 節點

3. 根節點有左右子樹（完整二元樹形狀）

   根 / \ 節點 節點

4. 根節點有右子樹，右子樹有左子樹

   根 \ 節點 / 節點

5. 右傾斜樹 (Right-skewed tree)

   根 \ 節點 \ 節點

所以，正確答案是 5 種。