#include
#include
#include
#include
using namespace std;
typedef struct node
{
	int data;
	struct node  *lchild,*rchild;
}bstnode;
class BST
{
	public:
		double sum1,sum2;
		bstnode *root;
		BST()
		{
			root=NULL;
		}
		void display(bstnode *b)
		{
			if(b!=NULL)
			{
				printf("%d",b->data);
				if(b->lchild!=NULL||b->rchild!=NULL)
				{
					printf("(");
					display(b->lchild);
					if(b->rchild!=NULL)
						printf(",");
					display(b->rchild);
					printf(")");
				}
			}
		}
		void ll(bstnode *&b)
		{
			bstnode *temp=b->lchild->rchild;
			b->lchild->rchild=b->rchild;
			b->rchild=b->lchild;
			b->lchild=b->rchild->lchild;
			b->rchild->lchild=temp;
			int a=b->data;
			b->data=b->rchild->data;
			b->rchild->data=a;
		}
		void rr(bstnode *&b)
		{
			bstnode *temp=b->rchild->lchild;
			b->rchild->lchild=b->lchild;
			b->lchild=b->rchild;
			b->rchild=b->lchild->rchild;
			b->lchild->rchild=temp;
			int a=b->data;
			b->data=b->lchild->data;
			b->lchild->data=a;
		}
		void lr(bstnode *&b)
		{
			rr(b->lchild);
			ll(b);
		}
		void rl(bstnode *&b)
		{
			ll(b->rchild);
			rr(b);
		}
		void balance(bstnode *&b)
		{
			int bf=balanum(b);
			if(bf>1)
			{
				if(balanum(b->lchild)>0)
				{
					//cout<<"LL"0)
					{
						//cout<<"RL"lchild=NULL;
				t->rchild=NULL;
				return t;
			}
			else
				if(k==t->data)
					return 0;
				else
					if(kdata)
						return insert(t->lchild,k,t);
					else
						return insert(t->rchild,k,t);
		}
		
		bool remove(bstnode *b);
		int hight(bstnode *b)//测量该节点的高度 
		{
			int lchildh,rchildh;
			if(b==NULL)return(0);
			else
			{
				lchildh=hight(b->lchild);
				rchildh=hight(b->rchild);
				return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
			}
		}
		int balanum(bstnode *b)//计算该节点的平衡因子 
		{
			return hight(b->lchild)-hight(b->rchild);
		}
		void fixup(bstnode *&temp)//调整树 
		{
			while(1)
			{
				if(temp==NULL)
					return;
				if(balanum(temp)==2)
				{
					if(fabs(balanum(temp->lchild))==1)
					{
						//cout<<"找到失衡最小子树"rchild))==1)
						{
							//cout<<"找到失衡最小子树"lchild);
						fixup(temp->rchild);
						return;
					}
			}	
		}
		void creat(int a[],int n)
		{
			root=NULL;
			int i=0;
			while(idatalchild);
				else
					return 1+com(x,n->rchild);	
		}
		void inorder(bstnode *b)
		{
			if(b!=NULL)
			{
				inorder(b->lchild);
				printf("%3d",b->data);
//				cout<<" "lchild==NULL)
					sum2+=(com(b->data,root)+1);
				if(b->rchild==NULL)
					sum2+=(com(b->data,root)+1);
				inorder(b->rchild);
			}
		}
		void sussess()
		{
			sum1=0;
			sum2=0;
			inorder(root);
			coutrchild)
					n=n->rchild;
			return n;
		}
		bstnode *min(bstnode *n)
		{
			if(n!=NULL)
				while(n->lchild)
					n=n->lchild;
			return n;
		}
		void del(bstnode *n,bstnode *p, int d)
		{
			bstnode *temp=NULL;
			if(n==NULL)
			{
				cout<<"未找到该数据"lchild,n,d);
				else
					if(d>n->data)
						return del(n->rchild,n,d);
					else
						if(n->lchild&&n->rchild)
						{
							if(hight(n->lchild)>hight(n->rchild))
							{
								temp=max(n->lchild);
								n->data=temp->data;
								return del(n->lchild,n,n->data);
							}
							else
							{
								temp=min(n->rchild);
								n->data=temp->data;
								return del(n->rchild,n,n->data);
							}
						}
						else
						{
							if(n->lchild&&n->rchild==NULL)
							{
								temp=max(n->lchild);
								n->data=temp->data;
								return del(n->lchild,n,n->data);
							}
							else
								if(n->rchild&&n->lchild==NULL)
								{
									temp=min(n->rchild);
									n->data=temp->data;
									return del(n->rchild,n,n->data);
								}
								else
								{
									if(p!=NULL)
										if(n==p->lchild)
											p->lchild=NULL;
										else
											p->rchild=NULL;
									delete n;
									n=NULL;
									fixup(root);
								}
						}
							
		}
};
void randata(int datas[])
{
    srand(time(0));
	for(int i=0;i<10;i++)
		datas[i]=rand()%100;
}
int main()
{
	int datas[10]={16,3,7,11,9,26,18,14,15,1};
	randata(datas);
	
	cout<<"生成10个数据："<>chos;
		switch(chos)
		{
			case 1:
				int findnum;
				cout<<"请输入需要检索的数据：";
				cin>>findnum;
				bst.find(findnum,bst.root); 
				break;
			case 2:
				int insnum;
				cout<<"请输入需要插入的数据：";
				cin>>insnum;
				bst.insert(bst.root,insnum,NULL);
				bst.fixup(bst.root);
				cout<>delnum;
				bst.del(bst.root,NULL,delnum);
				cout<