/////////////////////////////////////////////////////////// 

//--------------------------------------------------------- 

//            基于二叉链表实现二叉树的基本运算

//--------------------------------------------------------- 

/////////////////////////////////////////////////////////// 



#include<stdio.h> 

#include<stdlib.h>

#include<malloc.h>

#include<string.h>

#include<ctype.h>

#include"stack.h"



//以下为函数运行结果状态代码 

#define TRUE 1

#define FALSE 0

#define OK 1 

#define ERROR 0 

#define INFEASIBLE -1 

#define OVERFLOW -2 



/*typedef int Status; //函数类型，其值为函数结果状态代码

typedef char TElemType; //数据类型定为字符型 

typedef struct BiTNode{

		TElemType  data;//结点存储数据的值 

		BiTNode *lchild, *rchild;//指向左子树 

} *BiTree;*/ //二叉树结点的结构定义 

int index=0;

char str[100];



//-------------基本操作的函数原型说明----------------

Status InitBiTree(BiTree &T);              //构造空二叉树

Status DestroyBiTree(BiTree &T);           //销毁二叉树T

Status CreateBiTree(BiTree &T);            //构造二叉树T

Status ClearBiTree (BiTree &T);            //将二叉树T清空

Status BiTreeEmpty(BiTree T);              //判断二叉树是否为空

int BiTreeDepth(BiTree T);              //求二叉树的深度

TElemType Root(BiTree T);                     //返回T的根

TElemType Value(BiTree T,int e);                 //返回e的值

Status Assign(BiTree T,int &e,TElemType value);        //结点e赋值为value

BiTree Parent(BiTree T,int e);                //若e是T的非根结点，则返回它的双亲结点指针，否则返回NULL



BiTree LeftChild(BiTree T,int e);             //返回e的左孩子结点指针。若e无左孩子，则返回NULL

BiTree RightChild(BiTree T,int e);            //返回e的右孩子结点指针。若e无右孩子，则返回NULL

BiTree LeftSibling(BiTree T,int e);           //返回e的左兄弟结点指针。若e是T的左孩子或者无左兄弟，则返回NULL

BiTree RightSibling(BiTree T,int e);          //返回e的右兄弟结点指针。若e是T的右孩子或者无有兄弟，则返回NULL。

Status InsertChild(BiTree T,BiTree p,int LR,BiTree c);//根据LR为0或者1，插入c为T中p所指结点的左或右子树，p所指结点的原有左子树或右子树则为c的右子树

Status DeleteChild(BiTree T,BiTree p,int LR);       //根据LR为0或者1，删除c为T中p所指结点的左或右子树。

Status PreOrderTraverse(BiTree T);         //先序遍历T

Status InOrderTraverse(BiTree T);          //中序遍历T

Status PostOrderTraverse(BiTree T);        //后序遍历T

Status LevelOrderTraverse(BiTree T);       //层序遍历T



//-----------基本操作的算法----------------

Status InitBiTree(BiTree &T){

	//构造空二叉树

	BiTNode *NT=(BiTNode * )malloc(sizeof(BiTNode));

	NT->lchild=NULL;

	NT->rchild=NULL;

	NT->data='#';

	T=NT;

	return OK;

}





Status DestroyBiTree(BiTree &T){

	//销毁二叉树T

	if(T){

		if(T->lchild)

			DestroyBiTree(T->lchild);

		if(T->rchild)

			DestroyBiTree(T->rchild);

		free(T);

		T=NULL;

	}

	return OK;

}



Status ClearBiTree(BiTree &T){

	//将二叉树清空

	DestroyBiTree(T);

	BiTree TP;

	T=TP;

	InitBiTree(T);

	return OK;

}



Status BiTreeEmpty(BiTree T){

	if(!T){//二叉树不存在

		return INFEASIBLE;

	}

	if(T->data=='#'){

		return TRUE;

	}

	return FALSE;

}



/*Status AssignStr(char *br,char *tr){

	int i;

	br[0]=strlen(tr);

	for(i=0;i<br[0];i++){

		br[i+1]=*(tr+i);

	}

	return OK;

}*/



