如何用C++遞歸算法實現樹的遍歷

在C++中，使用遞歸算法實現樹的遍歷有三種主要方法：前序遍歷（Pre-order Traversal）、中序遍歷（In-order Traversal）和后序遍歷（Post-order Traversal）。這里給出一個簡單的二叉樹結構以及相應的遞歸遍歷實現。

首先，定義一個二叉樹節點結構體：

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

接下來，實現遞歸遍歷：

1. 前序遍歷（Pre-order Traversal）：根節點 -> 左子樹 -> 右子樹

void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

2. 中序遍歷（In-order Traversal）：左子樹 -> 根節點 -> 右子樹

void inOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

3. 后序遍歷（Post-order Traversal）：左子樹 -> 右子樹 -> 根節點

void postOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    cout << root->val << " ";
}

以上代碼中，我們使用了遞歸的方式實現了二叉樹的前序、中序和后序遍歷。在主函數中，可以創建一個二叉樹并調用相應的遍歷函數進行測試。