//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;
	}
}