Status CreateBiTree(BiTree &T){

	//构造二叉树

	//按先序次序输入二叉树中结点的值（一个字符）,'#'表示空树

	char ch;

	ch = str[index++];

	if(ch=='#'){

		T=NULL;

		return OK;

	}

	else{

		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

			exit(ERROR);

		T->data=ch;

		CreateBiTree(T->lchild);//递归构造左子树

		CreateBiTree(T->rchild);//递归构造右子树

	}

	return OK;

}



int BiTreeDepth(BiTree T){

	//求二叉树的深度

	int deep=0;

	if(T){

		int lchildDepth=BiTreeDepth(T->lchild);

		int rchildDepth=BiTreeDepth(T->rchild);

		deep=lchildDepth>=rchildDepth?lchildDepth+1:rchildDepth+1;

	}

	return deep;

}



TElemType Root(BiTree T){

	if(T->data=='#'){

		printf("T为空\n");

		return 0;

	}

	return T->data;

}



TElemType Value(BiTree T,int e){

	//返回e的值,e为满二叉树中的序号

	int i=0,j,n=e;

	char str[20]={0};

	char output[20]={0};

	BiTree p=T,pri_p;

	while(n){

		str[i]=n%2+'0';

		n=n/2;

		i++;

	}

	for(j=0;j<i;j++){

		output[j]=str[i-1-j];

	}//把e转换为二进制数保存在数组output中

	for(j=1;j<i;j++){

		pri_p=p;

		if(output[j]=='1'){

			p=p->rchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",e);

				return '#';

			}

		}

		else{

			p=p->lchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",e);

				return '#';

			}

		}

	}

	return p->data;

}



Status Assign(BiTree T,int &e,TElemType value){

	int i=0,j,n=e;

	char str[20]={0};

	char output[20]={0};

	BiTree p=T,pri_p;

	while(n){

		str[i]=n%2+'0';

		n=n/2;

		i++;

	}

	for(j=0;j<i;j++){

		output[j]=str[i-1-j];

	}//把e转换为二进制数保存在数组output中

	for(j=1;j<i;j++){

		pri_p=p;

		if(output[j]=='1'){

			p=p->rchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",e);

				return OVERFLOW;

			}

		}

		else{

			p=p->lchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",e);

				return OVERFLOW;

			}

		}

	}

	p->data=value;

	return OK;

}



BiTree Parent(BiTree T,int e){

	//若e是T的非根结点，则返回它的双亲结点指针，否则返回NULL

	int ee=e;

	if(e==1){

		return NULL;

	}

	ee=ee/2;//第e个结点的双亲结点的序号

	int i=0,j,flag=0;

	char str[20]={0};

	char output[20]={0};

	BiTree p=T,pri_p;

	while(ee){

		str[i]=ee%2+'0';

		ee=ee/2;

		i++;

	}

	for(j=0;j<i;j++){

		output[j]=str[i-1-j];

	}//把ee转换为二进制数保存在数组output中

	for(j=1;j<i;j++){

		pri_p=p;

		if(output[j]=='1'){

			p=p->rchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",ee);

				return NULL;

			}

		}

		else{

			p=p->lchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",ee);

				return NULL;

			}

		}

	}

	return p;

}



BiTree LeftChild(BiTree T,int e){

	//返回e的左孩子结点指针。若e无左孩子，则返回NULL

	int i=0,j,n=e;

	char str[20]={0};

	char output[20]={0};

	BiTree p=T,pri_p;

	while(n){

		str[i]=n%2+'0';

		n=n/2;

		i++;

	}

	for(j=0;j<i;j++){

		output[j]=str[i-1-j];

	}//把e转换为二进制数保存在数组output中

	for(j=1;j<i;j++){

		pri_p=p;

		if(output[j]=='1'){

			p=p->rchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",e);

				return NULL;

			}

		}

		else{

			p=p->lchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",e);

				return NULL;

			}

		}

	}

	return p->lchild;

}



