今天写的：VC6.0下通过
//后序遍历非递归算法 2004/8/8
#include <iostream.h>
typedef struct node
{
int data;
struct node* left;
struct node* right;
}node;
//层次遍历二叉树所用到的队列
class queue
{
public:
queue()
{
q=new node*[10];
front=0;
rear=0;
maxsize=10;
}
int IsFull()
{
if((rear+1)%maxsize==front)
return 1;
else
return 0;
}
int IsEmpty()
{
if(front==rear)
return 1;
else
return 0;
}
void InQueue(node* p)
{
if(IsFull())
{
cout<<"队列满!!进队失败!!"<<endl;
return;
}
else
{
q[rear]=p;
rear=(rear+1)%maxsize;
}
}
node* OutQueue()
{
if(IsEmpty())
{
cout<<"队列空!!出队失败!!"<<endl;
return 0;
}
else
{
node* t;
t=q[front];
front=(front+1)%maxsize;
return t;
}
}
private:
node** q;
int front;
int rear;
int maxsize;
};
// 非递归后序遍历二叉树 工作栈
//首先需要一个结构，存tag;
typedef struct Mystruct
{
node* p;
int tag;
}Mystruct;
class stack
{
public:
Mystruct* s;
int top;
int size;
public:
void push(Mystruct x)
{
if(IsFull())
{
cout<<"栈己满!!"<<endl;
return;
}
s[++top]=x;
}
void ptop()
{
if(IsEmpty())
{
cout<<"栈己空!!"<<endl;
}
else
{
top--;
}
}
Mystruct pop()
{
if(IsEmpty())
{
cout<<"栈己空!!"<<endl;
Mystruct m;
m.p =0;
m.tag =0;
return m;
}
return s[top--];
}
stack()
{
top=-1;
size=100;
s=new Mystruct[100];
}
int IsEmpty ()
{
if(top==-1)
return 1;
else
return 0;
}
int IsFull()
{
if(top==size-1)
return 1;
else
return 0;
}
};
//全局变量
queue q1;
stack s1;
//层次生成二叉树
node* CreateBtree()
{
int data;
cout<<"请输入根结点: ";
cin>>data;
node* root;
root=new node;
root->data =data;
root->left =0;
root->right =0;
q1.InQueue (root);
node* p;
while(!q1.IsEmpty ())
{
p=q1.OutQueue ();
cout<<"请输入"<<p->data <<"的左子树: ";
cin>>data;
node* l;
if(data)
{
l=new node;
l->data =data;
l->left =0;
l->right =0;
p->left =l;
q1.InQueue (l);
}
cout<<"请输入"<<p->data <<"的右子树: ";
cin>>data;
if(data)
{
l=new node;
l->data =data;
l->left =0;
l->right =0;
p->right =l;
q1.InQueue (l);
}
}
return root;
}
//第一次写的后序遍历非递归算法 2004/8/8
void backtravel(node* p)
{
Mystruct mystruct;
while(1)
{
while(p!=0)
{
mystruct.p =p;
mystruct.tag =0;
s1.push (mystruct);
p=p->left ;
}
if(s1.s[s1.top].tag ==0)
{
s1.s[s1.top].tag =1;
p=s1.s[s1.top].p ;
p=p->right ;
}
else
{
if(s1.IsEmpty ())
break;
cout<<s1.s[s1.top].p->data <<" ";
s1.ptop (); //弹出栈顶元素。
}
}
}
//上面这个算法用了两重循环，且当遍历空树时会出错
//我改进了上面的算法，如下：
//改进的后序非递归遍历算法 2004/8/8
void backtravel1(node* p)
{
Mystruct mystruct;
while(p!=0|| !s1.IsEmpty ())
{
if(p)
{
mystruct.p =p;
mystruct.tag =0;
s1.push (mystruct);
p=p->left ;
}
else
{
if(s1.s[s1.top].tag ==0)
{
s1.s[s1.top].tag =1;
p=s1.s[s1.top].p ;
p=p->right ;
}
else
{
cout<<s1.s[s1.top].p->data <<" ";
s1.ptop (); //弹出栈顶元素。
}
}
}
}
void main()
{
node* root;
root=CreateBtree();
backtravel1(root);
}
[em02][em02]
