bitnode.cpp

这时关于树的一些操作的程序

#include"stdio.h"
#include"malloc.h"
#include"define.h"

typedef char TElemType;

typedef struct BiTNode	/*声明二叉树结点的形式*/
{
	TElemType data;		/*定义数据域*/
	struct BiTNode *lchild,*rchild,*parent;	/*定义左、右孩子及双亲指针*/
}BiTNode;

Status InitBiTree(BiTNode &T)
/*初始化二叉树，即初始化头结点*/
{
	if(&T==NULL)return ERROR;
	T.data=0;		/*头结点数据域用以记录二叉树的节点*/
	T.parent=NULL;	/*将所有指针置零*/
	T.lchild=NULL;
	T.rchild=NULL;
	return OK;
}


Status CreatBiTree(BiTNode &T,BiTNode *Pparent,BiTNode *(&Pnow),int i)
/*递归添加二叉树T结点，该结点由Pnow指向，其双亲结点由Pparent指向，
如果i=1,则添加为双亲结点的左结点，如果i=0,则添加为双亲结点的右结点*/
{
	
	char ch;	
	if(i==1)printf("\nEnter LEFT_CHILD for -%c- [<--] :",Pparent->data);
	else printf("\nEnter RIGHT_CHILD for -%c- [-->]:",Pparent->data);
	while((ch=getchar())==10);/*保证输入的字符不为回车键*/
	if(ch==' ')Pnow=NULL;	/*如果输入的字符为空白键，则不再为双亲结点添加该位置的孩子结点*/
	else	/*输入字符为非空白键，添加孩子结点*/
	{
		if(!(Pnow=(BiTNode *)malloc(sizeof(BiTNode))))return ERROR;/*为新结点开辟内存单元*/
		Pnow->data=ch;	/*将字符值写入数据域*/
		Pnow->parent=Pparent;	/*记录双亲结点位置*/
		Pnow->lchild=NULL;
		Pnow->rchild=NULL;
		T.data++;	/*头结点所记录的结点数加1*/
		CreatBiTree(T,Pnow,Pnow->lchild,1);	/*为当前结点添加左孩子结点*/
		CreatBiTree(T,Pnow,Pnow->rchild,0);	/*为当前结点添加右孩子结点*/
	}
	return OK;/*添加结束，返回上级结点（双亲结点）*/
}

Status StrCreatBiTree(BiTNode &T,BiTNode *Pparent,BiTNode *(&Pnow),int i,char *str,int &j)
/*将字符串str的内容递归添加到二叉树T结点，该结点由Pnow指向，其双亲结点由Pparent指向，
如果i=1,则添加为双亲结点的左结点，如果i=0,则添加为双亲结点的右结点*/
{
	
	char ch;	
	if((ch=str[j])=='^')Pnow=NULL;	/*如果字符串中的字符为^，则不再为双亲结点添加该位置的孩子结点*/
	else	/*输入非^字符，添加孩子结点*/
	{
		if(!(Pnow=(BiTNode *)malloc(sizeof(BiTNode))))return ERROR;/*为新结点开辟内存单元*/
		Pnow->data=ch;	/*将字符值写入数据域*/
		Pnow->parent=Pparent;	/*记录双亲结点位置*/
		Pnow->lchild=NULL;
		Pnow->rchild=NULL;
		T.data++;	/*头结点所记录的结点数加1*/
		StrCreatBiTree(T,Pnow,Pnow->lchild,1,str,++j);	/*为当前结点添加左孩子结点*/
		StrCreatBiTree(T,Pnow,Pnow->rchild,0,str,++j);	/*为当前结点添加右孩子结点*/
	}
	return OK;/*添加结束，返回上级结点（双亲结点）*/
}

void printBiTree(BiTNode *Pnow)
/*递归输出结点，输出形式为：当前结点（左孩子结点，右孩子结点）*/
{
	printf("\n%c",Pnow->data);	/*输出当前结点数据域*/
	if(Pnow->lchild!=NULL)printf("(%c,",Pnow->lchild->data);/*输出左孩子结点数据域*/
	else printf("( ,");
	if(Pnow->rchild!=NULL)printf("%c)",Pnow->rchild->data);/*输出右孩子结点数据域*/
	else printf(" )");
	if(Pnow->lchild!=NULL)printBiTree(Pnow->lchild);/*输出左孩子结点*/
	if(Pnow->rchild!=NULL)printBiTree(Pnow->rchild);/*输出右孩子结点*/
}

Status PrintElement(TElemType e)
/*输出数据元素*/
{
	printf(" %c ",e);
	return OK;
}



Status PreOrderTraverse(BiTNode *Pnow,Status (* Visit)(TElemType e))
/*先序遍历二叉树，对数据元素用函数Visit访问*/
{
	if(Pnow)/*检验当前结点是否为空*/
	{
		if(Visit(Pnow->data))/*调用Visit函数访问当前数据元素*/
			if(PreOrderTraverse(Pnow->lchild,Visit))/*如果左孩子不为空，递归调用PreOrderTraverse()*/
				if(PreOrderTraverse(Pnow->rchild,Visit))/*如果右孩子不为空，递归调用PreOrderTraverse()*/
					return OK;/*调用结束，返回上一级函数*/
		return ERROR;
	}
	else return OK;
}

Status InOrderTraverse(BiTNode *Pnow,Status (* Visit)(TElemType e))
/*中序遍历二叉树，对数据元素用函数Visit访问*/
{
	if(Pnow)
	{
		if(InOrderTraverse(Pnow->lchild,Visit))/*如果左孩子不为空，递归调用InstOrderTraverse()*/
			if(Visit(Pnow->data))/*调用Visit函数访问当前数据元素*/
				if(InOrderTraverse(Pnow->rchild,Visit))/*如果右孩子不为空，递归调用InstOrderTraverse()*/
					return OK;
		return ERROR;	
	}
	else return OK;
}

Status PostOrderTraverse(BiTNode *Pnow,Status (* Visit)(TElemType e))
/*后序遍历二叉树，对数据元素用函数Visit访问*/
{
	if(Pnow)
	{
		if(PostOrderTraverse(Pnow->lchild,Visit))/*如果左孩子不为空，递归调用PoststOrderTraverse()*/
			if(PostOrderTraverse(Pnow->rchild,Visit))/*如果右孩子不为空，递归调用PoststOrderTraverse()*/
				if(Visit(Pnow->data))/*调用Visit函数访问当前数据元素*/
					return OK;
		return ERROR;	
	}
	else return OK;
}



void main()
{
	BiTNode T;
	Status (*Visit)(TElemType);
	char *str={"AB^^CDF^G^^^E^^"};
	char *str1={"ABC^^DE^G^^F^^^"};
	char *str2={"-+a^^*b^^-c^^d^^/e^^f^^"};
	int j=0;
	Visit=PrintElement;
	InitBiTree(T);	
	//CreatBiTree(T,&T,T.lchild,1);/*使用直接输入方式建立二叉树*/
	StrCreatBiTree(T,&T,T.lchild,1,str,j);/*使用字符串形式建立二叉树*/	
	printf("\n T has %d node\n",T.data);
	printBiTree(T.lchild);
	printf("\nPreOrderTraverse: ");
	PreOrderTraverse(T.lchild,Visit);
	printf("\nInstOrderTraverse: ");
	InOrderTraverse(T.lchild,Visit);
	printf("\nPostOrderTraverse: ");
	PostOrderTraverse(T.lchild,Visit);
	N;
	
}