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

#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;
		}
	}
	return OK; 
}

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;
		}
	}
	return OK;
}

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;
	}
	return OK;
}

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];
		}//把两个数组合并到一个数组
	}
	return OK;
}

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