c++ 先序中序后序遍历

在C++中，树的先序遍历（前序遍历）、中序遍历和后序遍历是三种基本的遍历方法，它们分别对应于在访问节点和子树时的不同顺序。

1. 先序遍历（Preorder Traversal）：先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。遍历顺序为：根 -> 左 -> 右。

2. 中序遍历（Inorder Traversal）：首先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。遍历顺序为：左 -> 根 -> 右。

3. 后序遍历（Postorder Traversal）：首先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。遍历顺序为：左 -> 右 -> 根。

下面是三种遍历方法的C++代码示例：

#include <iostream>
using namespace std;

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

// 先序遍历
void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val << " ";
}

int main() {
    // 构建一棵树作为示例
    TreeNode *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);

    cout << "先序遍历结果: ";
    preorderTraversal(root);
    cout << endl;

    cout << "中序遍历结果: ";
    inorderTraversal(root);
    cout << endl;

    cout << "后序遍历结果: ";
    postorderTraversal(root);
    cout << endl;

    // 注意：这里没有释放树节点所占用的内存，实际使用时应避免内存泄漏
    return 0;
}