c++ 先序遍历，中序遍历和后序遍历

在C++中，树和二叉树的遍历有三种基本方式：先序遍历、中序遍历和后序遍历，它们都是用于访问树的所有节点的一种顺序。

1. **先序遍历** (Preorder Traversal):
- 首先访问根节点；
- 然后递归遍历左子树；
- 最后递归遍历右子树。
示例（对于一个二叉树）：`A -> B -> D -> E -> C -> F`（假设根节点为A）

2. **中序遍历** (Inorder Traversal):
- 首先递归遍历左子树；
- 然后访问根节点；
- 最后递归遍历右子树。
示例（对于一个二叉搜索树）：`D -> B -> E -> A -> C -> F`（根节点数值排序后的顺序）

3. **后序遍历** (Postorder Traversal):
- 首先递归遍历左子树；
- 然后递归遍历右子树；
- 最后访问根节点。
示例（对于一个二叉树）：`B -> D -> E -> F -> C -> A`

这三种遍历方式通常通过递归或迭代的方式实现，并通过调用函数来完成对每个节点的访问。递归方法更为简洁直观，但可能会消耗更多的栈空间；而迭代方法则需要维护额外的数据结构，如栈，以保存节点状态。

相关问题

c++先序遍历，中序遍历，后序遍历代码

在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() {
    // 创建一个简单的二叉树
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    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 << "Preorder traversal: ";
    preorderTraversal(root);
    cout << endl;

    cout << "Inorder traversal: ";
    inorderTraversal(root);
    cout << endl;

    cout << "Postorder traversal: ";
    postorderTraversal(root);
    cout << endl;

    // 释放内存（在实际应用中，应当确保完全释放分配的内存）
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

在这个示例中，我们首先定义了一个二叉树节点的结构体`TreeNode`，然后分别实现了三个遍历函数：`preorderTraversal`、`inorderTraversal`和`postorderTraversal`。每个函数都接收一个指向根节点的指针，并递归地访问和打印节点值。

用c++编写二叉树的先序遍历，中序遍历，后序遍历

下面是用C语言实现二叉树的先序遍历、中序遍历和后序遍历的代码：

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建一个新的节点
TreeNode* createNode(int val) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 向二叉树中插入一个节点
TreeNode* insert(TreeNode *root, int val) {
    if (root == NULL) {
        return createNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else if (val > root->val) {
        root->right = insert(root->right, val);
    }
    return root;
}

// 先序遍历
void preorder(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->val);
        preorder(root->left);
        preorder(root->right);
    }
}

// 中序遍历
void inorder(TreeNode *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->val);
        inorder(root->right);
    }
}

// 后序遍历
void postorder(TreeNode *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->val);
    }
}

int main() {
    TreeNode *root = createNode(5);
    insert(root, 2);
    insert(root, 8);
    insert(root, 1);
    insert(root, 3);
    insert(root, 6);
    insert(root, 9);

    printf("先序遍历：");
    preorder(root);
    printf("\n");

    printf("中序遍历：");
    inorder(root);
    printf("\n");

    printf("后序遍历：");
    postorder(root);
    printf("\n");

    return 0;
}

以上代码运行结果为：

先序遍历：5 2 1 3 8 6 9 
中序遍历：1 2 3 5 6 8 9 
后序遍历：1 3 2 6 9 8 5