二叉树的非递归遍历里的栈存在的意义是什么

Question

  
void PreOrderNoRec (BinTree BT) 
{  stack S;  BinTree p=BT->root;
   while ((p != NULL) || !StackEmpty(S))
  { if (p!=NULL)                       
      { printf (“%c”, p->data);  /*访问当前结点*/
       Push (S,p);  /*将p压入栈S*/
       p = p->lchild; }  /*将p指向其左子树*/
    else 
       { p = Top(S); 
        Pop(S);  /*从栈S弹出栈顶元素*/
        p = p->rchild; }  /*将p指向其右子树*/
    }
}

二叉树的非递归遍历中，不是很理解算法里的栈存在的意义是什么，因为最后节点访问顺序的输出是靠printf

Answer 1

在二叉树的非递归遍历算法中，使用栈来辅助遍历的过程。栈的作用主要体现在两个方面：

保存访问过的节点：在遍历二叉树时，需要将已经访问过的节点保存下来，以便在遍历完当前节点的子树后能够回到父节点继续遍历。这时候需要用到一个辅助栈，将已经访问过的节点依次保存到栈中。当遍历完当前节点的子树后，可以从栈中取出上一个访问过的节点，然后继续遍历其右子树。

保存待访问的节点：在遍历二叉树时，需要按照某种次序依次访问树中的节点。在使用递归算法时，系统会自动保存当前的执行状态，因此程序能够在递归返回时正确地继续执行。但是在使用非递归算法时，需要手动保存待访问的节点，以便在遍历完当前节点的左子树后能够继续遍历右子树。这时候也需要用到一个辅助栈，将待访问的节点保存到栈中。

因此，栈在二叉树的非递归遍历算法中扮演了一个重要的角色，它能够帮助我们保存已经访问过的节点，以及待访问的节点，使得程序能够正确地遍历整棵树，并且保证遍历的次序正确。