基于二叉排序树的商品信息查询算法的设计与实现数据结构实验报告五信计162班刘禹熙·160279【实验学时】6学时【实验目的】熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。

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

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

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

（3）比较二叉排序树和平衡二叉树的平均查找长度。

【测试数据】随机生成。

【实现提示】（1）初始，二叉排序树和平衡二叉树都为空树，操作界面给出查找、插入和删除三种操作供选择。

每种操作均要提示输入关键字。

每次插入或删除一个结点后，应更新平衡二叉树或二叉排序树的显示。

（2）平衡二叉树或二叉排序树的显示可以采用凹入表形式，也可以采用图形界面画出树形。

【概要设计】1.定义二叉树存储结构类型ADT BiTree{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<iostream>#include<string>#include<time.h>#include<stdlib.h>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 (key<T->data)return searchBST(T->lchild,key,T,P);elsereturn 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 (key<P->data)P->lchild=S;elseP->rchild=S;return true;}elsereturn 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;elseQ->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(key<T->data)return deleteBST(T->lchild,key);elsereturn 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;i<ss;i++)cout<<" ";cout<<T->data<<endl;if(T->rchild)Tree_printing(T->rchild,ss);}int main(){PTree T=NULL;int key;char a;PTree p;while(1){cout<<"请选择功能"<<endl;cout<<"R:随机生成100个数创建二叉树"<<endl;cout<<"C：创建二叉树"<<endl;cout<<"I：创建二叉树结点"<<endl;cout<<"D：删除结点"<<endl;cout<<"S：查找二叉树中元素"<<endl;cout<<"P：打印二叉树"<<endl;cin>>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个数的二叉树创建完成"<<endl;cout<<"该树为:"<<endl;Tree_printing(T,1);break;}case 'C':{int n;cout<<"输入二叉树的节点个数"<<endl;cin>>n;cout<<"一共有"<<n<<"个节点"<<endl;if(n==0)break;cout<<"开始建树BST,请输入"<<n<<"个节点"<<endl;for(int i=0;i<n;i++){cout<<"请输入第"<<i+1<<"个节点的数值:__\b\b";cin>>key;insertBST(T,key);}cout<<"二叉树建立完毕如图"<<endl;Tree_printing(T,1);break;}case 'I':{cout<<"请输入要插入的值"<<endl;cin>>key;if(insertBST(T,key))cout<<"插入成功"<<endl;elsecout<<"原排序中有该元素,插入失败"<<endl;break; }case 'D':{cout<<"请输入要删除的值"<<endl;cin>>key;if(searchBST(T,key,NULL,p)){cout<<"删除"<<key<<endl;deleteBST(T,key);cout<<"删除后的树:"<<endl;Tree_printing(T,1);}elsecout<<"关键字"<<key<<"不在二叉排序树"<<endl;break;}case 'S':{cout<<"请输入要查找的值:__\b\b";cin>>key;if(searchBST(T,key,NULL,p))cout<<"关键字"<<key<<"在排序中"<<endl;elsecout<<"关键字"<<key<<"不在排序中"<<endl;break;}case 'P':{Tree_printing(T,1);break;}}}return 0;}【程序截图】【实验分析】实验采用了二叉排序树的存储方式，减小了插入过程中的时间复杂度，约为O(log(n)),在实验变成过程中，整体实验比较简单，但学会了二叉排序树的查询方法，二叉排序树的查询方法兼具顺序表和链表的优势，既方便定位查询，又方便查找和删除。

附：平衡二叉树#include <iostream.h>#include <string.h>#define NUM 10typedef 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!" << endl;return NULL;}AVLNode *b;b = a->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!" << endl; return NULL;}AVLNode *b;b = a->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!" << endl; return NULL;}AVLNode *b, *c;b = a->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!" << endl; return NULL;}AVLNode *b, *c;b = a->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;elsep = p->rchild;}if( s->key < q->key ) //将结点*s插入到合适的位置上去q->lchild = s;elseq->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;elsef->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;}。