二叉树的应用

（1）     创建一棵二叉树；

（2）     二叉树的先序递归遍历；

（3）     二叉树的中序递归遍历；

（4）     二叉树的后序递归遍历；

（5）     二叉树的层次遍历；

（6）     计算二叉树的深度；

（7）     统计二叉树中的叶子结点的个数；

（8）     统计二叉树中度为2的节点数；

（9）     输入任一结点值，输出其左、右孩子结点值；

（10）  输出某一结点在二叉树中的层数；

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int count = 0;	//定义计算结点个数的变量
typedef struct tnode{
	char data;	//二叉树结点值
	struct tnode *lchild,*rchild;
}BT;

/*以先序序列输入结点的值*/
BT *CreateBTree(){
	BT *t;
	char ch;
	scanf("%c",&ch);
	getchar();
	if(ch=='0')
		t = NULL;
	else{
		t = (BT*) malloc (sizeof (BT));
		t->data = ch;
		printf("请输入%c结点的左孩子的结点：",t->data);
		t->lchild = CreateBTree();
		printf("请输入%c结点的右孩子的结点：",t->data);
		t->rchild = CreateBTree();
	}
	return t;
}

/*先序遍历二叉树*/
void PreOrder(BT *T){
	if(T == NULL)
		return;
	else{
		printf("%c",T->data);	//输出结点的数据域
		PreOrder(T->lchild);	//先序遍历输出左子树
		PreOrder(T->rchild);	//先序遍历输出右子树 
	}
}
/*中序遍历二叉树*/
void InOrder(BT *T){
	if(T == NULL)
		return;
	else{
		InOrder(T->lchild);
		printf("%c",T->data);
		InOrder(T->rchild);
	}
}
/*后序遍历二叉树*/
void PostOrder(BT *T){
	if(T == NULL)
		return;
	else{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		printf("%c",T->data);
	}
}

/*二叉树的层次遍历*/
void LevelOrder(BT *T){
	int f,r;	//f：队列的头下标  r：队尾下一个位置的下标 
	BT *p,*q[MAX];
	p = T;
	if(p != NULL){	//若二叉树非空，则根结点地址入队 
		f = 1;
		q[f] = p;
		r = 2;
	}
	while(f != r){		//队列不为空时 
		p = q[f];	//用指针p 获取队首结点 
		printf("%c",p->data);
		if(p->lchild != NULL){
			q[r] = p->lchild;
			r = (r+1) % MAX;
		}
		if(p->rchild != NULL){
			q[r] = p->rchild;
			r = (r+1) % MAX;
		}
		f = (f+1) % MAX;
	}
}

/*计算二叉树的深度*/
int TreeDepth(BT *T){
	int ldep,rdep;
	if(T == NULL)
		return 0;
	else{
		ldep = TreeDepth(T->lchild);
		rdep = TreeDepth(T->rchild);
		if(ldep > rdep)
			return ldep+1;
		else
			return rdep+1;
	}
}

/*叶子结点的个数*/
void LeafNum(BT *T){
	if(T){	//若树不为空 
		if(T->lchild==NULL && T->rchild==NULL)
			count++;
		LeafNum(T->lchild);
		LeafNum(T->rchild);
	}
}

/*二叉树中度为2的节点数*/
int TwoNodesNum(BT *T){
	if (T == NULL)
		return 0;
	if (T->lchild != NULL && T->rchild != NULL)
		return 1 + TwoNodesNum(T->lchild) + TwoNodesNum(T->rchild);
	return TwoNodesNum(T->lchild) + TwoNodesNum(T->rchild);
}

