#include<iostream.h>
#include<STRSTREAM.H>
typedef int elemtype;
struct bstnode
{
	elemtype data;
	bstnode *lchild;
	bstnode *rchild;
};

void initbtree ( bstnode *&bst )
{ bst=NULL;}

int bstreeempty ( bstnode *bst )
{ return bst==NULL;}

int find ( bstnode *bst,elemtype &x )
{
	if ( bst==NULL )
		return 0;
	else  if ( x==bst->data )
	{
		x=bst->data;
		return 1;
	}
	else if ( x<bst->data )
		return find ( bst->lchild,x );
	else
		return find ( bst->rchild,x );
}

int update ( bstnode *bst,elemtype x )
{
	if ( bst==NULL )
		return 0;
	else if ( x==bst->data )
	{
		bst->data=x;
		return 1;
	}
	else if ( x<bst->data )
		return update ( bst->lchild,x );
	else
		return update ( bst->rchild,x );
}

void insert ( bstnode *&bst,elemtype x )
{
	if ( bst==NULL )
	{
		bstnode *p=new bstnode;
		p->data=x;
		p->lchild=p->rchild=NULL;
		bst=p;
	}
	else if ( x<bst->data )
		insert ( bst->lchild,x );
	else
		insert ( bst->rchild,x );
}

int dele ( bstnode *&bst,elemtype x )
{
	bstnode *t=bst,*s=NULL;
	while ( t!=NULL )
	{
		if ( x==t->data )  break;
		else if ( x<t->data )
			{ s=t; t=t->lchild;}
		else
			{ s=t; t=t->lchild;}
	}
	if ( t==NULL )  return 0;
	if ( t->lchild==NULL&&t->rchild==NULL )
	{
		if ( t==bst )
			bst=NULL;
		else if ( t==s->lchild )
			s->lchild=NULL;
		else
			s->rchild=NULL;
		delete t;
	}
	else if ( t->lchild==NULL||t->rchild==NULL )
	{
		if ( bst==t )
		{
			if ( t->lchild==NULL )
				bst=t->rchild;
			else
				bst=t->lchild;
		}
		else
		{
			if ( t==s->lchild&&t->lchild!=NULL )
				s->lchild=t->lchild;
			else if ( t==s->lchild&&t->rchild!=NULL )
				s->lchild=t->rchild;
			else if ( t==s->rchild&&t->lchild!=NULL )
				s->rchild=t->lchild;
			else if ( t==s->rchild&&t->rchild!=NULL )
				s->rchild=t->rchild;
		}
		delete t;
	}
	else if ( t->lchild!=NULL&&t->rchild!=NULL )
	{
		bstnode *p=t,*q=t->lchild;
		while ( q->rchild!=NULL )
		{
			p=q;
			q=q->rchild;
		}
		t->data=q->data;
		if ( p==t ) t->lchild=q->lchild;
		else p->rchild=q->lchild;
		delete q;
	}
	return 1;
}

void createbstree ( bstnode *&bst,elemtype a[],int n )
{
	bst=NULL;
	for ( int i=0; i<n; i++ )
		insert ( bst,a[i] );
}

void inorder ( bstnode *bst )
{
	if ( bst!=NULL )
	{
		inorder ( bst->lchild );
		cout<<bst->data<<' ';
		inorder ( bst->rchild );
	}
}

int bstreedepth ( bstnode *bst )
{
	if ( bst==NULL )
		return 0;
	else
	{
		int dep1=bstreedepth ( bst->lchild );
		int dep2=bstreedepth ( bst->rchild );
		if ( dep1>dep2 )
			return dep1+1;
		else
			return dep2+1;
	}
}

int bstreecount ( bstnode *bst )
{
	if ( bst==NULL )
		return 0;
	else
		return bstreecount ( bst->lchild ) +bstreecount ( bst->rchild ) +1;

}

int bstreeleafcount ( bstnode *bst )
{
	if ( bst==NULL )
		return 0;
	else if ( bst->lchild==NULL&&bst->rchild==NULL )
		return 1;
	else return bstreeleafcount ( bst->lchild ) +bstreeleafcount ( bst->rchild );
}

void printbstree ( bstnode *bst )
{
	if ( bst==NULL )
		return;
	else
	{
		cout<<bst->data;
		if ( bst->lchild!=NULL||bst->rchild!=NULL )
		{
			cout<<'(';
			printbstree ( bst->lchild );
			if ( bst->rchild!=NULL )
				cout<<',';
			printbstree ( bst->rchild );
			cout<<')';
		}
	}
}

void clearbstree ( bstnode *&bst )
{
	if ( bst!=NULL )
	{
		clearbstree ( bst->lchild );
		clearbstree ( bst->rchild );
		delete bst;
		bst=NULL;
	}
}

void main()
{
	elemtype a[10]={30,50,20,70,25,54,80,23,92,40};
	bstnode *bst=NULL;
	createbstree ( bst,a,10 );
	cout<<"output bstree:"<<endl;
	printbstree ( bst );
	cout<<endl;
	cout<<"inorder list:"<<endl;
	inorder ( bst );
	cout<<endl;
	elemtype x;
	cout<<"input find is x:";
	cin>>x;
	if ( find ( bst,x ) )
		cout<<"ok!!!"<<endl;
	else
		cout<<"fail!!!"<<endl;
	insert ( bst,36 );
	dele ( bst,30 );
	dele ( bst,20 );
	cout<<"op end inorder:"<<endl;
	inorder ( bst );
	cout<<endl;
	cout<<"op end glist:"<<endl;
	printbstree ( bst );
	cout<<endl;
	clearbstree ( bst );
}