在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构

总结先根遍历得到的非递归算法思想如下：

1）入栈，主要是先头结点入栈，然后visit此结点

2）while，循环遍历当前结点，直至左孩子没有结点

3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）

先看符合此思想的算法：

            2）这里在保存结点的时候，我保存的是指针也就是结点的地址，将其变为int型存储，在pop的时候里面使用的是指针，所以取的是&pBiNode，而不是pBiNode，为什么请自行思考指针的使用，最好理解的就是BiTNode *pBiNode;定义改为BiTree pBiNode就很好理解了。

上面这个算法其实是错误的！为什么呢？ 这里我检查好久，期间出现还出现过无限循环，也出现过从左子树退出后右边子树不显示，最后我修改了第一个while判断条件，为什么呢？因为如果在pop之后，栈已空但是右子树还有，就无法继续了，这个在我写出后并没有进行太多验证，后面再阐述，这里并没有压入null指针，看一下压入空指针的例子，主要是左子树为空的时候才压入栈的，如下：

 BiTNode *pBiNode = T;
 SqStack S;
 InitStack(&S);
 Push(&S, (SElemType)T);

 while (!IsStackEmpty(S))
 {
  GetTop(S, (SElemType*)&pBiNode);
  while (pBiNode)
  {
   VisitNode(pBiNode->data);  
   pBiNode = pBiNode->lchild;
   Push(&S, (SElemType)pBiNode);
  }
  if(pBiNode == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode);
  }  
  if ( !IsStackEmpty(S))
  {
   Pop(&S, (SElemType*)&pBiNode);
   pBiNode = pBiNode->rchild;
   Push(&S, (SElemType)pBiNode);
  }
 }

 return 0;
}