/*输入任一结点值，输出其左、右孩子结点值*/
void GetChild(BT *T, char date_pre){
	if(T == NULL)
		return;
	else{
		if(T->data == date_pre)
		{
			if(T->lchild==NULL && T->rchild==NULL){
				printf("该结点为叶子结点，无左右孩子\n");
				return;
			}
			else if(T->lchild!=NULL && T->rchild==NULL){
				printf("%c的左孩子结点：%c\n%c无右孩子结点\n",T->data,T->lchild->data,T->data);
				return;
			}
			else if(T->lchild==NULL && T->rchild!=NULL){
				printf("%c无左孩子结点\n%c的右孩子结点：%c\n",T->data,T->data,T->rchild->data);
				return;
			}
			else{
				printf("%c的左孩子结点：%c\n%c的右孩子结点：%c\n",T->data,T->lchild->data,T->data,T->rchild->data);
				return;	
			}
		}
		GetChild(T->lchild,date_pre);	//先序遍历输出左子树
		GetChild(T->rchild,date_pre);	//先序遍历输出右子树
	}
}

/*查找date_pre在第几层*/
int Get_Level(BT *Q, char date_pre, int height){
	int h; 
	if(Q == NULL)
		return 0;
	else{
		if(Q->data == date_pre)
			return height;
		else{
			h = Get_Level(Q->lchild,date_pre,height+1);
			if (h!=0)
				return(h);
			else	
				return(Get_Level(Q->rchild,date_pre,height+1));
		}
	}
}

void MenuTree()
{
	    printf("           二叉树的各种操作");
		printf("\n==================================================");
		printf("\n|     1--创建一棵二叉树                          |");
		printf("\n|     2--二叉树的先序递归遍历                    |");
		printf("\n|     3--二叉树的中序递归遍历                    |");
		printf("\n|     4--二叉树的后序递归遍历                    |");
		printf("\n|     5--二叉树的层次遍历                        |");
		printf("\n|     6--计算二叉树的深度                        |");
		printf("\n|     7--统计二叉树中的叶子结点的个数            |");
		printf("\n|     8--统计二叉树中度为2的节点数               |");
		printf("\n|     9--输入任一结点值，输出其左、右孩子结点值  |");
		printf("\n|     M--输出某一结点在二叉树中的层数            |");
		printf("\n|     0--返回                                    |");
		printf("\n==================================================");	
		printf("\n请输入菜单号（0-10）：");
}

main(){
	BT *T=NULL;
	int f;
	char choice,a,m;
	while(1){
		MenuTree();
		scanf("%c",&choice);
		getchar();
		switch(choice){
			case '1':
				printf("请按先序遍历输入二叉树的结点：\n");
				printf("输入结点后按回车('0'表示该结点为空)\n");
				printf("请输入根结点：");
				T = CreateBTree();
				printf("二叉树建立成功！\n");
				break;
			case '2':
				printf("二叉树的先序遍历为：");
				PreOrder(T);
				break; 
			case '3':
				printf("二叉树的中序遍历为：");
				InOrder(T);
				break; 
			case '4':
				printf("二叉树的后序遍历为：");
				PostOrder(T);
				break; 
			case '5':
				printf("二叉树的层次遍历为：");
				LevelOrder(T);
				break;
			case '6':
				printf("二叉树的深度是：%d",TreeDepth(T));
				break;
			case '7':
				count = 0;
				LeafNum(T);
				printf("二叉树中的叶子结点的个数是：%d",count);
				break;
			case '8':
				printf("该二叉树中度为2的节点数：%d",TwoNodesNum(T));
				break;
			case '9':
				char num_pre;
				printf("输入任一结点值，输出其左、右孩子结点值");
				scanf("%c",&num_pre);
				GetChild(T,num_pre);
				break;
			case 'M':
				int level;
				char search_level;
				printf("请输入要查找的结点：");
				scanf(" %c",&search_level);
				level = Get_Level(T,search_level,1);
				if(level!=101)
					printf("%c结点的高度为%d",search_level,level);
				else
					printf("二叉树中没有该结点");
				break;
			case '0':
				exit(1);
			default:
				printf("输入有误，请重新在0-10中选择！");
		}
		if(choice != '0'){
			printf("\n按回车继续，按任意键返回主菜单！\n");
			a = getchar();
			if(a != '\xA'){
				getchar();
				exit(1);
			}
		}
	}
}