bt_fun.cpp

BiTree 实现二叉树的基本功能

//BT_Fun.cpp
//2008.05.17
//uuhorse

#include "St_BT.h"


Status InitBiTree (BiTree &T)	//构造空二叉树T
{
	/*
	T=( BiTree )malloc( sizeof(BiTNode) );
	T->lchild=NULL;
	T->rchild=NULL;
	*/
	T=NULL;
	return true;
}

Status CreateBiTree (BiTree &T)//按定义构造二叉树T
{
	TElemType tempNode;

	scanf("%c",&tempNode);
	if(tempNode==' ')
	{
		T=NULL;
	}
	else
	{
		T=(BiTree) malloc (sizeof(BiTNode));
		if ( T==NULL )
			return false;
		T->data=tempNode;	//生成根节点
		CreateBiTree (T->lchild);	//构造左子树
		CreateBiTree (T->rchild);	//构造右子树
	}

	return true;
}

Status PreOrderTraverse ( BiTree T /*,Status (*Visit)(TElemType e) */) //前序遍历
{

	if (T!=NULL)
	{
		if ( Visit (T) )	//访问根节点
			if (PreOrderTraverse ( T->lchild  ))	//遍历左子树
				if (PreOrderTraverse ( T->rchild ))	//遍历右子树
					return true;
		return false;
	}
	return true;
}

Status InOrderTraverse ( BiTree T/*,Status (*Visit)(TElemType e) */ )//中序遍历
{
	if (T!=NULL)
	{
		if (InOrderTraverse ( T->lchild  ))	//遍历左子树
			if ( Visit (T) )	//访问根节点
				if (InOrderTraverse ( T->rchild ))	//遍历右子树
					return true;
		return false;
	}
	return true;
}	

Status PostOrderTraverse ( BiTree T/*,Status (*Visit)(TElemType e) */)//后序遍历
{
	if (T!=NULL)
	{
		if (PostOrderTraverse ( T->lchild  ))	//遍历左子树
			if (PostOrderTraverse ( T->rchild ))	//遍历右子树
				if ( Visit (T) )	//访问根节点
					return true;
		return false;
	}
	return true;
}

Status LevelOrderTraverse ( BiTree T/*,Status (*Visit)(TElemType e) ,int MaxSize*/)//层序遍历
{
	#define MaxSize 100

	BiTree Qu[MaxSize];
	//Qu= (BiTNode **)malloc (sizeof(BiTree));	//定义循环队列，用于存储同层节点
	int front,rear;
	
	front=rear=0;
	if(!Visit (T))				///////////
		return false;
	rear++;
	Qu[rear]= T;
	while (rear!=front)
	{
		front=(front+1)%MaxSize;
		T=Qu[front];
		if (T->lchild!=	NULL)	//左孩子访问成功
		{
			printf(" %c ",T->lchild->data);
			rear=(rear+1)%MaxSize;
			Qu[rear]=T->lchild;
		}
		if (T->rchild!=NULL)
		{
			printf(" %c ",T->rchild->data);
			rear=(rear+1)%MaxSize;
			Qu[rear]=T->rchild;
		}
	}
	printf("\n");
	return true;
}

Status DestoryBiTree (BiTree &T)	//销毁二叉树 T
{
	if (T==NULL)
		return false;
	DestoryBiTree (T->lchild);
	DestoryBiTree (T->rchild);
	free (T);
	T=NULL;
	return true;
}

Status BiTreeEmpty(BiTree &T)		//若T为空二叉树，返回true,否则，返回false
{
	if( T==NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int BiTreeDepth (BiTree &T)	//返回树T的深度
{
	int maxDepth=1;
	int lDepth;
	int rDepth;

	if (T==NULL)
		return 0;
	lDepth=BiTreeDepth (T->lchild);
	rDepth=BiTreeDepth (T->rchild);
	maxDepth += ( (lDepth>rDepth)? lDepth:rDepth );
	return maxDepth;
}

BiTNode Root (BiTree &T)		//返回树T的根节点
{
	return *T;
}

Status Assign (BiTree &T, TElemType &e, TElemType value)//二叉树存在，e是T的某个节点，节点e赋值为value
{
	BiTNode* tmp;
	tmp=FineNode (T,e);
	if (tmp==NULL)
		return false;
	tmp->data=value;
	return true;
}

BiTNode *FineNode (BiTree T, TElemType e)//查找data域为e的节点
{
	BiTNode* p=NULL;
	if (T==NULL)
	{
		return NULL;
	}
	else if(T->data==e)
	{
		return T;
	}
	else
	{
		p=FineNode (T->lchild,e);//查找左子树
		if (p==NULL)	//如果未找到，则查找右子树
			p=FineNode (T->rchild,e);
		return p;
	}
}

BiTNode* Parent (BiTree T, TElemType e)//返回节点e的双亲
{
	BiTNode* parent=NULL;
	if (T==NULL || (T->lchild==NULL && T->rchild==NULL))
	{
		return NULL;
	}
	else if(T->lchild!=NULL && T->lchild->data==e)
	{
		return T;
	}
	else if (T->rchild!=NULL && T->rchild->data==e)
	{
		return T;
	}
	else
	{
		parent=Parent (T->lchild,e);//查找左子树
		if (parent==NULL)	//如果未找到，则查找右子树
			parent=Parent (T->rchild,e);
		return parent;
	}
}

BiTNode* LeftChild (BiTree T, TElemType e)//返回节点e的左孩子
{
	if( BiTreeEmpty (T))
	{
		printf("T is NULL!\n");
		return NULL;
	}
	BiTNode* lp;
	lp=FineNode(T, e);
	return lp->lchild;
}

BiTNode* RightChild (BiTree &T, TElemType e)//返回节点e的右孩子
{
	if( BiTreeEmpty (T))
	{
		printf("T is NULL!\n");
		return NULL;
	}
	BiTNode* rp;
	rp=FineNode(T, e);
	return rp->rchild;
}

Status InsertChild (BiTree &T, BiTNode* p, Status LR, TElemType c)
//根据LR为0或1，在节点p处插入左孩子节点或右孩子节点,p原有子树成为c的右子树
{
	BiTree tmp;
	BiTNode* inTmp;		//////////////////
	inTmp= (BiTNode*)malloc (sizeof(BiTNode));

	if (T==NULL || p==NULL || inTmp==NULL)
		return false;
	
	#define L 0
	#define R 1
	if (LR==L)
	{
		tmp=p->lchild;
		p->lchild=inTmp;
	}
	else
	{
		tmp=p->rchild;
		p->rchild=inTmp;
	}
	inTmp->data=c;
	inTmp->lchild=NULL;
	inTmp->rchild=tmp;

	return true;
}

Status DeleteChild (BiTree &T, BiTNode* p, Status LR )
//根据LR为0或1，删除T中p所指向节点的左孩子或右孩子
{
	if (T==NULL || p==NULL)
		return false;
	#define L 0
	#define R 1
	if (LR==L && p->lchild!=NULL)
	{
		DeleteChild (p,p->lchild,L);
		DeleteChild (p,p->lchild,R);
		free (p->lchild);
		p->lchild=NULL;
	}
	else if (LR==R && p->rchild!=NULL)
	{
		DeleteChild (p,p->rchild,L);
		DeleteChild (p,p->rchild,R);
		free (p->rchild);
		p->rchild=NULL;
	}
	return true;
}

Status Visit (BiTNode* p)//对节点进行访问输出
{
	if (p==NULL)
	{
		printf("节点p为空，访问失败！\n");
		return false;
	}
	else
	{
		printf(" %c ",p->data);
		return true;
	}
}