前序遍历的非递归算法

<法一>

思路：

二叉树的前序遍历过程：

1. 从树根开始沿着左子树一直深入，直到最左端无法深入时，返回；
2. 进入最近深入时遇到结点的右子树，再进行如此的深入和返回；
3. 直到最后从根节点的右子树返回到根节点为止；

由其深入返回的过程我们知道可以用一个栈来帮助我们消除递归

1.存入根结点：首先判断root（根节点）是否为空，如果为空则直接return，不为空就将根节点压入栈中。这里我随机生成一个树作为例子，

→

2.进行非递归前序遍历：将A弹出，打印出A结点存入的值，接着再依次检查A是否有右孩子（Rson）和左孩子（Lson）（因为是前序遍历，而栈的特点是先进后出，我们需要优先打印左孩子的值，所以先检查是否有右孩子，如果有的话将右孩子优先压入栈中），如果有的话依次存入栈中，此时栈中全是第二层的元素

随后我们再弹出栈顶结点B，打印他的值，接着依葫芦画瓢，分别再次检查B的右孩子和左孩子，如果有的话分别存入，因为B没有左孩子，所以第三次压栈存入D结点

再次弹出D结点，存入其右孩子和左孩子，栈更新为：

因为G，F为叶子结点，没有孩子，所以分别弹出F，G并打印值，目前为止打印出：ABDFG;

当栈中只剩C时，弹出C，打印值，因为C有右孩子，所以存入其右孩子E，栈更新为：

最后，弹出E，存入其右孩子H:

因为G是叶子结点，所以弹出G后栈为空，整个树也遍历完毕，由此可以得到循环的条件是当且仅当栈不为空时

3.观察特点进行总结：只要左子树还没有遍历完，就会弹出元素的同时，存入新的元素，直到左子树全部被遍历完没有新的元素存入，才会开始遍历右子树，这也构成我们的中序遍历。

代码实现如下：

typedef struct BiTNode
{
  char data;
  struct BiTNode *lson, *rson;
} BiTNode, *BiTree;  //二叉树的结构体

// 二叉树的前序遍历算法1基于STL stack
void PreOrder1(BiTree bt)
{
  stack<BiTree> Stack;
  if (bt == NULL)    //如果根结点为空，直接return
    return;
  Stack.push(bt);    //根结点不为空将其压入栈中
  while (!Stack.empty())  //循环条件：当栈不为空时
  {
    BiTree Cur = Stack.top();  
    cout << Cur->data << endl; 
    Stack.pop();           //取出并打印栈顶元素
    if (Cur->rson)             
      Stack.push(Cur->rson);
    if (Cur->lson)
      Stack.push(Cur->lson);   //分别将栈顶元素的右孩子和左孩子压入栈中
  }
}

<法二>

思路：

1.连续将结点的左孩子压入栈中：此处我仍用这个生成的树进行演示，法二的主要思路是只要当前节点指向左孩子的指针不为NULL，就一直打印当前节点值并压入栈中。

→

打印：AB

2.弹出栈顶元组：直到一个结点没有左孩子时，此时退出循环，此时只有从B的右孩子D进行入手，所以我们弹出栈顶元素B，并将指针指向该节点的右孩子D，重复第一步的操作：

3.重复1，2步：循环到F时又退出了，我们再重复第二步的操作，弹出F，而F也没有右孩子，所以继续弹出D，将节点指针指向D的右孩子G，继续循环：

→

→→

注意：由于C，E，H只有右孩子没有左孩子所以只能弹出C后E才能进栈，弹出E后C才能进栈

3.循环结束条件：如果初始的根结点为空，则循环直接退出，进入循环后如果栈中没有新增元素，并且没有新增元素即将入栈（即当前指向的结点为空），代表遍历完成，此时退出循环。

代码实现如下：

// 二叉树的前序遍历算法2基于STL stack
void PreOrder2(BiTree bt)
{
  stack<BiTree> Stack;
  BiTree Cur;
  while (!Stack.empty() || bt != NULL)  //循环终止条件
  {
    while (bt != NULL)   
    {
      cout << bt->data << endl;
      Stack.push(bt);
      bt = bt->lson;
    }
    if (!Stack.empty())   
    {
      Cur = Stack.top();
      Stack.pop();
      bt = Cur->rson;
    }
  }
}