void BinTree::PostOrder(Node *r)//递归实现后序遍历
{
if(r==NULL)
{
return ;
}
else
{
PostOrder(r->left);
PostOrder(r->right);
cout<<r->data<<" ";
}
}
void BinTree::PostOrder1(Node *r)//后序遍历的非递归实现
{
if(r==NULL)
return ;
Node *p=r;
stack<Node*>s;
while(p || !s.empty())
{
while(p)//先将所有的左孩子压入栈中
{
s.push(p);
p=p->left;
}
if(!s.empty())
{
Node *q=s.top();
if(q->FirstVisited)//如果是第一次访问
{
q->FirstVisited=false;
p=q->right;
}
else//如果是第二次访问，则输出
{
cout<<q->data<<" ";
s.pop();
p=NULL;//给p一条出路
}
}
}
}
int main()
{
BinTree t;
t.CreateTree();//创建二叉树
/////////////三种遍历方式//////////////
cout<<"先序遍历:";
t.preOrder(t.root);//先序遍历
cout<<endl<<"先序遍历非递归实现算法:";
t.preOrder1(t.root);
cout<<endl;
cout<<"中序遍历:";
t.InOrder(t.root);//中序遍历
cout<<endl<<"中序遍历非递归算法:";
t.InOrder1(t.root);
cout<<endl;
cout<<"后序遍历:";
t.PostOrder(t.root);//后序遍历
cout<<endl<<"后序遍历的非递归算法:";
t.PostOrder1(t.root);//后序遍历的非递归算法
cout<<endl;
return 0;
}
测试结果如下：
