学步园

/*
*@2012-12-11
*二叉树的递归创建，先序(中序、后序)递归遍历二叉树
*/
#include <iostream>
using namespace std;
typedef char TElemType;
typedef struct BitreeNode
{
	TElemType TItem;
	struct BitreeNode *lchild;//左孩子
	struct BitreeNode *rchild;//右孩子
}BitreeNode,*Bitree;
//初始化二叉树
int InitBitree(Bitree &T)
{
	T=(Bitree)malloc(sizeof(BitreeNode));
	if(!T)
		return 0;
	T->TItem='#';
	T->lchild=NULL;
	T->rchild=NULL;
	return 1;
}
//判断二叉树是否空
int EmptyBitree(Bitree &T)
{
	if(T!=NULL)
		return 1;
	return 0;
}
//销毁二叉树
int DestroyBitree(Bitree &T)
{
	if(T!=NULL)
	{
		if(DestroyBitree(T->lchild))
		{	
			if(DestroyBitree(T->rchild))
			{
				//cout<<T->TItem<<" ";
				free(T);
				return 1;
			}
			return 0;
		}
	}
	return 1;
}
//递归创建二叉树
int CreatBitree(Bitree &T)
{
	TElemType ch;
	cin>>ch;//以ab##c##格式输入，'#'表示当前子树为空子树
	if(ch=='#')
	{
		T=NULL;
		return 0;
	}
	else
	{
		T=(Bitree)malloc(sizeof(BitreeNode));
		if(T)
		{
			T->TItem=ch;
			CreatBitree(T->lchild);
			CreatBitree(T->rchild);
		}
	}
	return 1;
}
//先序遍历二叉树,根->左->右
void PreOrderTravers(Bitree T)
{
	if(T!=NULL)
	{
		cout<<T->TItem<<" ";
		PreOrderTravers(T->lchild);
		PreOrderTravers(T->rchild);
	}
}
//中序遍历二叉树,左->根->右
void InOrderTravers(Bitree T)
{
	if(T!=NULL)
	{
		InOrderTravers(T->lchild);
		cout<<T->TItem<<" ";
		InOrderTravers(T->rchild);
	}
}
//后序遍历二叉树,左->右->根
void PostOrderTravers(Bitree T)
{
	if(T!=NULL)
	{
		PostOrderTravers(T->lchild);
		PostOrderTravers(T->rchild);
		cout<<T->TItem<<" ";
	}
}

int main()
{
	Bitree S;
	InitBitree(S);
	CreatBitree(S);
	EmptyBitree(S);//树非空返回1
	cout<<"先序遍历结果：";
	PreOrderTravers(S);
	cout<<endl;
	cout<<"中序遍历结果：";
	InOrderTravers(S);
	cout<<endl;
	cout<<"后序遍历结果：";
	PostOrderTravers(S);
	cout<<endl;
	DestroyBitree(S);
	return 0;
}