#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode{
	int data;
	BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTNode *CreatTree(){
	BiTNode *t;
	int x;
	scanf("%d",&x);
	getchar();
	if(x==0) t=NULL;
	else{
		t =(BiTree)malloc(sizeof(BiTNode));
		t->data=x;
		printf("请输入%d结点的左结点：",t->data);
		t->lchild=CreatTree();
		printf("请输入%d结点的右结点：",t->data);
		t->rchild=CreatTree();	 
	} 
	return t;
}
//	先序遍历 
void PreOrder(BiTNode *T){
	if(T){
		printf("%3d",T->data);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
} 
//	中序遍历 
void InOrder(BiTNode *T){
	if(T){
		InOrder(T->lchild);
		printf("%3d",T->data);
		InOrder(T->rchild);
	}
} 
//	后序遍历 
void PostOrder(BiTNode *T){
	if(T){
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		printf("%3d",T->data);
	}
}
//	层次遍历
void levelOder(BiTNode *T){
	int i,j;
	BiTNode *q[100],*p;
	p=T;
	if(p!=NULL){
		i=1;
		q[i]=p;
		j=2;
	}
	while(i!=j){
		p=q[i];
		printf("%3d",p->data);
		if(p->lchild!=NULL){
			q[j]=p->lchild;
			j++;
		}
		if(p->rchild!=NULL){
			q[j]=p->rchild;
			j++;
		}
		i++;	
	}
	
} 
//	求叶子数
void LeafNum(BiTNode *T){
	if(T){
		if(T->lchild==NULL&&T->rchild==NULL)count++;
		LeafNum(T->lchild);
		LeafNum(T->rchild);
	}
}
//	求结点数
void NodeNum(BiTNode *T){
	if(T){
		count++;
		NodeNum(T->lchild);
		NodeNum(T->rchild);
	}
}
//	求树的深度 
void TreeDepth(BiTNode *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;
	}
}

int main(){
	BiTNode *T=NULL;
	printf("输入根节点："); 
	T=CreatTree();
	printf("\n");
	PreOrder(T);
	printf("\n");
	InOrder(T);
	printf("\n");
	PostOrder(T);
	printf("\n");
	levelOder(T);
}