BiTree RightChild(BiTree T,int e){

	//返回e的右孩子结点指针。若e无右孩子，则返回NULL

	int i=0,j,n=e;

	char str[20]={0};

	char output[20]={0};

	BiTree p=T,pri_p;

	while(n){

		str[i]=n%2+'0';

		n=n/2;

		i++;

	}

	for(j=0;j<i;j++){

		output[j]=str[i-1-j];

	}//把e转换为二进制数保存在数组output中

	for(j=1;j<i;j++){

		pri_p=p;

		if(output[j]=='1'){

			p=p->rchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",e);

				return NULL;

			}

		}

		else{

			p=p->lchild;

			pri_p=p;

			if(p==NULL){

				printf("该二叉树不存在第%d个元素\n",e);

				return NULL;

			}

		}

	}

	return p->rchild;

}



BiTree LeftSibling(BiTree T,int e){

	//返回e的左兄弟结点指针。若e是T的左孩子或者无左兄弟，则返回NULL

	if(e%2==0){

		return NULL;

	}

	BiTree Par;

	Par=Parent(T,e);

	if(Par){

		return Par->lchild;

	}

	return NULL;

}



BiTree RightSibling(BiTree T,int e){

	//返回e的右兄弟结点指针。若e是T的右孩子或者无右兄弟，则返回NULL

	if(e%2==1){

		return NULL;

	}

	BiTree Par;

	Par=Parent(T,e);

	if(Par){

		return Par->rchild;

	}

	return NULL;

}



Status InsertChild(BiTree T,BiTree p,int LR,BiTree c){

	//根据LR为0或者1，插入c为T中p所指结点的左或右子树，p所指结点的原有左子树或右子树则为c的右子树

	if(c->rchild){

		return ERROR;

	}

	BiTree temp=(!LR)?p->lchild:p->rchild;

	((!LR)?p->lchild:p->rchild)=c;

	c->rchild=temp;

	return OK;

}



Status DeleteChild(BiTree T,BiTree p,int LR){

	//根据LR为0或者1，删除c为T中p所指结点的左或右子树

	if(!LR&&p->lchild){

		DeleteChild(T,p->lchild,0);

		DeleteChild(T,p->lchild,1);

	}

	else if(LR&&p->rchild){

		DeleteChild(T,p->rchild,0);

		DeleteChild(T,p->rchild,1);

	}

	free((!LR)?p->lchild:p->rchild);

	((!LR)?p->lchild:p->rchild)=NULL;

	return OK;

}



Status PreOrderTraverse(BiTree T){

	//先序遍历T

	BiTree p=T;

	SqStack S;

	InitStack(S);

	while(p||!StackEmpty(S)){

		if(p){

			printf("%c ",p->data);

			Push(S,p);

			p=p->lchild;

		}

		else {

			Pop(S,p);

			p=p->rchild;

		}

	}

}



Status InOrderTraverse(BiTree T){

	//中序遍历T

	BiTree p=T;

	SqStack S;

	InitStack(S);

	

	while(p||!StackEmpty(S)){

		if(p){

			Push(S,p);

			p=p->lchild;

		}

		else {

			Pop(S,p);

			printf("%c ",p->data);

			p=p->rchild;

		}

	}

}



Status PostOrderTraverse(BiTree T){

	//后序遍历T

	BiTree p=T;

	SqStack S;

	int k[100];

	InitStack(S);

	

	while(p||!StackEmpty(S)){

		while(p!=NULL){

			Push(S,p);

			k[StackLength(S)-1]=0;

			p=p->lchild;

		}

		while(!StackEmpty(S)&&k[StackLength(S)-1]==1){

			Pop(S,p);

			printf("%c ",p->data);

		}

		if(!StackEmpty(S)){

			k[StackLength(S)-1]=1;

			GetTop(S,p);

			p=p->rchild;

		}

		else break;

	}

}



