C++怎么实现二叉树的遍历_C++数据结构与二叉树遍历算法-C++-PHP中文网

C++怎么实现二叉树的遍历_C++数据结构与二叉树遍历算法

穿越時空

发布： 2025-11-18 05:09:24

原创

850人浏览过

二叉树遍历包括前序、中序、后序和层序四种，可通过递归或迭代实现。前序遍历先访问根节点，再左子树、右子树；中序是左→根→右；后序为左→右→根；层序按层级从上到下、每层从左到右访问节点。递归实现简洁直观，迭代则借助栈或队列模拟过程，其中前序迭代使用栈并优先压入右子树，中序持续向左入栈后回退访问，后序较复杂需标记已访问节点或双栈辅助，层序遍历利用队列实现，可记录每层节点数以分行输出。

c++怎么实现二叉树的遍历_c++数据结构与二叉树遍历算法

二叉树的遍历是数据结构中的基础操作，C++中可以通过递归或迭代的方式实现。常见的遍历方式有三种：前序、中序和后序，再加上层序遍历，共四种。下面详细介绍每种遍历的实现方法。

前序、中序、后序遍历（递归实现）

定义二叉树节点结构后，递归遍历非常直观。顺序区别在于“根”的处理时机：

前序遍历：先访问根节点，再遍历左子树，最后右子树（根→左→右）
中序遍历：先遍历左子树，再访问根节点，最后右子树（左→根→右）
后序遍历：先遍历左子树，再右子树，最后访问根节点（左→右→根）

代码示例：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
<p>// 前序遍历
void preorder(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}</p><p>// 中序遍历
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}</p><p>// 后序遍历
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}</p>

登录后复制

前中后序遍历（迭代实现）

使用栈模拟递归过程，可以避免函数调用开销，也便于理解执行流程。

立即学习“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);
    }
}

登录后复制

中序迭代：

宣小二

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

查看详情

一直向左走到底，路径上节点入栈，到空时回退并访问，再转向右子树。

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;
    }
}

登录后复制

后序迭代：

较复杂，可借助两个栈，或使用一个栈配合“上次访问节点”标记。

void postorderIterative(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> stk;
    TreeNode* lastVisited = nullptr;
    TreeNode* curr = root;
    while (curr || !stk.empty()) {
        if (curr) {
            stk.push(curr);
            curr = curr->left;
        } else {
            TreeNode* peekNode = stk.top();
            if (peekNode->right && lastVisited != peekNode->right) {
                curr = peekNode->right;
            } else {
                cout << peekNode->val << " ";
                lastVisited = stk.top(); stk.pop();
            }
        }
    }
}

登录后复制

层序遍历（广度优先）

使用队列实现，按层级从上到下、从左到右访问节点。

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);
    }
}

登录后复制

若需按层输出（每层一行），可在循环内记录当前层节点数：

void levelOrderPerLevel(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front(); q.pop();
            cout << node->val << " ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << endl; // 每层换行
    }
}

登录后复制

基本上就这些。掌握递归与迭代的写法，能应对大多数面试和工程场景。迭代写法虽然稍复杂，但有助于深入理解遍历逻辑。实际开发中可根据需求选择合适方式。

以上就是C++怎么实现二叉树的遍历_C++数据结构与二叉树遍历算法的详细内容，更多请关注php中文网其它相关文章！