C++ 類與指針實現二叉樹：從定義到遍歷完整指南

二叉樹定義與性質

• 每個節點至多兩棵子樹（左/右），順序固定。
• 性質：第 i 層最多 2^{i-1} 個節點；深度 k 的樹最多 2^k-1 個節點；葉子數 = 度為 2 的節點數 + 1。
• 完全二叉樹：除最後一層外每層滿，最後一層靠左排列。

鏈式存儲結構

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

n 個節點的二叉鏈表含 n+1 個空鏈域。

三種遞歸遍歷

// 先序：根 → 左 → 右
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << ' ';
    preorder(root->left);
    preorder(root->right);
}

// 中序：左 → 根 → 右
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << ' ';
    inorder(root->right);
}

// 後序：左 → 右 → 根
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << ' ';
}

封裝類實現

class BinaryTree {
    TreeNode* root;
public:
    BinaryTree() : root(nullptr) {}
    void insert(int val) { // BST 插入示例
        TreeNode** cur = &root;
        while (*cur) {
            if (val < (*cur)->val) cur = &(*cur)->left;
            else cur = &(*cur)->right;
        }
        *cur = new TreeNode(val);
    }
    void preOrder() { preorder(root); cout << endl; }
    void inOrder() { inorder(root); cout << endl; }
    void postOrder() { postorder(root); cout << endl; }
    int countNodes(TreeNode* n) { return n ? countNodes(n->left)+countNodes(n->right)+1 : 0; }
    int countLeaves(TreeNode* n) { return n ? (n->left||n->right ? countLeaves(n->left)+countLeaves(n->right) : 1) : 0; }
    // ... 其他操作
};

非遞歸遍歷（棧模擬）

中序非遞歸為例：

void inorderIter(TreeNode* root) {
    stack st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        cout << cur->val << ' ';
        cur = cur->right;
    }
}

應用場景

• 表達式樹（中序輸出中綴，後序輸出後綴）。
• 二叉搜索樹（中序有序）。
• 哈夫曼樹（帶權路徑長度最短）。