前序和中序均是每个节点经过两次:
第一次经过时入栈(若是先序则入栈,并输出该节点),入完后往左子树走 ;
第二次经过时为了提供右子树节点下标,故提供右子树节点下标后就出栈(若是中序则出栈,并输出该节点);
后序则麻烦一些:每个节点要经过三次
第一次经过时入栈,找左子树,并标记该节点已经经过一次了;
第二次经过时目的是找到其右子树,并标记该节点已经经过两次了;
当判断标记第三次经过该节点时,输出该节点并将该节点出栈;
代码如下:
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
struct Node
{
int x;
int l,r;
};
Node tree[1005];
void postOrder( int root )
{
stack<int>sta;
int flag[15]; //记录每个节点访问次数栈
memset(flag,0,sizeof(flag));
int p=root;
while( !sta.empty() || p != -1 )
{
if( p != -1 )
{ //第一次访问,flag置1,入栈
sta.push(p);
flag[p] = 1;
p=tree[p].l;
}
else //(p == NULL)
{
if( flag[ () ] == 1 )
{ //第二次访问,flag置2,取栈顶元素但不出栈
p=();
flag[p] = 2;
p = tree[p].r;
}
else
{ //第三次访问,出栈
p = ();
sta.pop();
cout<< tree[p].x <<" "; //出栈时,访问输出
p = -1; //p置空,以便继续退栈
}
}
}
cout<<endl;
return;
}
void preOrder(int root)
{
int p=root;
stack<int>sta;
while(p!=-1 || !sta.empty() )
{
if(p!=-1)
{
cout<<tree[p].x<<" ";
sta.push(p);
p=tree[p].l;
}
else
{
int t=();
sta.pop();
p=tree[t].r;
}
}
cout<<endl;
return ;
}
void inOrder(int root)
{
int p=root;
stack<int>sta;
while( p!=-1 || !sta.empty() )
{
if( p!=-1 )
{
sta.push(p);
p=tree[p].l;
}
else
{
int t=();
cout<<tree[t].x<<" ";
sta.pop();
p=tree[t].r;
}
}
cout<<endl;
return;
}
int main()
{
// 例子数据
tree[1].l=2,tree[1].r=3;
tree[2].l=4,tree[2].r=5;
tree[3].l=-1,tree[3].r=6;
tree[4].l=-1,tree[4].r=-1;
tree[5].l=-1,tree[5].r=-1;
tree[6].l=-1,tree[6].r=-1;
tree[1].x=100,tree[2].x=200,tree[3].x=300,tree[4].x=400,tree[5].x=500,tree[6].x=600;
//依次是 : 后序,前序,中序
postOrder(1);
preOrder(1);
inOrder(1);
return 0;
}