前文论述了二叉树的递归扫描算法(二叉树的前根)扫描的改进)，该文主要论述二叉树的非递归算法，采用堆栈结构
总结了通过前根遍历得到的非递归算法的思想，如下。
1 )进入堆栈主要是起始节点进入堆栈，对该节点进行visit
2 ) while，巡视当前节点，直到左子有节点为止
3 ) if节点的右子节点为真，1 )转移到遍历。 否则，退出当前节点并转移到父节点遍历1 ) )。
首先，让我们来看看符合这一思想的算法：
intpreordertraversenonrecursiveex (constbitreet，int ) visit node (t elemtype data ) )
{
if(t==null ) )。
{
返回- 1；
}
BiTNode *pBiNode=T；
SqStack S；
initstack(s )；
push(s，) SElemType ) t；
while (！ istackempty(s ) )
{
是while(Pbinode )
{
visitnode(Pbinode-data；
if(PbInode！=T )
{
push(s，) SElemType ) pBiNode；
}
pBiNode=pBiNode-lchild；
}
if(Pbinode==null ) )。
{
pop(s，) SElemType* ) pBiNode；
}
if(Pbinode-rchild==null ) ) () ) ) ) ) ) ) )。
{
pop(s，) SElemType* ) pBiNode； //如果此时堆栈为空，则存在问题
}
pBiNode=pBiNode-rchild；
}
返回0；
}
注意：1)这里使用的是堆栈结构。 请参阅以上述顺序结构存储的堆栈
2 )在这里，保存节点的时候，我保存着指针也就是节点的地址。 将其作为int型存储器，在pop的时候在里面使用指针，所以取pBiNode而不是pBiNode。 为什么请自己考虑指针的使用方法。 最好理解的是BiTNode *pBiNode。 将定义改为BiTree pBiNode很容易理解。
上面的算法其实是错误的！ 为什么呢？ 在这里久违地检查一下。 在此期间也出现过无限循环。 有时，从左边的子树退出后，右边的子树不再显示。 最后我修正了最初的while判断条件。 为什么会这样呢？ 因为，在pop之后，如果堆栈空了，但右边的子树还在的话，就不能继续了。 这个在我导出之后很少验证。 稍后我会讲到，这里没有压入空指针。 让我们看一下压入空指针的例子。 主要是在左边的部分树为空时压入堆栈。 如下所示。
intpreordertraversenonrecursive (constbitreet，int ) visit node (t elemtype data ) )
{
if(t==null ) )。
{
返回- 1；
}
BiTNode *pBiNode=T；
SqStack S；
initstack(s )；
push(s，) SElemType ) t；
while (！ istackempty(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 (！ istackempty(s ) )
{
pop(s，) SElemType* ) pBiNode；
pBiNode=pBiNode-rchild；
push(s，) SElemType ) pBiNode；
}
}
返回0；
}
在此，首先推入根节点，然后判断左子树是否为空，如果不为空，则推入堆栈，否则退出while循环后，将空节点推出堆栈，判断当前堆栈是否为空，如果不为空，则跳过堆栈
入右孩子结点，再判断此右子树的左孩子是否为空，继续循环。这里有两个浪费的地方：一个就是压入空孩子结点入栈，二就是频繁使用GetTop获得栈顶元素
这里返回过来再看初开始设计的算法，那里正好没有压入NULL指针或者说空的孩子结点，但是并不能输出完整，这里我们想到可以在判断栈的时候加入，当前的结点是否为NULL就可以了，这样就不会出现不会显示退出左子树结点不能显示右子树结点的尴尬了，如下：
//非递归先序遍历二叉树
int PreOrderTraverseNonRecursiveEx(const BiTree &T,
int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while ( !IsStackEmpty(S) || pBiNode) //主要修改的就是这句
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空，就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
在第一个while循环加入这个之后，就可以了，测试用例与二叉树先序遍历类似。如下测试上节的二叉树例子：
此时输入的数据仍然还是 12 34 0 0 78 0 0，测试结果如下：
--- BiTree ---
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12 34 78
这个还不足以测试，再看如下的二叉树
此时输入数据应该为：12 34 24 0 0 50 0 0 78 37 0 0 0，测试结果如下：
--- BiTree ---
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
24
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
50
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
37
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12 34 24 50 78 37
由先序遍历可知，正好是正确的，另外这些算法不光是对先序遍历的，如果想变为中序或者后序，只需将上面算法中的visit之类的先去掉，然后将它加入合适的位置，就可以了