实验五查找算法实现1、实验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。

2、问题描述查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。

3、基本要求（1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。

（2）根据给定的数据建立平衡二叉树。

4、测试数据随即生成5、源程序#include<>#include<>#include<>#define EQ(a,b) ((a)==(b))#define LT(a,b) ((a)<(b))#define LQ(a,b) ((a)>(b))typedef int Keytype;typedef struct{ Keytype key; //关键字域}ElemType;typedef struct BSTnode{ ElemType data;int bf;struct BSTnode *lchild,*rchild;}BSTnode,*BSTree;void InitBSTree(BSTree &T){T=NULL;}void R_Rotate(BSTree &p){BSTnode *lc;lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;}void L_Rotate(BSTree &p){BSTnode *rc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}void Leftbalance(BSTree &T) {BSTnode *lc,*rd;lc=T->lchild;switch(lc->bf){case +1:T->bf=lc->bf=0; R_Rotate(T);break;case -1:rd=lc->rchild; switch(rd->bf){ case 1:T->bf=-1;lc->bf=0;break;case 0:T->bf=lc->bf=0;break;case -1:T->bf=0;lc->bf=1;break;}rd->bf=0;L_Rotate(T->lchild);R_Rotate(T);}}void Rbalance(BSTree &T) {BSTnode *lc,*ld;lc=T->rchild;switch(lc->bf){ case 1:ld=lc->lchild;switch(ld->bf){ case 1:T->bf=0;lc->bf=-1;break;case 0:T->bf=lc->bf=0;break;case -1:T->bf=1;lc->bf=0;break;}ld->bf=0;R_Rotate(T->rchild);L_Rotate(T);case -1:T->bf=lc->bf=0;L_Rotate(T);break;}}int InsertAVL(BSTree &T,ElemType e,bool &taller) { if(!T){ T=(BSTree)malloc(sizeof(BSTnode));T->data=e;T->lchild=T->rchild=NULL;T->bf=0;taller=true;}else{ if(EQ,T->){ taller=false;cout<<"结点 "<<<<" 不存在。

"<<endl;return 0;}if(LT,T->){ if(!InsertAVL(T->lchild,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->rchild,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:Rbalance(T);taller=false;break;}}}return 1;}bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree &p) { if(!T){ p=f;cout<<"结点不存在。

"<<endl;return false;}else if( EQ,T-> ){ p=T;cout<<"查找成功，存在结点";cout<<p-><<endl;return true;}else if(LT,T->)return SearchBST(T->lchild,key,T,p);return SearchBST(T->rchild,key,T,p);}void Leftbalance_div(BSTree &p,int &shorter){ BSTree p1,p2;if(p->bf==+1) //p结点的左子树高，删除结点后p的bf减1,树变矮{ p->bf=0;shorter=1;}else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减1,树高不变{ p->bf=-1;shorter=0;}else{ p1=p->rchild;//p1指向p的右子树if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变{ L_Rotate(p);p1->bf=1;p->bf=-1;shorter=0;}else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮{ L_Rotate(p);p1->bf=p->bf=0;shorter=1;}else{ p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0){ p->bf=0;p1->bf=0;}else if(p2->bf==-1){ p->bf=+1;p1->bf=0;}else{ p->bf=0;p1->bf=-1;p2->bf=0;p=p2;shorter=1;}}}void Rbalance_div(BSTree &p,int &shorter) { BSTree p1,p2;if(p->bf==-1){ p->bf=0;shorter=1;}else if(p->bf==0){ p->bf=+1;shorter=0;}else{ p1=p->lchild;if(p1->bf==0){ R_Rotate(p);p1->bf=-1;p->bf=+1;shorter=0;}else if(p1->bf==+1){ R_Rotate(p);p1->bf=p->bf=0;shorter=1;}else{ p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lchild=p2->rchild;p2->rchild=p;if(p2->bf==0){ p->bf=0;p1->bf=0;}else if(p2->bf==1){ p->bf=-1;p1->bf=0;}else{ p->bf=0;p1->bf=1;}p2->bf=0;p=p2;shorter=1;}}}void Delete(BSTree q,BSTree &r,int &shorter){ if(r->rchild==NULL){ q->data=r->data;q=r;r=r->lchild;free(q);shorter=1;}else{ Delete(q,r->rchild,shorter);if(shorter==1)Rbalance_div(r,shorter);}}ElemType DeleteAVL(BSTree &p,ElemType key,int &shorter) { ElemType k,a,b;=1;=0;BSTree q;if(p==NULL){ cout<<"结点不存在。

"<<endl;return b;}else if(LT,p-> )//在p的左子树中进行删除{ k=DeleteAVL(p->lchild,key,shorter);if(shorter==1)Leftbalance_div(p,shorter);return k;}else if(LQ,p-> )//在p的右子树中进行删除{ k=DeleteAVL(p->rchild,key,shorter);Rbalance_div(p,shorter);return k;}else{q=p;if(p->rchild==NULL) //右子树空则只需重接它的左子树{ p=p->lchild;free(q);shorter=1;}else if(p->lchild==NULL)//左子树空则只需重接它的右子树 { p=p->rchild;free(q);shorter=1;}else{ Delete(q,q->lchild,shorter);if(shorter==1)Leftbalance_div(p,shorter);p=q;}return a;}}void Print_BSTTree(BSTree T,int i){ if(T){ if(T->rchild)Print_BSTTree(T->rchild,i+1);for(int j=1;j<=i;j++)cout<<" ";cout<<T-><<endl;if(T->lchild)Print_BSTTree(T->lchild,i+1);}}int main(){ BSTree T;ElemType e;InitBSTree(T);bool tall=false;bool choice=true;char y;{ cout<<"输入要插入结点(数字):";cin>>;InsertAVL(T,e,tall);Print_BSTTree(T,0);cout<<"是否继续，是选y，否选n:"; cin>>y;if(y=='Y'||y=='y')choice=true;else choice=false;}BSTree f,p;choice=true;while(choice){ cout<<"输入要查找的结点:";cin>>;SearchBST( T,e,f,p);cout<<"是否继续，是选y，否选n："; cin>>y;if(y=='Y'||y=='y')choice=true;else choice=false;}int shorter;choice=true;while(choice){ cout<<"输入要删除的结点:";cin>>;DeleteAVL(T,e,shorter);Print_BSTTree(T,0);cout<<"是否继续，是选y，否选n："; cin>>y;if(y=='Y'||y=='y')choice=true;else choice=false;}return 0;}。