/*二叉树递归遍历*/
#include<stdio.h>
#include<malloc.h>
typedef char ElemType;
typedef struct BitNode
{
	ElemType data;
	struct BitNode * lchild,*rchild;
}BitNode,*BitTree;
void InitTree(BitTree &T)
{
	T=(BitNode *)malloc(sizeof(BitNode));
	T=NULL;
}
void InsertTree1(BitNode *&T,ElemType value)
{	

}
void InsertTree2(BitNode *&T,ElemType value)	//二叉排序树插入
{
	BitNode *Q;
	if(T==NULL)
	{
		Q=(BitNode *)malloc(sizeof(BitNode));
		Q->data=value;
		Q->lchild=NULL;
		Q->rchild=NULL;
		T=Q;
		return ;
	}
	if(T->data > value)
		InsertTree2(T->lchild,value);
	if(T->data < value)
		InsertTree2(T->rchild,value);
}
void visit(BitNode *p)
{
	printf("%c\t",p->data);
}
void PreOrder(BitTree T)	//1.先序遍历
{
	if(T!=NULL)
	{
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
void InOrder(BitTree T)		//2.中序遍历
{
	if(T!=NULL)
	{
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}
void PostOrder(BitTree T)	//3.后序遍历
{
	if(T!=NULL)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}
void DeepTree(BitTree T)	//4.求树的深度
{

}
void main()
{
	BitNode *T;
	InitTree(T);
	InsertTree2(T,'6');
	InsertTree2(T,'3');
	InsertTree2(T,'2');
	InsertTree2(T,'4');
	InsertTree2(T,'5');
	InsertTree2(T,'7');
	InsertTree2(T,'8');
	InsertTree2(T,'1');
	PreOrder(T);
	printf("\n");
	InOrder(T);
	printf("\n");
	PostOrder(T);
	printf("\n");
}