非递归实现：二叉树先序遍历的栈结构详解

本文将详细介绍二叉树先序遍历的非递归算法实现及其原理。在传统的递归方法之外，非递归算法通常利用数据结构中的栈来模拟递归过程。二叉树的先序遍历顺序是：先访问根节点，然后遍历左子树，最后遍历右子树。以下是算法的核心步骤： 1. 入栈操作：首先将根节点压入栈中，这样栈顶总是指向待访问的节点。然后调用访问函数（如`VisitNode`）处理当前节点。 2. 循环遍历：使用一个`while`循环，当栈不为空时，持续执行以下操作： - 取出栈顶节点，并访问其数据。 - 将当前节点（除了根节点）压入栈，确保左子树被遍历。 - 将当前节点设置为其左子节点，准备处理左子树。 3. 结束条件判断：当左子树遍历完成后，检查右子节点是否存在。如果右子节点存在，继续按步骤1执行；若不存在，则从栈中弹出节点，进入父节点的遍历过程，即返回到上一层，直到遇到下一个非空子节点或栈为空。 然而，原始给出的代码中存在一个错误。在判断右子节点是否为空时，作者在`Pop`操作后直接检查`pBiNode->rchild==NULL`，这可能导致问题。因为在`Pop`操作后，栈可能已经为空，这时直接访问`pBiNode->rchild`可能会导致未定义的行为。正确的做法是在`Pop`操作后，先判断栈是否为空，只有在栈不为空的情况下再进行右子节点的检查。 修正后的代码可能如下所示： ```cpp //... while (!IsStackEmpty(S)) { while (pBiNode) { VisitNode(pBiNode->data); if (pBiNode != T) { Push(&S, (SElemType)pBiNode); } pBiNode = pBiNode->lchild; } if (!IsStackEmpty(S)) { // 修改1：先判断栈是否为空 Pop(&S, (SElemType*)&pBiNode); if (pBiNode->rchild == NULL) { // 修改2：检查右子节点之前先确保栈非空 Pop(&S, (SElemType*)&pBiNode); } } pBiNode = pBiNode->rchild; } ``` 通过以上修改，非递归的二叉树先序遍历算法就能正确地按照先根（根-左-右）的顺序遍历整个二叉树。理解这种算法的关键在于掌握如何用栈模拟递归调用的过程，以及在遍历过程中处理好栈的空与满状态。