输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树的二叉链表。
写出对用二叉链表存储的二叉树进行先序、中序和后序遍历的非递归算法。
写出对用二叉链表存储的二叉树进行层次遍历算法。
思路：
在这里只介绍下后序遍历的非递归算法。
后序遍历要先访问左子树，再访问右子树，最后访问根节点。如果左右子树为空，则遍历根节点；如果左右子树访问完了，则访问根节点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
代码如下：
<span style="font-size:14px;">//输入示例：ABD###CE##F##
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <queue>
using namespace std;
typedef struct tree{
char data;
struct tree *lchild,*rchild;
}BiNode,*BiTree;
void InitTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
{
T=NULL;
return ;
}
T=(BiTree)malloc(sizeof(BiNode));
T->data=ch;
InitTree(T->lchild);
InitTree(T->rchild);
}
void PreOrder(BiTree bt)
{
stack <BiTree> S;
int i,j;
BiTree p;
if(bt)
p=bt;
S.push(p);
while(!S.empty())
{
while(p)
{
printf("%c",p->data);
p=p->lchild;
S.push(p);
}
S.pop();
if(!S.empty())
{
p=S.top();
S.pop();
p=p->rchild;
S.push(p);
}
}
}
void InOrder(BiTree bt)
{
stack <BiTree> S;
int i,j;
BiTree p;
if(bt)
p=bt;
S.push(p);
while(!S.empty())
{
while(p)
{
p=p->lchild;
S.push(p);
}
S.pop();
if(!S.empty())
{
p=S.top();
printf("%c",p->data);
S.pop();
p=p->rchild;
S.push(p);
}
}
}
void PostOrder(BiTree bt)
{ //后序非递归遍历
stack <BiTree> s;
BiTree p,last; //last是上一次访问的结点
if(bt)
{
s.push(bt);
p=bt;
}
while(!s.empty())
{
p=s.top();
if((p->lchild==NULL && p->rchild==NULL) || last!=NULL &&(last==p->lchild || last==p->rchild))
{//如思路中判断
printf("%c",p->data);
last=p; //记录访问结点
s.pop();
}
else
{
if(p->rchild)
s.push(p->rchild);
if(p->lchild)
s.push(p->lchild);
}
}
}
void LevelOrder(BiTree bt)
{//层次遍历
queue <BiTree> q;
BiTree p;
if(bt)
q.push(bt);
while(!q.empty())
{
p=q.front();
q.pop();
printf("%c",p->data);
if(p->lchild)
q.push(p->lchild);
if(p->rchild)
q.push(p->rchild);
}
}
int main()
{
BiTree T;
printf("请输入树的结点：");
InitTree(T);
printf("先序遍历结果为：");
PreOrder(T);
putchar('\n');
printf("中序遍历结果为：");
InOrder(T);
putchar('\n');
printf("后序遍历结果为：");
PostOrder(T);
putchar('\n');
printf("层次遍历结果为：");
LevelOrder(T);
putchar('\n');
return 0;
}</span>