include <windows.h>

//#include <malloc.h>

include <stdio.h>

include<conio.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int depth=0,count=0;
typedef char Elemtype;
typedef struct Node{
Elemtype data;
struct Node *lchild;
struct Node rchild;
}tNode,tree;

//函数声明
void createF(tree *flage);//先序show
void createM(tree *flage);
void createR(tree *flage);
void showF(tree flage);//先序show
void showM(tree flage);
void showR(tree flage);
void leafF(tree flage);//叶子计数
void leafM(tree flage);
void leafR(tree flage);
void hightree(tree flage,int f);//树高计数
int leaf(tree flage);//分治算法
void leafpath(tree flage,Elemtype ch);//路径算法
void leafpath1(tree flage);//路径算法
void menu(tree *flage); //遍历选择函数
void menu1(tree flage); //show选择函数
void menu2(tree flage); ///叶子计数函数
void swap(tree flage);//交换左右子树

int main(int argc, char** argv) {
int r,h=0;
Elemtype x;
tree flage;
menu(&flage);/遍历选择函数 /
while(1){
system("cls");
printf(" 0退出系统\n");
printf(" 1show函数 \n");
printf(" 2叶子计数 \n");
printf(" 3树高计数\n");
printf(" 4计算路径\n");
printf(" 5交换左右子树\n");
scanf("%d",&r);
system("cls");
switch(r){
case 0:printf("感谢使用！ ");printf("退出系统！\n");exit(0);
case 1:menu1(flage)/show选择函数 /;break;
case 2:menu2(flage)/叶子计数选择函数 /;break;
case 3:hightree(flage,h)/树高计数/ ;break;
case 4:leafpath1(flage)/路径算法/;break;
case 5:swap(flage);break;
default:printf(" 菜单选择错误！\n");
}
h=0;
if(r==3) printf("树高depth=%d\n",depth);
printf("按任意键继续.....\n");
getch();
}
return 0;
}

void menu(tree *flage){//遍历选择函数
int r;
printf(" 1先序遍历\n");
printf(" 2中序遍历\n");
printf(" 3后序遍历\n");
scanf("%d",&r);
system("cls");
printf("请输入,’#‘代表空树，例如ABCD##EF####G##HI##J#K##\n");
switch(1){
case 1:createF(flage);break;
case 2:createM(flage);break;
case 3:createR(flage);break;
default:printf(" 菜单选择错误！\n");

}

}

void menu1(tree flage){//show选择函数
int x;
while(1){
system("cls");
printf(" 0退返回上一界面\n");
printf(" 1先序输出\n");
printf(" 2中序输出\n");
printf(" 3后序输出\n");
scanf("%d",&x);
system("cls");
switch(x){
case 0:;return;
case 1:showF(flage);break;
case 2:showM(flage);break;
case 3:showR(flage);break;
default:printf(" 菜单选择错误！\n");
}
getch();
}
}

void menu2(tree flage){//叶子计数
int x;
while(1){
system("cls");
printf(" 0退返回上一界面\n");
printf(" 1先序叶子计数\n");
printf(" 2中序叶子计数\n");
printf(" 3后序叶子计数\n");
printf(" 4分治算法叶子计数\n"); //分治算法
scanf("%d",&x);
system("cls");
switch(x){
case 0:;return;
case 1:leafF(flage);break;
case 2:leafM(flage);break;
case 3:leafR(flage);break;
case 4:leaf(flage);break;//分治算法
default:printf(" 菜单选择错误！\n");
}printf("叶子数量count=%d\n",count);
getch();
count=0;
}
}

void createF(tree flage){//先序遍历
Elemtype ch;
ch=getchar();
depth++;
if(ch=='#') flage=NULL;
else{
flage=(tNode)malloc(sizeof(tNode));
(flage)->data=ch;
createF(&(flage)->lchild);
createF(&(*flage)->rchild);
}

}

void createM(tree flage){//中序遍历
Elemtype ch;
ch=getchar();
depth++;
if(ch=='#') flage=NULL;
else{
flage=(tNode)malloc(sizeof(tNode));
createM(&(flage)->lchild);
(flage)->data=ch;
createM(&(*flage)->rchild);
}

}

void createR(tree flage){//后序遍历
Elemtype ch;
ch=getchar();
depth++;
if(ch=='#') flage=NULL;
else{
flage=(tNode)malloc(sizeof(tNode));
createR(&(flage)->lchild);
createR(&(flage)->rchild);
(*flage)->data=ch;
}

}

void showF(tree flage){//先序show
if(flage==NULL) return;
else{
printf("%c",flage->data);
showF(flage->lchild);
showF(flage->rchild);
}

}

void showM(tree flage){//中序show
if(flage==NULL) return;
else{
showM(flage->lchild);
printf("%c",flage->data);
showM(flage->rchild);
}

}

void showR(tree flage){//后序show
if(flage==NULL) return;
else{
showR(flage->lchild);
showR(flage->rchild);
printf("%c",flage->data);
}

}

void leafF(tree flage){//叶子计数
if(flage!=NULL){
if(flage->lchildNULL && flage->rchildNULL){
count++;
}leafF(flage->lchild);
leafF(flage->rchild);
}
}

void leafM(tree flage){
if(flage!=NULL){
leafF(flage->lchild);
if(flage->lchildNULL && flage->rchildNULL){
count++;
}
leafF(flage->rchild);
}
}

void leafR(tree flage){
if(flage!=NULL){
leafF(flage->lchild);
leafF(flage->rchild);
if(flage->lchildNULL && flage->rchildNULL){
count++;
}
}
}

int leaf(tree flage){//分治算法
if(flageNULL) count=0;
else if(flage->lchildNULL && flage->rchild==NULL){
count=1;
}else{
count=leaf(flage->lchild)+leaf(flage->rchild);
}return count;
}

void hightree(tree flage,int f){//树高计数
if(flage!=NULL){
if(f>depth) depth=f;
hightree(flage->lchild,f+1);
hightree(flage->rchild,f+1);
}
}

void leafpath1(tree flage){
Elemtype x;
printf("请输入");
fflush(stdin);
x=getchar();
leafpath(flage,x);
}

void leafpath(tree flage,Elemtype ch){//路径算法
tree s[100];
int top=-1,i;
tree p,q;
p=flage;
q=NULL;
while(p!=NULL||top!=0)//判空
{
while(p!=NULL)
{ top++;
if (top>=100) return;//输入确认
s[top]=p;p=p->lchild;

 }
	if(top>0){
		p=s[top];
		
		if(p->rchild==NULL||p->rchild==q)
		{
			if(p->data==ch)
			{for(i=0;i<=top;i++)	printf("%c ",s[i]->data);top=0;}
				q=p;
				top--;
				p=NULL;
				
		}

		else p=p->rchild;
	}
}printf("输入错误!\n");

}

void swap(tree flage){
tree d;
if(flage){
swap(flage->lchild);//递归交换结点
swap(flage->rchild);//递归交换结点
d = flage->lchild;//交换左右子树
flage->lchild = flage->rchild;
flage->rchild = d;

}

}