- #include<bits_stdc++.h>
- #define max 50
- using namespace std;
- typedef struct bstnode//BST 结构
- {
- int data;
- bstnode *lc;
- bstnode *rc;
- }bt,*bst;
- typedef struct avltnode//AVL
- {
- int data;
- int bf;//balance factor
- avltnode *lc;
- avltnode *rc;
- }*avltt;
- void rightrotate(avltt *p)//right rotate
- {
- avltt l=(*p)->lc;//l 指向 p 的左子树
- (*p)->lc=l->rc;//l 的右子树挂接为 p 的左子树
- l->rc=(*p);
- *p=l;
- }
- void leftrotate(avltt *p)//left rotate
- {
- avltt r=(*p)->rc;
- (*p)->rc=r->lc;
- r->lc=(*p);
- *p=r;
- }
- void leftbalance(avltt *t)//left balance
- {
- avltt l,r;
- l=(*t)->lc;
- switch(l->bf)
- {
- case 1:
- (*t)->bf=l->bf=0;
- rightrotate(t);
- break;
- case -1:
- r = l->rc; //rd 指向 T 的左孩子的右子树的根结点
- switch(r->bf) // 修改 T 及其左孩子的平衡因子
- {
- case 1:
- (*t)->bf = -1;
- l->bf = 0;
- break;
- case 0:
- (*t)->bf = l->bf = 0;
- break;
- case -1:
- (*t)->bf = 0;
- l->bf = 1;
- break;
- }
- r->bf = 0;
- leftrotate(&(*t)->lc);
- rightrotate(t);
- break;
- }
- }
- void rightbalance(avltt *t)//right balance
- {
- avltt lc,rd;
- lc= (*t)->rc;
- switch (lc->bf)
- {
- case -1:
- (*t)->bf = lc->bf = 0;
- leftrotate(t);
- break;
- case 1:
- rd = lc->lc;
- switch(rd->bf)
- {
- case 1:
- (*t)->bf = 0;
- lc->bf = -1;
- break;
- case 0:
- (*t)->bf = lc->bf = 0;
- break;
- case -1:
- (*t)->bf = 0;
- lc->bf = 1;
- break;
- }
- rd->bf = 0;
- rightrotate(&(*t)->rc);
- leftrotate(t);
- break;
- }
- }
- int insertavl(avltt *T,int e,bool *taller)//insert AVL
- {
- if ((*T)==NULL)
- {
- (*T)=(avltt)malloc(sizeof(avltnode));
- (*T)->bf = 0;
- (*T)->data = e;
- (*T)->lc = NULL;
- (*T)->rc = NULL;
- *taller = true;
- }
- else if (e == (*T)->data)
- {
- *taller = false;
- return 0;
- }
- else if (e < (*T)->data)
- {
- if(!insertavl(&(*T)->lc,e,taller))
- return 0;
- if(*taller)
- {
- switch ((*T)->bf)
- {
- case 1:
- leftbalance(T);
- *taller = false;
- break;
- case 0:
- (*T)->bf = 1;
- *taller = true;
- break;
- case -1:
- (*T)->bf = 0;
- *taller = false;
- break;
- }
- }
- }
- else
- {
- if(!insertavl(&(*T)->rc,e,taller))
- return 0;
- if (*taller)
- {
- switch ((*T)->bf)
- {
- case 1:
- (*T)->bf = 0;
- *taller = false;
- break;
- case 0:
- (*T)->bf = -1;
- *taller = true;
- break;
- case -1:
- rightbalance(T);
- *taller = false;
- break;
- }
- }
- }
- return 1;
- }
- int searcht(bst t,int k)//search BST
- {
- if(!t)
- {
- cout<<"false"<<endl;
- //*p=f;
- return 0;
- }
- else if(k==t->data)
- {
- cout<<"find"<<endl;
- //*p=t;
- return 1;
- }
- else if(k<t->data)
- searcht(t->lc,k);
- else
- searcht(t->rc,k);
- }
- int search2(bst t,bst f,int k,bst *p)
- {
- if(!t)
- {
- *p=f;return 0;
- }
- else if (k==t->data)
- {
- *p=t;
- return 1;
- }
- else if(k<t->data)
- {
- return search2(t->lc,t,k,p);
- }
- else
- {
- return search2(t->rc,t,k,p);
- }
- }
- void insertt(bst *t,int k)//insert BST
- {
- bst p,s;
- if(!search2(*t,NULL,k,&p))//cant find
- {
- s=(bst)malloc(sizeof(bstnode));
- s->data=k;
- s->lc=s->rc=NULL;
- if(!p)
- *t=s;
- else if(k<p->data)
- p->lc=s;
- else
- p->rc=s;
- }
- else
- cout<<k<<"已存在"<<endl;
- }
- void deletee(bst *p)// 删除重接
- {
- bst q,s;
- if((*p)->rc==NULL)
- {
- q=(*p);(*p)=(*p)->lc;
- free(q);
- }
- else if((*p)->lc==NULL)
- {
- q=*p;*p=(*p)->rc;
- free(q);
- }
- else
- {
- q=*p;s=(*p)->lc;
- while(s->rc)
- {
- q=s;
- s=s->rc;
- }
- (*p)->data=s->data;
- if(q!=*p)
- q->rc=s->lc;
- else
- q->lc=s->lc;
- free(s);
- }
- }
- void deletet(bst *t,int k)//delete BST
- {
- if(k==(*t)->data)
- deletee(t);
- else if(k<(*t)->data)
- deletet(&(*t)->lc,k);
- else
- deletet(&(*t)->rc,k);
- }
- void displaybst(bst t)//pre-order BST
- {
- if(t)
- {
- cout<<t->data<<" ";
- displaybst(t->lc);
- displaybst(t->rc);
- }
- }
- void displayavlt(avltt t)//pre-order AVL
- {
- if(t)
- {
- cout<<t->data<<" ";
- displayavlt(t->lc);
- displayavlt(t->rc);
- }
- }
- int main ()
- {
- int i,c=0;
- int a[max];
- bst t=NULL,p;
- avltt avlt=NULL;
- bool taller;
- cout<<"产生随机数为:"<<endl;
- for(i=0;i<max;i++)
- {
- a[i]=(rand()%100);
- cout<<a[i]<<" ";
- if((i+1)%10==0)cout<<endl;
- }
- for(i=0;i<max;i++)//build BST
- insertt(&t,a[i]);
- cout<<"binary sort tree:"<<endl;
- displaybst(t);
- for(i=0;i<max;i++)//build AVL tree
- insertavl(&avlt,a[i],&taller);
- cout<<endl<<"AVL tree:"<<endl;
- displayavlt(avlt);
- int k;
- for(c;c!=4;)
- {
- cout<<endl<<"请选择 BST 操作 (1:search,2:insert,3:delete,4:qiut)"<<endl;
- cin>>c;
- if(c==4)break;
- switch(c)
- {
- case 1:
- cout<<"请输入查找值:"<<endl;cin>>k;searcht(t,k);break;
- case 2:
- cout<<"请输入插入值:"<<endl;cin>>k;insertt(&t,k);
- cout<<"插入后为:"<<endl;displaybst(t);break;
- case 3:
- cout<<"请输入删除值:"<<endl;cin>>k;deletet(&t,k);
- cout<<"删除后为:"<<endl;displaybst(t);break;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2495957.html