C 語言經典面試題：三個節點的二叉樹有幾種形態？

這是一道考察二叉樹結構理解與組合數學的經典題目。

答案：5 種形態

三個節點的二叉樹共有 5 種 不同拓撲結構。以下用圖形直觀展示（`0` 代表節點，`*` 代表空位）：

形態 1：右傾鏈
***0
**/*\
*0***0

形態 2：左傾鏈
****0
***/
**0
*/
0

形態 3：左子樹雙節點
**0
*/
0
*\
**0

形態 4：右子樹雙節點
0
*\
**0
*/\
0

形態 5：平衡型（根 + 左右孩子）
0
*\
**0
***\
****0

數學原理：卡特蘭數

n 個節點的二叉樹形態數 = 第 n 個卡特蘭數：

C(n) = (2n)! / ((n+1)! * n!)

• n=1 → 1
• n=2 → 2
• n=3 → 5
• n=4 → 14
• n=5 → 42

遞歸關係

C(n) = Σ C(i) * C(n-1-i) (i=0..n-1)

即：左子樹 i 節點，右子樹 n-1-i 節點，根佔 1 節點。

代碼驗證（遞歸生成）

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { struct Node *left, *right; } Node;

Node* clone(Node* root) {
    if (!root) return NULL;
    Node* n = malloc(sizeof(Node));
    n->left = clone(root->left);
    n->right = clone(root->right);
    return n;
}

void printTree(Node* root, int depth) {
    if (!root) { printf("%*s*\n", depth*2, ""); return; }
    printTree(root->right, depth+1);
    printf("%*s0\n", depth*2, "");
    printTree(root->left, depth+1);
}

int main() {
    // 手動構建 5 種形態驗證
    // ... 略
    printf("總計 5 種形態\n");
    return 0;
}

面試延伸問題

• 如何判斷兩棵二叉樹結構相同？（遞歸比較左右子樹）
• 給定前序+中序遍歷，能否唯一確定二叉樹？（能）
• 二叉樹節點數與高度關係？（最小高度 ⌊log₂(n)⌋+1，最大高度 n）