c++中如何遍历二叉树_c++二叉树遍历方法-C++-PHP中文网

c++中如何遍历二叉树_c++二叉树遍历方法

裘德小鎮的故事

发布： 2025-09-28 09:44:02

原创

1024人浏览过

C++中二叉树遍历有四种主要方式：1. 前序遍历（根-左-右），递归或栈实现；2. 中序遍历（左-根-右），常用于BST获取有序序列；3. 后序遍历（左-右-根），适用于释放内存；4. 层序遍历（广度优先），使用队列按层访问节点。

c++中如何遍历二叉树_c++二叉树遍历方法

在C++中，二叉树的遍历主要有四种常见方式：前序遍历、中序遍历、后序遍历和层序遍历（广度优先）。每种遍历方式访问节点的顺序不同，适用于不同的场景。下面详细介绍这些方法的实现。

1. 二叉树节点定义

在开始遍历之前，先定义一个基本的二叉树节点结构：

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

2. 前序遍历（根-左-右）

前序遍历先访问根节点，然后递归地遍历左子树，最后遍历右子树。

递归实现：

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

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

迭代实现（使用栈）：

立即学习“C++免费学习笔记（深入）”；

void preorderIterative(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        cout << node->val << " ";
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
}

3. 中序遍历（左-根-右）

中序遍历常用于二叉搜索树，可以得到有序序列。

递归实现：

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

迭代实现：

void inorderIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* curr = root;
    while (curr || !stk.empty()) {
        while (curr) {
            stk.push(curr);
            curr = curr->left;
        }
        curr = stk.top();
        stk.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

4. 后序遍历（左-右-根）

后序遍历在删除节点或释放内存时很有用。

递归实现：

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

迭代实现（双栈法）：

void postorderIterative(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> stk1, stk2;
    stk1.push(root);
    while (!stk1.empty()) {
        TreeNode* node = stk1.top();
        stk1.pop();
        stk2.push(node);
        if (node->left) stk1.push(node->left);
        if (node->right) stk1.push(node->right);
    }
    while (!stk2.empty()) {
        cout << stk2.top()->val << " ";
        stk2.pop();
    }
}

5. 层序遍历（从上到下，从左到右）

层序遍历使用队列实现，适合按层级处理节点。

void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

基本上就这些。根据实际需求选择合适的遍历方式，递归写法简洁易懂，迭代写法更节省系统栈空间。不复杂但容易忽略细节，比如空指针判断和入栈顺序。

以上就是c++++中如何遍历二叉树_c++二叉树遍历方法的详细内容，更多请关注php中文网其它相关文章！