C++二叉樹課程設計：前中後序遍歷、葉子節點統計、節點總數與深度計算

需求分析

實現二叉樹基本操作：

• 三種深度優先遍歷：前序、中序、後序
• 統計葉子節點數
• 統計總節點數
• 計算樹的深度（高度）

核心代碼實現

#include <iostream>
using namespace std;

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

class BinaryTree {
public:
    TreeNode* root;

    BinaryTree() : root(nullptr) {}

    // 1. 前序遍歷：根 -> 左 -> 右
    void preOrder(TreeNode* node) {
        if (!node) return;
        cout << node->val << " ";
        preOrder(node->left);
        preOrder(node->right);
    }

    // 2. 中序遍歷：左 -> 根 -> 右
    void inOrder(TreeNode* node) {
        if (!node) return;
        inOrder(node->left);
        cout << node->val << " ";
        inOrder(node->right);
    }

    // 3. 後序遍歷：左 -> 右 -> 根
    void postOrder(TreeNode* node) {
        if (!node) return;
        postOrder(node->left);
        postOrder(node->right);
        cout << node->val << " ";
    }

    // 4. 統計葉子節點（左右子樹均為空）
    int countLeaves(TreeNode* node) {
        if (!node) return 0;
        if (!node->left && !node->right) return 1;
        return countLeaves(node->left) + countLeaves(node->right);
    }

    // 5. 統計總節點數
    int countNodes(TreeNode* node) {
        if (!node) return 0;
        return 1 + countNodes(node->left) + countNodes(node->right);
    }

    // 6. 計算樹的深度（根深度為1）
    int maxDepth(TreeNode* node) {
        if (!node) return 0;
        return 1 + max(maxDepth(node->left), maxDepth(node->right));
    }

    // 測試構建示例樹
    void buildSample() {
        root = new TreeNode(1);
        root->left = new TreeNode(2);
        root->right = new TreeNode(3);
        root->left->left = new TreeNode(4);
        root->left->right = new TreeNode(5);
        root->right->right = new TreeNode(6);
    }
};

int main() {
    BinaryTree tree;
    tree.buildSample();

    cout << "前序: "; tree.preOrder(tree.root); cout << endl;
    cout << "中序: "; tree.inOrder(tree.root); cout << endl;
    cout << "後序: "; tree.postOrder(tree.root); cout << endl;
    cout << "葉子數: " << tree.countLeaves(tree.root) << endl;
    cout << "總節點: " << tree.countNodes(tree.root) << endl;
    cout << "樹深度: " << tree.maxDepth(tree.root) << endl;
    return 0;
}

輸出結果

前序: 1 2 4 5 3 6
中序: 4 2 5 1 3 6
後序: 4 5 2 6 3 1
葉子數: 3
總節點: 6
樹深度: 3

遞歸與非遞歸對比

上述為遞歸實現，簡潔易懂。大數據量時可改用棧模擬非遞歸避免棧溢出。課程設計通常要求同時實現兩種方式並分析時空複雜度。