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

答案是递归和迭代两种方法均可实现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;
inorderTraversalRecursive(root->left);  // 遍历左子树
std::cout << root->val << " ";      // 访问根节点
inorderTraversalRecursive(root->right); // 遍历右子树
}
立即学习“C++免费学习笔记（深入）”；调用方式：inorderTraversalRecursive(root);
方法二：迭代实现中序遍历（使用栈）
迭代方式利用栈模拟系统调用栈的行为，适合不想使用递归或担心栈溢出的场景。

							
								
								
									GPT Detector
									在线检查文本是否由GPT-3或ChatGPT生成
								
								下载 
							
						
#include 
#include 
void inorderTraversalIterative(TreeNode root) {
std::stack> stk;
TreeNode* curr = root;
while (curr != nullptr || !stk.empty()) {
    // 一直向左走，将路径上的节点入栈
    while (curr != nullptr) {
        stk.push(curr);
        curr = curr->left;
    }

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

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

立即学习“C++免费学习笔记（深入）”；完整示例与输出

构建一个简单二叉树测试：
        1
       / \
      2   3
     / \
    4   5
中序遍历结果应为：4 2 5 1 3
两种方法都能正确输出该序列。
基本上就这些。递归写法简洁易懂，迭代写法更贴近底层逻辑，理解栈的使用有助于掌握其他遍历方式。根据需求选择合适的方法即可。