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

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

尼克

发布： 2025-10-15 14:43:01

原创

219人浏览过

答案是递归和迭代两种方法均可实现C++中二叉树的中序遍历。递归法按“左-根-右”顺序访问节点，代码简洁；迭代法利用栈模拟调用过程，避免栈溢出风险。两者均能正确输出中序序列4 2 5 1 3。

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

在C++中实现二叉树的中序遍历，主要有两种方法：递归和迭代。中序遍历的顺序是“左子树 → 根节点 → 右子树”，常用于二叉搜索树（BST）中获取有序序列。

定义二叉树节点结构

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

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

登录后复制

方法一：递归实现中序遍历

递归是最直观、最常用的方式。只需要按照“左-根-右”的顺序访问节点。

void inorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) return;
<pre class='brush:php;toolbar:false;'>inorderTraversalRecursive(root->left);  // 遍历左子树
<strong>std::cout << root->val << " ";</strong>      // 访问根节点
inorderTraversalRecursive(root->right); // 遍历右子树

登录后复制

}

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

调用方式：inorderTraversalRecursive(root);

方法二：迭代实现中序遍历（使用栈）

迭代方式利用栈模拟系统调用栈的行为，适合不想使用递归或担心栈溢出的场景。

百度文心百中

百度大模型语义搜索体验中心

查看详情

#include <stack>
#include <iostream>
<p>void inorderTraversalIterative(TreeNode<em> root) {
std::stack<TreeNode</em>> stk;
TreeNode* curr = root;</p><pre class='brush:php;toolbar:false;'>while (curr != nullptr || !stk.empty()) {
    // 一直向左走，将路径上的节点入栈
    while (curr != nullptr) {
        stk.push(curr);
        curr = curr->left;
    }

    // 当前为空，从栈顶取出节点并访问
    curr = stk.top();
    stk.pop();
    <strong>std::cout << curr->val << " ";</strong>  // 访问当前节点

    // 转向右子树
    curr = curr->right;
}

登录后复制

}

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