数据结构实验——查找算法的实现

1、实验五查找算法实现1、实验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。2、问题描述查找表是数据处理的重要操作， 试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树， 并比较两者的平均查找长度。3、基本要求（1） 以链表作为存储结构，实现二叉排序树的建立、查找和删除。（2） 根据给定的数据建立平衡二叉树。4、测试数据随即生成5、源程序#include<iostream.h>#include<stdlib.h>#include<string.h>#define EQ(a,b) (a)=

2、(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->l

3、child; 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;

4、 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

5、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,bo

6、ol &taller) if(!T) T=(BSTree)malloc(sizeof(BSTnode); T->data=e; T->lchild=T->rchild=NULL; T->bf=0; taller=true; else if(EQ(e.key,T->data.key) taller=false; cout<<"结点 "<<e.key<<" 不存在。"<<endl; return 0; if(LT(e.key,T->data.key) if(!Inse

7、rtAVL(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; talle

8、r=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(key.key,T->data.key) ) p=T; cout<<"

9、;查找成功，存在结点" cout<<p->data.key<<endl; return true; else if(LT(key.key,T->data.key) return SearchBST(T->lchild,key,T,p); else 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-

10、>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=

11、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(BST

12、ree &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->rc

13、hild; 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) i

14、f(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; a.key=1; b.key=0; BSTree q; if(p=NULL) cout<<"结点

15、不存在。"<<endl; return b; else if(LT(key.key,p->data.key) )/在p的左子树中进行删除 k=DeleteAVL(p->lchild,key,shorter); if(shorter=1) Leftbalance_div(p,shorter); return k; else if(LQ(key.key,p->data.key) )/在p的右子树中进行删除 k=DeleteAVL(p->rchild,key,shorter); if(shorter=1) Rbalance_div(p,shorter);

16、 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

17、) if(T) if(T->rchild) Print_BSTTree(T->rchild,i+1); for(int j=1;j<=i;j+) cout<<" " cout<<T->data.key<<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; while(choic

18、e) cout<<"输入要插入结点(数字):" cin>>e.key; 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>>e.key; SearchBST( T,e,f,p); cout<<"是否继续，是选y，否选n：" cin>>y; if(y='Y'|y='y') cho