#include<iostream.h>
struct node
{
	int data;
	node*lchild;
	node*rchild;
};
find(node*p,int a,node*q)
{
	node*pre=NULL;
	if((p!=NULL)&&(a<p->data))
	{
    while((p!=NULL)&&(a<p->data))
	{
		pre=p;
		p=p->lchild;
	}
	if(p==NULL)
		pre->lchild=q;
	else 
		find(p,a,q);
	}
   if((p!=NULL)&&(a>p->data))
	{
	while((p!=NULL)&&(a>p->data))
	{
		pre=p;
		p=p->rchild;
	}
	if(p==NULL)
		pre->rchild=q;
	else 
		find(p,a,q);
	}
}
node*creattree()
{
	node*root=NULL,*q=NULL;
	int num;
	cout<<"please put in the number of num,when want to end please put in -1"<<endl;
	cin>>num;
	if(num==-1)
		return NULL;
	else
	{
		root=new node;
		root->data=num;
		root->lchild=NULL;
    	root->rchild=NULL;
	}	
	cout<<"please put in the number of num,when want to end please put in -1"<<endl;
	cin>>num;
	while(num!=-1)
	{
		q=new node;
		q->data=num;
		q->lchild=NULL;
		q->rchild=NULL;
		find(root,num,q);
		cout<<"please put in the number of num,when want to end please put in -1"<<endl;
	    cin>>num;
	}
	return root;
}
travel(node*p)
{
	if(p->lchild)
		travel(p->lchild);
	cout<<p->data<<endl;
		if(p->rchild)
			travel(p->rchild);
		
}
btravel(node*p)
{
	cout<<p->data<<endl;
	if(p->lchild)
		btravel(p->lchild);//測試手段要正確，不是travel,是btravel
	
		if (p->rchild)
			btravel(p->rchild);
		
		
}
ctravel(node*p)
{
	if(p->lchild)
		ctravel(p->lchild);
	 if(p->rchild)
			ctravel(p->rchild);
		cout<<p->data<<endl;
		
}
int depth(node*p)
{
	int i=0,j=0,max=0;
	if(p)
	max++;
	if(p->lchild)
		i=depth(p->lchild);
	if(p->rchild)
		j=depth(p->rchild);
	if(i>=j)
		max+=i;
	else
		max+=j;
	return max;
}
main()
{
	node*p=creattree();
	travel(p);
	cout<<endl<<endl;
	btravel(p);
	cout<<endl<<endl;
	ctravel(p);
	cout<<endl<<endl<<"the depth of the tree is "<<depth(p)<<endl;
}