【答案解析】后序遍历可以用递归实现，程序中递归的调用就是保存函数的信息在栈中。一般情况下，能用递归解决的问题都可以用栈解决，只是递归更符合人们的思维方式，代码相对而言也更简单，但不能说明递归比栈的方式更快、更节省空间，因为在递归过程中都是操作系统来帮助用栈实现存储信息。下面用栈来实现二叉树的后序遍历。栈的思想是“先进后出”，即首先把根结点入栈(这时栈中有一个元素)，根结点出栈的时候再把它的右左孩子入栈(这时栈中有两个元素，注意是“先进右后进左”，不是“先进左后进右”)，再把栈顶出栈(也就是左孩子)，再把栈顶元素的右左孩子入栈，此过程一直执行直到栈为空，出栈的元素按顺序排列就是这个二叉树的先序遍历。
用栈来解决二叉树的后序遍历是最后输出父亲结点，先序遍历是在结点出栈时入栈右左孩子。显然，对于后续遍历，不应该在父亲结点出栈时，才把右左孩子入栈，应该在入栈时就把右左孩子一并入栈。在父亲结点出栈时，应该判断右左孩子是否已经遍历过(是否执行过入栈)，那么就应该有一个标记来判断孩子是否遍历过。下面借用二叉树的结构体来定义一个适用于这个算法的新结构体：
typedef struct stackTreeNode
{
BTree treeNode;
int flag;
}*pSTree;
结构体中，flag为标志位，0表示左右孩子没有遍历，2表示左右孩子遍历完，具体实现代码如下：
int lastOrder(BTree root)
{
stack＜pSTree＞ stackTree;
pSTree sYree = (pSTree)malloc(sizeof( struct stackTreeNode));
sTree-＞treeNode=root;
sTree-＞flag=0;
stackTree.push(sTree);
while(!stackTree.empty())
{
pSTree tmptree=stackTree.top();
if(tmptree-＞flag==2)
{
cout＜＜tmptree-＞treeNode-＞data＜＜" ";
stackTree.pop();
}
else
{
if(tmptree-＞treeNode-＞rchild)
{
pSTree sTree = (pSTree)malloc(sizeof( struct stackTreeNode));
sTree-＞treeNode=tmptree-＞treeNode-＞rchild;
sTree-＞flag=0;
stackTree.push(sTree);
}
tmptree-＞flag++;
if(tmptree-＞treeNode-＞1child)
{
pSTree sTree=(pSTree)malloc(sizeof( struct stackTreeNode));
sTree-＞treeNode=tmptree-＞treeNode-＞1child;
sTree-＞flag=0;
stackTree.push(sTree);
}
tmptree-＞flag++;
}
}
return 1;
}
引申：如何使用非递归方法实现二叉树的先序遍历与中序遍历?
将二叉树的先序遍历递归算法转化为非递归算法的方法如下：
1)将二叉树的根结点作为当前结点。
2)若当前结点非空，则先访问该结点，并将该结点进栈，再将其左孩子结点作为当前结点，重复步骤2)，直到当前结点为空为止。
3)若栈非空，则栈顶结点出栈，并将当前结点的右孩子结点作为当前结点。
4)重复步骤2)、3)，直到栈为空且当前结点为空为止。
程序代码示例如下：
typedef street
{
Bitree Elem[100];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
Stacklnit(s);
p=t;
while(p!=null‖!StackEmpty(s))
{
while(p!=null)
{
visite(p-＞data);
push(s,p);
p=p-＞1child;
}
if(!StackEmpty(s))
{
p=pop(s);
p=p->rchild;
}
}
}
将中序遍历递归算法转化为非递归算法的方法如下：
1)将二叉树的根结点作为当前结点。
2)若当前结点非空，则该结点进栈并将其左孩子结点作为当前结点，重复步骤2)，直到当前结点为空为止。
3)若栈非空，则将栈顶结点出栈并作为当前结点，接着访问当前结点，再将当前结点的右孩子结点作为当前结点。
4)重复步骤2)、3)，直到栈为空且当前为空为止。
程序代码示例如下：
typedef struct
{
Bitree Elem[100];
int top;
}SqStack;
void InOrderUnrec(Bitree t)
SqStack s;
StackInit(s);
p=t;
while(p!=null‖!StackEmpty(s))
{
while(p!=null)
{
push(s,p);
p=p-＞lchild;
}
if(!StackEmpty(s))
{
p=pop(s);
visite(p-＞data);
P=P-＞rchild;
}
}
}