source.cpp

C++中的一个简单的二叉树的后续递归算法例子

#include<iostream.h>
#include"head.h"
#define size 5

bitree::bitree(binode *root)//析构函数
{
    creat(root);
}

void bitree::creat(binode *root)
{
    int n;
	cout<<"give the node of the tree:"<<endl;
	cin>>n;
	if(n=='a')
		root=NULL;//建立一棵空树
	
	else
	{
	    root=new binode;
	    root->data=n;
	    creat(root->lchild);//递归建立左子树
	    creat(root->rchild);//递归建立右子树
	}
}




void bitree::PostOrder(binode *root)//后序非递归算法
{
	element s[size];
	
	

    int top=-1;//采用顺序栈假定栈不会发生上溢
	while(root !=NULL||top !=-1)
	{
	    while(root!=NULL)
		{
		    top++;
			s[top].ptr=root;
			s[top].flag=1;
			root=root->lchild;
		}
		while(top!=-1&&s[top].flag==2)
		{
		    root=s[top--].ptr;
			cout<<root->data<<endl;
		}
		if(top!=-1)
		{
		    s[top].flag=2;
			root=s[top].ptr->rchild;
		}
	}
	
	
    
}