二叉树的创建和遍历

/**
** name: 二叉树的创建和遍历
** author: Dev|il
** date: 2011-10-15 12:56
**/

#include <iostream>
#include <queue>
using namespace std;

const int MAX_TREE_SIZE = 1000;
typedef int ElemType;
typedef bool Status;
typedef ElemType bitTree[MAX_TREE_SIZE]; //树的线性定义,只适合存储满二叉树

const ElemType END = -1;
//树的二叉链表定义
typedef struct LNode{
	ElemType data;
	struct LNode *lchild, *rchild;
}BitNode, *BiTree;


/////////////////////////////////函数的声明///////////////////////////////////////////

//按先序DLR输入二叉树节点的值,构造二叉链表表示的二叉树T
Status DLRCreateBiTree(BiTree &t);

//DLR
//采用二叉链表存储结构,visit是对节点操作的应用函数
//先序遍历二叉树t,对每个节点调用visit函数一次且一次
//一旦visit操作失败,则函数操作失败
Status PreOrderTraverse(BiTree t, Status (* visit)(ElemType e));

//LDR
//采用二叉链表的存储结构,visit是对节点操作的应用函数
//中序遍历二叉树t,对每个节点调用visit函数一次且一次
//一旦visit操作失败,则函数操作失败
Status InOrderTranverse(BiTree t, Status(*visit)(ElemType e));

//LRD
//采用二叉链表的存储结构,visit是对节点操作的应用函数
//后序遍历二叉树t,对每个节点调用visit函数一次且一次
//一旦visit操作失败,则函数操作失败
Status PostOrderTranverse(BiTree t, Status(*visit)(ElemType e));


//采用二叉链表的存储结构,visit是对节点操作的应用函数
//层序遍历二叉树t,对每个节点调用visit函数一次且一次
//一旦visit操作失败,则函数操作失败
void LevelOrderTranverse(BiTree t, Status(*visit)(ElemType e));

//访问函数
Status visit(ElemType e);

//返回二叉树t的深度
int DLRBiTreeDepth(BiTree t);
///////////////////////////////////////////////////////////////////////////////
//////////////////////////////////函数的实现//////////////////////////////////

Status DLRCreateBiTree(BiTree &t)
{
	ElemType e;
	cin>>e;
	if(e == END)
		t = NULL;
	else
	{
		t = (BiTree)malloc(sizeof(BitNode)); //创建节点,相当于建立头
		if(!t)
			return false;
		t->data = e; //赋数据
		if(!DLRCreateBiTree(t->lchild)) //建立左子树
			return false;
		if(!DLRCreateBiTree(t->rchild)) //建立右子树
			return false;
	}
	return true;
}


Status PreOrderTraverse(BiTree t, Status (* visit)(ElemType e))
{
	if(t)
	{
		if(visit(t->data))
			if(PreOrderTraverse(t->lchild, visit))
				if(PreOrderTraverse(t->rchild, visit))
					return true;
		return false;
	}else
		return true;
}

Status InOrderTranverse(BiTree t, Status(*visit)(ElemType e))
{
	if(t)
	{
		if(InOrderTranverse(t->lchild, visit))
			if(visit(t->data))
				if(InOrderTranverse(t->rchild, visit))
					return true;
		return false;
	}else
		return true;
}

Status PostOrderTranverse(BiTree t, Status(*visit)(ElemType e))
{
	if(t)
	{
		if(PostOrderTranverse(t->lchild, visit))
			if(PostOrderTranverse(t->rchild, visit))
				if(visit(t->data))
					return true;
		return false;
	}else
		return true;
}

void LevelOrderTranverse(BiTree t, Status(*visit)(ElemType e))
{
	queue<BiTree> q;
	q.push(t);
	while(!q.empty())
	{
		BiTree cur = q.front();
		q.pop();
		visit(cur->data);
		if(cur->lchild)
			q.push(cur->lchild);
		if(cur->rchild)
			q.push(cur->rchild);
	}
}
Status visit(ElemType e)
{
	cout<<e<<"  ";
	return true;
}

int BiTreeDepth(BiTree t)
{
	int Ldepth, Rdepth, max;
	if(!t)
		return 0;
	else
	{
		Ldepth = BiTreeDepth(t->lchild);
		Rdepth = BiTreeDepth(t->rchild);
		max = Ldepth > Rdepth ? Ldepth : Rdepth;
		return max + 1;
	}
}
/////////////////////////////////////////////////////////////////////////////

int main()
{
	BiTree t;
	DLRCreateBiTree(t);
	cout<<"先序遍历:";
	PreOrderTraverse(t, visit);
	cout<<endl<<"中序遍历:";
	InOrderTranverse(t, visit);
	cout<<endl<<"后序遍历:";
	PostOrderTranverse(t, visit);
	cout<<endl<<"层次遍历:";
	LevelOrderTranverse(t, visit);
	cout<<endl<<"树的深度:";
	cout<<BiTreeDepth(t);
	cout<<endl;
	return 0;
}