#include<stdio.h>
#include<stdlib.h>

#define MAX 100
typedef char DataType;

typedef struct tnode{
	DataType data;
	struct tnode *rc;//右孩子 
	struct tnode *lc;//左孩子 
}BT;

//先序遍历 
void DLR(BT *T)
{
	if(T != NULL)
	{
		printf("%c",T->data);
		DLR(T->lc);//遍历左子树 
		DLR(T->rc);
	}
}

//中序遍历 
void LDR(BT *T)
{
	if(T != NULL)
	{
		LDR(T->lc);
		printf("%c",T->data);
		LDR(T->rc);
	}
}

//后序遍历 
void LRD(BT *T)
{
	if(T != NULL)
	{
		LRD(T->lc);
		LRD(T->rc);
		printf("%c",T->data);
	}
}

//层次遍历 
void LevelOrder(BT *T)
{
	int f,r;		//定义队头队尾指针 
	BT *p,*q[MAX];	//定义循环队列，存放节点指针 
	p=T;
	if(p!=NULL)		//若二叉树非空，则根节点地址入队 
	{
		f = 1;
		q[f] = p;
		r = 2;
	}
	while(f!=r)
	{
		p=q[f];
		printf("%c",p->data);
		if(p->lc != NULL)//队首节点的左孩子入队 
		{
			q[r] = p->lc;
			r = (r+1)%MAX;
		}
		if(p->rc != NULL)//队首节点的有孩子入队 
		{
			q[r] = p->rc;
			r = (r+1)%MAX;
		}
		f = (f+1)%MAX;
	}
}


//建立二叉树
BT *CreateBTree()
{
	BT* t;
	char ch;
	printf("请输入根节点\n"); 
	scanf("%c",&ch);
	getchar();
	if(ch == '0')
	{
		t = NULL;
	}
	else
	{
		t = (BT*)malloc(sizeof(BT));
		t->data = ch;
		printf("请输入%c节点的左孩子节点(输入0取消输入)\n",t->data);
		t->lc = CreateBTree();
		printf("请输入%c节点的右孩子节点(输入0取消输入)\n",t->data);
		t->rc = CreateBTree();
	}
	return t;
} 

//展示树 
void ShowBTree(BT *T)
{
	if(T != NULL)
	{
		printf("%c",T->data);
		if(T->lc != NULL)
		{
			printf("(");
			ShowBTree(T->lc);
			if(T->rc != NULL)
			{
				printf(",");
				ShowBTree(T->rc);
			}
			printf(")");
		}
		else if(T->rc != NULL)
		{
			printf("(");
			ShowBTree(T->lc);
			if(T->rc != NULL)
			{
				printf(",");
				ShowBTree(T->rc);
			}
			printf(")");
		}
	}
}

//返回叶子节点数量 
int leaf_num(BT *T)
{
    if (T == NULL)
        return 0;
    if (T->lc == NULL && T->rc == NULL)
        return 1;

    return (leaf_num(T->lc) + leaf_num(T->rc));
}

//求总结点数 
int node_num(BT *T)
{
	int tmp1 = 0, tmp2 = 0;
	if(T == NULL)
		return 0;
	tmp1 = node_num(T->lc);
	tmp2 = node_num(T->rc);
	return 1+tmp1+tmp2;
}

//求树的深度 
int TreeDepth(BT *T)
{
	int ldepth = 0;//左深度 
	int rdepth = 0;//右深度 
	if(T == NULL)
	{
		return 0;
	}
	else
	{
		ldepth = TreeDepth(T->lc);
		rdepth = TreeDepth(T->rc);
		if(ldepth > rdepth)
			return ldepth+1;
		else
			return rdepth+1;
	}
}

//菜单 
void menu()
{
	char word[][30]={{"1.建立二叉树\n"},{"2.输出二叉树\n"},{"3.先序遍历\n"},{"4.中序遍历\n"},{"5.后序遍历\n"},{"6.层次遍历\n"},
					{"7.输出叶子节点数量\n"},{"8.输出二叉树总节点数\n"},{"9.输出树的深度\n"},{"0.退出\n"}};
	for(int i = 0;i<10;i++)
	{
		printf("%s",word[i]);
	}
}


int main()
{
	//menu();
	BT* tree = NULL;
	char ch = '0';
	while(1)
	{
		system("cls");
		menu();
		scanf("%c",&ch);
		getchar();
		
		switch(ch)
		{
			case '1':
				tree = CreateBTree();
				printf("建立树成功！\n");
				break;
			case '2':
				ShowBTree(tree);
				printf("\n");
				break;
			case '3':
				DLR(tree);
				break;
			case '4':
				LDR(tree);
				break;
			case '5':
				LRD(tree);
				break;
			case '6':
				LevelOrder(tree);
				break;
			case '7':
				printf("\n");
				printf("叶子节点的数量是%d\n",leaf_num(tree));
				break;
			case '8':
				printf("树的总节点数为%d\n",node_num(tree));
				break;
			case '9':
				printf("树的深度为%d\n",TreeDepth(tree));
				break;
			case '0':
				return 0;
				 
		}
		system("pause");
	}
}