C++如何实现二叉树的非递归中序遍历-C++-PHP中文网

递归虽简洁但禁用因其栈空间不可控、易栈溢出、调试困难；非递归中序遍历通过手动模拟调用栈，以“左路压栈→弹栈访问→右子树推进”实现可预测内存使用与中断安全。

c++如何实现二叉树的非递归中序遍历

为什么不能直接用递归，而要搞非递归

递归写法简洁，但实际项目里常被禁用：栈空间不可控、调试困难、嵌入式或实时系统中可能触发栈溢出。非递归中序遍历本质是手动模拟系统调用栈，核心在于「左路压栈 + 访问 + 右子树推进」——不是为了炫技，而是为了可预测的内存使用和中断安全。

`std::stack` 存什么节点最安全

存 TreeNode*（裸指针）最常用，但前提是能确保生命周期；若节点由智能指针管理（如 std::unique_ptr<treenode></treenode>），必须存 TreeNode* 而非 std::unique_ptr<treenode></treenode>，否则每次出栈会意外触发析构。切忌存引用或值拷贝——二叉树节点通常不含 trivial copy 语义，且体积大。

典型错误现象：use-after-free 或访问野指针，往往源于栈中保存了已移动或已释放的智能指针副本。

实操建议：

统一用原始指针入栈，仅作临时导航，不承担所有权
若用 std::shared_ptr<treenode></treenode>，仍应存 TreeNode*，避免循环引用或意外延长生命周期
初始化栈前确认根节点非空，空指针直接跳过，避免后续解引用崩溃

中序遍历非递归的核心三步怎么拆解

中序顺序是「左 → 根 → 右」，非递归的关键在于：不能等右子树处理完才访问根，而要在从左子树返回时立即访问——这靠「左路探到底 + 弹栈访问 + 切换到右子树」实现。

代码骨架如下（省略模板/命名空间）：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

void inorderTraversal(TreeNode* root) {
    std::stack<treenode> stk;
    TreeNode* curr = root;
    while (curr != nullptr || !stk.empty()) {
        // 1. 一路向左压栈，直到空
        while (curr != nullptr) {
            stk.push(curr);
            curr = curr->left;
        }
        // 2. 弹栈并访问（此时左子树已全处理完）
        curr = stk.top();
        stk.pop();
        visit(curr); // e.g., std::cout val right;
    }
}
</treenode>

常见错误：