Status LevelOrderTraverse(BiTree T){

	//层序遍历T

	BiTree q[100],ql[100],qr[100],p;

	int i,j,k,lev_num,dep=BiTreeDepth(T);

	p=T;

	q[0]=T;

	for(i=1;i<100;i++){

		q[i]=NULL;

	}

	for(k=0;k<dep;k++){

		lev_num=1;

		for(i=0;i<k;i++){

			lev_num*=2;

		}//每层的满二叉树结点数目

		for(i=0;i<lev_num;i++){

			if(q[i]){

				printf("%c ",q[i]->data);

				ql[i]=q[i]->lchild;

				qr[i]=q[i]->rchild;

			}

			else {

				ql[i]=NULL;

				qr[i]=NULL;

			}

		}//输出每层的结点，并把每个结点的左右孩子指针记录到两个数组中

		for(j=0;j<i;j++){

			q[2*j]=ql[j];

			q[2*j+1]=qr[j];

		}//把两个数组合并到一个数组

	}

}











int main(){

	strcpy(str,"ABDH#K###E##CFI###G#J##");

	BiTree T,pri,P;//P作为要插入的树

	int e;

	TElemType elem;

	int op=1;

	while(op){

		system("cls");

		printf("\n\n");

		printf("\tMenu for Bitree\n");

		printf("\t-------------------------------------------------\n");

		printf("\t\t1.InitaBitree\t\t12.RightChild\n");

		printf("\t\t2.DestroyBiTree\t\t13.LeftSibling\n");

		printf("\t\t3.CreateBiTree\t\t14.RightSibling\n");

		printf("\t\t4.ClearBiTree\t\t15.InsertChild\n");

		printf("\t\t5.BiTreeEmpty\t\t16.DeleteChild\n");

		printf("\t\t6.BiTreeDepth\t\t17.PreOrderTraverse\n");

		printf("\t\t7.Root\t\t\t18.InOrderTraverse\n");

		printf("\t\t8.Value\t\t\t19.PostOrderTraverse\n");

		printf("\t\t9.Assign\t\t20.LevelOrderTraverse\n");

		printf("\t\t10.Parent\t\t\n");

		printf("\t\t11.LeftChild\t\t\n");

		printf("\t-------------------------------------------------\n");

		printf("\t请选择你的操作[0~20]:");

		scanf("%d",&op);

		switch(op){

			case 1:

			{

				if(InitBiTree(T)){

					printf("空二叉树创建成功\n");

				}

				else {

					printf("空二叉树创建失败\n");

				}

				getchar();getchar();getchar();

			}

			break;

			case 2:

			{

				if(DestroyBiTree(T)){

					printf("二叉树销毁成功\n");

				}

				else {

					printf("二叉树销毁失败\n");

				}

				getchar();getchar();getchar();

			}

			break;

			case 3:

			{

				if(CreateBiTree(T)){

					printf("二叉树构造成功\n");

				}

				else {

					printf("二叉树构造失败\n");

				}

				getchar();getchar();getchar();

			}

			break;

			case 4:

			{

				if(ClearBiTree(T)){

				printf("二叉树清空成功\n");

				}

				else {

					printf("二叉树清空失败\n");

				}

				getchar();getchar();getchar();

			}

			break;	

			case 5:

			{

				if(BiTreeEmpty(T)){

					printf("二叉树是空的\n");

				}

				else {

					printf("二叉树不是空的\n");

				}

				getchar();getchar();getchar();

			}

			break;

			case 6:

			{

				int deptt;

				deptt=BiTreeDepth(T);

				printf("树的深度是%d\n",deptt);

				getchar();getchar();getchar();

			}

			break;

			case 7:

			{

				elem=Root(T);

				printf("树的根是%c\n",elem);

				getchar();getchar();getchar();

			}

			break;

			case 8:

			{

				printf("请输入要查找的结点在满二叉树中的对应位置：");

				scanf("%d",&e);

				elem=Value(T,e);

				printf("第%d个结点的数据是%c",e,elem);

				getchar();getchar();getchar();

			}

			break;

			case 9:

			{

				printf("请输入要赋值的位置的要赋的值：");

				scanf("%d%c",&e,&elem);

				getchar();

				if(Assign(T,e,elem)){

					printf("赋值成功\n");

				}

				else {

					printf("赋值失败\n");

				}

				getchar();getchar();getchar();

			}

			break;

			case 10:

			{

				printf("请输入要查找双亲结点的结点在满二叉树中的序号:");

				scanf("%d",&e);

				getchar();

				pri=Parent(T,e);

				printf("第%d个结点的双亲结点的指针是%d,数据是%c",e,pri,pri->data);

				getchar();getchar();getchar();

			}

			break;

			case 11:

			{

				printf("请输入要查找左孩子结点的结点在满二叉树中的序号:");

				scanf("%d",&e);

				pri=LeftChild(T,e);

				if(pri){

					printf("第%d个结点的左孩子结点的指针是%d,数据是%c",e,pri,pri->data);

				}

				else {

					printf("不存在此结点或此结点无左孩子");

				}

				getchar();getchar();getchar();

			}

			break;

			case 12:

			{

				printf("请输入要查找右孩子结点的结点在满二叉树中的序号:");

				scanf("%d",&e);

				pri=RightChild(T,e);

				if(pri){

					printf("第%d个结点的右孩子结点的指针是%d,数据是%c",e,pri,pri->data);

				}

				else {

					printf("不存在此结点或此结点无右孩子");

				}

				getchar();getchar();getchar();

			}

			break;

			case 13:

			{

				printf("请输入要查找左兄弟结点的结点在满二叉树中的序号:");

				scanf("%d",&e);

				pri=LeftSibling(T,e);

				if(pri){

					printf("第%d个结点的左兄弟结点的指针是%d,数据是%c",e,pri,pri->data);

				}

				else {

					printf("不存在此结点或此结点无左兄弟");

				}

				getchar();getchar();getchar();

			}

			break;

			case 14:

			{

				printf("请输入要查找右兄弟结点的结点在满二叉树中的序号:");

				scanf("%d",&e);

				pri=RightSibling(T,e);

				if(pri){

					printf("第%d个结点的右兄弟结点的指针是%d,数据是%c",e,pri,pri->data);

				}

				else {

					printf("不存在此结点或此结点无右兄弟");

				}

				getchar();getchar();getchar();

			}

			break;

			case 15:

			{

				index=0;

				if(CreateBiTree(P)){

					;

				} 

				else {

					printf("二叉树P构造失败\n");

					break;

				}

				DeleteChild(T,T,1);

				P->rchild=NULL;//根据插入要求将P树右孩子置空，以便插入

				printf("P是与T删去右子树之后相同的树\n");

				printf("树P已构造，要插入为左子树还是右子树?请输入0或1:");

				int LR;

				scanf("%d",&LR);

				getchar();

				if(InsertChild(T,T->lchild,LR,P)){

					printf("树P插入成功\n");

				}

				else {

					printf("树P插入失败\n");

				}

				getchar();getchar();getchar();

			}

			break;

			case 16:

			{

				printf("P是T的左子树\n");

				printf("要删除P的左子树还是右子树?请输入0或1:");

				int LR;

				scanf("%d",&LR);

				getchar();

				if(DeleteChild(T,T->lchild,LR)){

					printf("删除成功\n");

				}

				else {

					printf("删除失败\n");

				}

				getchar();getchar();getchar();

			}

			break;

			case 17:

			{

				printf("树T前序遍历为：\n");

				PreOrderTraverse(T);

				printf("\n--------The End-------");

				getchar();getchar();getchar();

			}

			break;

			case 18:

			{

				printf("树T中序遍历为：\n");

				InOrderTraverse(T);

				printf("\n--------The End-------");

				getchar();getchar();getchar();

			}

			break;

			case 19:

			{

				printf("树T后序遍历为：\n");

				PostOrderTraverse(T);

				printf("\n--------The End-------");

				getchar();getchar();getchar();

			}

			break;

			case 20:

			{

				printf("树T层序遍历为：\n");

				LevelOrderTraverse(T);

				printf("\n--------The End-------");

				getchar();getchar();getchar();

			}

			break;

		}

	}

}