基于二叉排序树的商品信息查询算法的设计与实现_final

基于二叉排序树的商品信息查询算法的与实现 数据结构实验五 信计162班 刘禹熙· 160279 【实验学时】6学时 【实验目的】 熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。 【问描述】 查找是数据处理的重要操作， 试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树， 并比较两者的平均查找长度。 【基本要求】 （1） 以链表作为存储结构，实现二叉排序树的建立、查找和删除。 （2） 根据给定的数据建立平衡二叉树。 （3） 比较二叉排序树和平衡二叉树的平均查找长度。 【测试数据】 随机生成。 【实现提示】 （1） 初始，二叉排序树和平衡二叉树都为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更新平衡二叉树或二叉排序树的显示。 （2） 平衡二叉树或二叉排序树的显示可以采用凹入表形式，也可以采用图形界面画出树形。 【概要设计】 1. 定义二叉树存储结构类型 ADTBiTree{ int data//每个树结点存放的数据值 BiTree *lchild,*rchild;//分支结点 函数类型：    Bool searchBST（T,key,f,p） 操作结果：查找树T中是否有值为key的结点并让指针p指向该树根结点。 Bool insertBST(T,key) 操作结果：在树中插入尚未存在的结点权值为key的结点，若已有该节点则不插入。 Bool deleteBST(T,key) 操作结果：在树T中删除结点权值为key 的结点，若结点不存在则，返回false。 Void Tree_printing(T,ss) 操作结果，在距屏幕左侧ss的地方凹入法打印已经存储的二叉树。 } 2. main函数说明 功能包括：R:用伪随机发生成100个结点的商品二叉树，并用凹入法打印新生成的二叉树 C:创建二叉树，可以批量添加结点； I:创建一个二叉树结点，若结点存在则不插入，若不存在则插入，并打印插入后的二叉树 D:删除二叉树值为key的结点，若不存在则返回结点不存在，并打印删除后的二叉树 S:查找二叉树中的元素，结果返回存在或不存在 P:凹入法打印二叉树。 【程序代码】 #include #include #include #include using namespace std; typedef struct BiTree { int data; struct BiTree *lchild,*rchild; }BiTree,*PTree; bool searchBST(PTree T,int key,PTree f,PTree &P) { if(!T) { P=f; return false; } else if (key==T->data) { P=T; return true; } else if (keydata) return searchBST(T->lchild,key,T,P); else return searchBST(T->rchild,key,T,P); } bool insertBST(PTree &T,int key) { PTree P,S; if (!searchBST(T,key,NULL,P)) { S=(PTree)malloc(sizeof(BiTree)); S->data=key; S->lchild=S->rchild=NULL; if(!P) T=S; else if (keydata) P->lchild=S; else P->rchild=S; return true; } else return false; } bool Delete(PTree &P) { PTree Q,S; if(P->rchild==NULL) { Q=P; P=P->lchild; free(Q);//释放内存 } else if (P->lchild==NULL) { Q=P; P=P->rchild; free(Q); } else { Q=P; S=P->lchild; while(S->rchild) { Q=S; S=S->rchild; } P->data=S->data; if(Q!=P) Q->rchild=S->lchild; else Q->lchild=S->lchild; free(S); } return true; } bool deleteBST(PTree &T,int key) { if(!T) return false; else { if(key==T->data) return Delete(T); else if(keydata) return deleteBST(T->lchild,key); else return deleteBST(T->rchild,key); } } void Tree_printing(PTree &T,int ss) { ss+=2; if(T->lchild) Tree_printing(T->lchild,ss); for(int i=0;idata<rchild) Tree_printing(T->rchild,ss); } int main() { PTree T=NULL; int key; char a; PTree p; while(1) { cout<<"请选择功能"<>a; switch(a) { case 'R': { for(int i=1;i<=100;i++) { while(!searchBST(T,key=rand()%200,NULL,p)) insertBST(T,key); } cout<<"随机生成100个数的二叉树创建完成"<>n; cout<<"一共有"<>key; insertBST(T,key); } cout<<"二叉树建立完毕如图"<>key; if(insertBST(T,key)) cout<<"插入成功"<>key; if(searchBST(T,key,NULL,p)) { cout<<"删除"<>key; if(searchBST(T,key,NULL,p)) cout<<"关键字"< #include #define NUM 10  typedef int KeyType;  class AVLTree;  class AVLNode  {  public:  KeyType key;  //任意一结点的左子树深度减去右子树的 //深度称为该节点的平衡因子.  int bf;      //记录平衡因子 AVLNode *lchild;  AVLNode *rchild;  AVLNode() {  lchild = NULL;  rchild = NULL;  bf = 0;  }  };  //平衡二叉排序树 class AVLTree  {  public:  AVLNode *root;  AVLTree() {  root = NULL;  }  AVLNode* LL_Rotate( AVLNode *a );    //LL(顺时针)型调整 AVLNode* RR_Rotate( AVLNode *a );    //RR(逆时针)型调整 AVLNode* LR_Rotate( AVLNode *a );    //LR(先逆后顺)型调整 AVLNode* RL_Rotate( AVLNode *a );    //RL(先顺后逆)型调整 void AVLInsert( AVLNode *&pavlt, AVLNode *s );  //插入一个新结点 };  /** *  LL(顺时针)型调整 *  */  AVLNode* AVLTree::LL_Rotate( AVLNode *a )  {    if( a == NULL )  {  cout<<  "the pointer is null!" <lchild;      //b指向a的左子树根结点 a->lchild = b->rchild;  //b的右子树挂在a的左子树上 b->rchild = a;  a->bf = b->bf = 0;  return b;  }  /** *  RR(逆时针)型调整 *  */  AVLNode* AVLTree::RR_Rotate( AVLNode *a )  {    if( a == NULL )  {  cout<<  "the pointer is null!" <rchild;  a->rchild = b->lchild;  b->lchild = a;  a->bf = b->bf = 0;  return b;  }  /** *  LR(先逆后顺)型调整 *  */  AVLNode* AVLTree::LR_Rotate( AVLNode *a )  {    if( a == NULL )  {  cout<<  "the pointer is null!" <lchild;  c = b->rchild;  a->lchild = c->rchild;  b->rchild = c->lchild;  c->lchild = b;  c->rchild = a;  //调整平衡因子 if( c->bf == 1 )  {  a->bf = -1;  b->bf = 0;  }  else if( c->bf == -1 )  {  a->bf = 0;  b->bf = 1;  }  else {  b->bf = a->bf = 0;  }  c->bf = 0;  return c;  }  /** *  RL(先顺后逆)型调整 *  */  AVLNode* AVLTree::RL_Rotate( AVLNode *a )  {    if( a == NULL )  {  cout<<  "the pointer is null!" <rchild;  c = b->lchild;  a->rchild = c->lchild;  b->lchild = c->rchild;  c->lchild = a;  c->rchild = b;  //调整平衡因子 if( c->bf == 1 )  {  a->bf = 0;  b->bf = -1;  }  else if( c->bf == -1 )  {  a->bf = 1;  b->bf = 0;  }  else {  a->bf = b->bf = 0;  }  c->bf = 0;  return c;  }  /** *  将结点s插入pavlt为根结点的平衡二叉排序树中 *  */  void AVLTree::AVLInsert( AVLNode *&pavlt, AVLNode *s )  {  AVLNode *f, *a, *b, *p, *q;  if( pavlt == NULL )  {  pavlt = s;  return;  }  a = pavlt;  f = NULL;  p = pavlt;  q = NULL;  //寻找插入点位置及最小不平衡树的子树 while( p != NULL )  {  if( p->key == s->key )  //AVL中已经存在关键字 return;  if( p->bf != 0 )        //寻找最小不平衡子树 {  a = p;  f = q;  }  q = p;  if( s->key < p->key )      p = p->lchild;  else p = p->rchild;  }  if( s->key < q->key )        //将结点*s插入到合适的位置上去 q->lchild = s;  else q->rchild = s;  p = a;  while( p != s )            //插入结点后修改相应的平衡因子 {  if( s->key < p->key )  {  p->bf++;  p = p->lchild;  }  else {  p->bf--;  p = p->rchild;  }  }  if( a->bf > -2 && a->bf < 2 )  //插入结点后没有破坏平衡树 return;  if( a->bf == 2 )  {  b = a->lchild;  if( b->bf == 1 )          //结点插在*a的左孩子的左子树中 p = LL_Rotate( a );    //LL型调整 else                      //结点插在*a的左孩子的右子树中 p = LR_Rotate( a );    //LR型调整 }  else {  b = a->rchild;  if( b->bf == 1 )          //结点插在*a的右孩子的左子树中 p = RL_Rotate( a );  //RL型调整 else                      //结点插在*a的右孩子的右子树中 p = RR_Rotate( a );  //RR型调整 }  if( f == NULL )              //原*a是AVL树的根 pavlt = p;  else if( f->lchild == a )    //将新子树链到原结点*a的双亲结点上 f->lchild = p;  else f->rchild = p;  }  int main( void )  {  int a[NUM] = { 34, 18, 13, 73, 16, 52, 58, 67, 82, 76 };  int i = 0;  AVLTree tree;  AVLNode pNode[NUM], *p = NULL;  for( i = 0; i < NUM; i++ )  {  pNode[i].key = a[i];  tree.AVLInsert( p, &pNode[i] );  }  return 0;  }