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

二叉排序树查找算法
二叉排序树，也称作二叉搜索树，是一种重要的数据结构，它的
主要作用是支持快速的查找操作。

在实际的程序设计中，二叉排序树
非常常见，因为它可以在平均情况下，以O(log n)的时间复杂度进行
查找，具有很高的效率。

二叉排序树的特点是，对于每一个节点，它的左子树上的所有节
点都比它小，右子树上的所有节点都比它大。

因此，当我们要查找某
个节点时，可以根据这个特点，快速定位到它所在的位置，因为每次
比较都可以把树的大小缩小一半。

对于二叉排序树的查找操作，我们需要先从根节点开始，依次比
较节点的值和要查找的值的大小关系。

如果要查找的值比节点的值小，那么就在左子树上继续查找；如果要查找的值比节点的值大，那么就
在右子树上查找；如果两者相等，那么就找到了要查找的节点。

如果
最终没有找到要查找的节点，那么就说明树中不存在这个节点。

二叉排序树的查找算法非常简单，但是在实际应用中，我们也需
要注意一些细节问题。

首先，要保证二叉排序树中不存在重复的节点，因为有重复的节点会导致查找结果不确定；其次，要保证二叉排序树
的平衡性，可以使用平衡算法来保证树的高度不会过高，从而提高查
找效率；最后，对于二叉排序树的插入和删除操作，也要注意保持树
的排序性。

总之，二叉排序树作为一种常见的数据结构，它的查找算法非常简单高效，但在实际应用中我们也需要注意避免一些常见问题，才能发挥其最大的作用。

因此，在程序设计中，要根据具体的情况，灵活应用二叉排序树来支持各种操作。

一、上机实验的问题和要求：复习二叉排序树的生成及查找算法，编写完整的程序。

实现二叉排序树上的查找算法。

具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。

二、源程序及注释：#include <stdio.h>#include <stdlib.h>typedef int InfoType;typedef int KeyType; //假定关键字类型为整数typedef struct node //结点类型{KeyType key; //关键字项InfoType otherinfo; //其它数据域，InfoType视应用情况而定下面不处理它struct node *lchild,*rchild;//左右孩子指针}BSTNode;typedef BSTNode *BSTree; //BSTree是二叉排序树的类型BSTNode *SearchBST(BSTree T,KeyType key){ //在二叉排序树T上查找关键字为key 的结点，成功时返回该结点位置，否则返回NULLif(T==NULL||key==T->key) //递归的终结条件return T; //若T为空，查找失败；否则成功，返回找到的结点位置if(key<T->key)return SearchBST(T->lchild,key);elsereturn SearchBST(T->rchild,key); //继续在右子树中查找}void InsertBST(BSTree *T,int key){ //插入一个值为key的节点到二叉排序树中BSTNode *p,*q;if((*T)==NULL){ //树为空树(*T)=(BSTree)malloc(sizeof(BSTNode));(*T)->key=key;(*T)->lchild=(*T)->rchild=NULL;}else{p=(*T);while(p){q=p;if(p->key>key)p=q->lchild;else if(p->key<key)p=q->rchild;else{printf("\n该二叉排序树中含有关键字为%d的节点!\n",key);return;}}p=(BSTree)malloc(sizeof(BSTNode));p->key=key;p->lchild=p->rchild=NULL;if(q->key>key)q->lchild=p;elseq->rchild=p;}}BSTree CreateBST(void){ //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回BSTree T=NULL; //初始时T为空树KeyType key;scanf("%d",&key); //读入一个关键字while(key){ //假设key=0是输入结束标志InsertBST(&T,key); //将key插入二叉排序树Tscanf("%d",&key); //读入下一关键字}return T; //返回建立的二叉排序树的根指针}void ListBinTree(BSTree T) //用广义表表示二叉树{if (T!=NULL){printf("%d",T->key);if (T->lchild!=NULL||T->rchild!=NULL){printf("(");ListBinTree(T->lchild);if (T->rchild!=NULL)printf(",");ListBinTree(T->rchild);printf(")");}}}void main(){BSTNode *SearchBST(BSTree T,KeyType key);void InsertBST(BSTree *Tptr,KeyType key);BSTree CreateBST();void ListBinTree(BSTree T); //用广义表表示二叉树BSTree T;BSTNode *p;int key;printf("请输入关键字（输入0为结束标志）：\n");T=CreateBST();ListBinTree(T);printf("\n");printf("请输入欲查找关键字：");scanf("%d",&key);p=SearchBST(T,key);if(p==NULL)printf("没有找到%d！\n",key);elseprintf("找到%d！\n",key);ListBinTree(p);printf("\n");}三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：1、输入数据时，总是不能得到结果，原因：在建立二叉树函数定义中，是对指针的值进行了修改；解决方法：用指向指针的指针。

1. 建立一棵二叉排序树，存储学生信息，并实现查询功能#include<iostream>#include<string>using namespace std;static int a,b;typedef struct node{int grade;string name;int no;struct node *lchild,*rchild;}BSTNode; //代表二叉排序树的结点定义typedef BSTNode *BSTree; //定义二叉排序树static BSTNode *t; //定义一个临时结点BSTNode * SearchBST(BSTree T, int no){if( )SearchBST(T->lchild, );//补充语句，根据学号向左子树搜索if(T-> == ) //补充语句，学号相等，查询成功，获得当前的T结点t=T;if(T->rchild!=NULL&&T->grade!=a&&T->rchild==NULL&&T->rchild->no==no) t=T->rchild;if(T->rchild!=NULL&&T->rchild->lchild!=NULL)SearchBST(T->rchild, ); //补充语句，根据学号向右子树搜索if(T->rchild!=NULL&&T->grade==b){a=T->rchild->grade;SearchBST(T->rchild,no);}return t;}void InserBST(BSTree *T,int grade,string name,int no){ //此函数用来插入二叉排序树中的结点来建立二叉排序树BSTNode *p,*q;if( (*T) ==NULL){(*T)= ; //补充语句，创建一个新结点(*T)->grade= ;(*T)->name= ;(*T)-> = ; //以上三条语句补充完整，创建学号，姓名，成绩构成的学生信息(*T)->lchild=(*T)->rchild= ; //补充语句，将被插入的新结点设置成叶结点标志}else{p=(*T);while(p){q=p;if( ) //补充判断条件，若grade成绩值小于当前结点，向左子树前进搜索p=q->lchild;else if( )//补充判断条件，若grade成绩值大于当前结点，向右子树前进搜索;}p=new BSTNode;p->grade=grade;p->name=name;p->no=no;p->lchild=p->rchild=NULL;if(q->grade>grade)q->lchild=p;elseq->rchild=p;}}BSTree CreateBST(void){BSTree T=NULL;int grade,no;string name;cin>>no;cin>>name;cin>>grade;b=a=grade;while(grade){; //补充语句，调用InserBST函数向二叉排序树插入结点cin>>no;cin>> ; //补充语句cin>> ; //补充语句}return T;}void ListBinTree(BSTree T){//此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序） if(T->lchild!=NULL); //补充语句，递归遍历左子树cout<<T->no<<" "<<T->name<<" "<<T->grade<<endl; //输出根（双亲）结点//补充一组语句，向右子树递归遍历}void main(){BSTree T;BSTNode *p;int no;cout<<"请输入学生信息（输入0为结束标志）:\n";cout<<"学号姓名成绩\n";T= ; //补充语句调用建立二叉排序函数cout<<"按成绩构建二叉排序树，存储学生数据成功！\n\n";cout<<" 52 \n";cout<<" / \\ \n";cout<<" 26 66 \n";cout<<" /\\ \\ \n";cout<<" 12 45 99 \n";cout<<" /\\ / \n";cout<<" 33 50 89 \n";cout<<" / \n";cout<<" 87 \n";cout<<"\n按成绩由低到高排序:";cout<<"\n 学号姓名成绩\n";; //补充语句调用排序函数printf("\n");cout<<"请输入所要查询学生的学号:";cin>>no;p= (T,no); //补充语句调用查询函数if(p==NULL)cout<<"没有找到”<< no<<”! \n";else{cout<<"\n 学号姓名成绩\n";cout<<p->no<<" "<<p->name<<" "<<p->grade<<endl;}}#include<iostream>#include<string>using namespace std;static int a,b;typedef struct node{int grade;string name;int no;struct node *lchild,*rchild;}BSTNode; //代表二叉排序树的结点定义typedef BSTNode *BSTree; //定义二叉排序树static BSTNode *t; //定义一个临时结点BSTNode * SearchBST(BSTree T, int no){if(T->lchild!=NULL)SearchBST(T->lchild,no); //补充语句，根据学号向左子树搜索if(T->no==no) //补充语句，学号相等，查询成功，获得当前的T结点t=T;if(T->rchild!=NULL&&T->grade!=a&&T->rchild==NULL&&T->rchild->no==no)t=T->rchild;if(T->rchild!=NULL&&T->rchild->lchild!=NULL)SearchBST(T->rchild,no); //补充语句，根据学号向右子树搜索if(T->rchild!=NULL&&T->grade==b){a=T->rchild->grade;SearchBST(T->rchild,no);}return t;}void InserBST(BSTree *T,int grade,string name,int no){ //此函数用来插入二叉排序树中的结点来建立二叉排序树BSTNode *p,*q;if( (*T) ==NULL){(*T)=new BSTNode; //补充语句，创建一个新结点(*T)->grade=grade;(*T)->name=name;(*T)->no=no; //以上三条语句补充完整，创建学号，姓名，成绩构成的学生信息(*T)->lchild=(*T)->rchild=NULL; //补充语句，将被插入的新结点设置成叶结点标志}else{p=(*T);while(p){q=p;if(p->grade>grade) //补充判断条件，若grade成绩值小于当前结点，向左子树前进搜索p=q->lchild;else if(p->grade<grade)p=q->rchild;//补充判断条件，若grade成绩值大于当前结点，向右子树前进搜索}p=new BSTNode;p->grade=grade;p->name=name;p->no=no;p->lchild=p->rchild=NULL;if(q->grade>grade)q->lchild=p;elseq->rchild=p;}}BSTree CreateBST(void){BSTree T=NULL;int grade,no;string name;cin>>no;cin>>name;cin>>grade;b=a=grade;while(grade){InserBST(&T,grade,name,no);//补充语句，调用InserBST函数向二叉排序树插入结点cin>>no;cin>>name; //补充语句cin>>grade; //补充语句}return T;}void ListBinTree(BSTree T){//此函数用于按顺序输出二叉排序树（以中序遍历方式输出即可得到有序）if(T->lchild!=NULL)ListBinTree(T->lchild); //补充语句，递归遍历左子树cout<<T->no<<" "<<T->name<<" "<<T->grade<<endl;//输出根（双亲）结点if(T->rchild!=NULL&&T->grade!=a&&T->rchild->lchild==NULL)cout<<T->rchild->no<<" "<<T->rchild->name<<" "<<T->rchild->grade<<endl; if(T->rchild!=NULL&&T->rchild->lchild==NULL)ListBinTree(T->rchild);if(T->rchild!=NULL&&T->grade==b){a=T->rchild->grade;ListBinTree(T->rchild);//补充一组语句，向右子树递归遍历}}void main(){BSTree T;BSTNode *p;int no;cout<<"请输入学生信息（输入0为结束标志）:\n";cout<<"学号姓名成绩\n";T=CreateBST(); //补充语句调用建立二叉排序函数cout<<"按成绩构建二叉排序树，存储学生数据成功！\n\n";cout<<" 52 \n";cout<<" / \\ \n";cout<<" 26 66 \n";cout<<" /\\ \\ \n";cout<<" 12 45 99 \n";cout<<" /\\ / \n";cout<<" 33 50 89 \n";cout<<" / \n";cout<<" 87 \n";cout<<"\n按成绩由低到高排序:";cout<<"\n 学号姓名成绩\n";ListBinTree; //补充语句调用排序函数printf("\n");cout<<"请输入所要查询学生的学号:";cin>>no;p=SearchBST(T,no); //补充语句调用查询函数if(p==NULL)cout<<"没有找到"<< no<<"! \n";else{cout<<"\n 学号姓名成绩\n";cout<<p->no<<" "<<p->name<<" "<<p->grade<<endl;}}。

基于递归二叉查找树查找算法一、引言递归二叉查找树是一种常见的查找算法，其在查找和排序问题中拥有广泛的应用。

基于递归二叉查找树的算法是一种高效、可靠的解决方案，可以极大的优化查找过程的复杂度。

本文将介绍基于递归二叉查找树的查找算法，重点讲解它的实现原理及其适用范围。

二、递归二叉查找树递归二叉查找树是一种二叉树，其中每个节点包含一个关键字，并且每个节点的左子树的所有关键字都小于该节点的关键字，右子树的关键字都大于该节点的关键字。

递归二叉查找树具有很多特点，例如支持二分查找、插入、删除等操作，并且对于大多数查找问题，它的平均空间复杂度为O(logn)。

三、基于递归二叉查找树查找算法基于递归二叉查找树的查找算法主要通过递归的方式实现，可以分为以下几个步骤：1. 判断待查找的关键字是否等于当前节点的关键字。

2. 如果等于，返回当前节点。

3. 如果小于当前节点的关键字，递归查找左子树。

4. 如果大于当前节点的关键字，递归查找右子树。

如下是基于递归二叉查找树的查找算法实现代码：```struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL) return NULL;if (root->val == val) return root;if (root->val > val) return searchBST(root->left, val);if (root->val < val) return searchBST(root->right, val);}```四、适用范围基于递归二叉查找树的查找算法适用于各种查找问题，包括但不限于以下几种情况：1. 静态查找递归二叉查找树适用于静态查找，即查找过程中不需要修改关键字的情况。

二叉排序树在网上商品信息检索中的应用[摘要]随着互联网的普及应用，网上购物得到了迅猛发展，而网上商品信息的检索量却也随之与日俱增，如何提高商品信息检索效率已成为急需解决的问题，本文提出一种基于二叉排序树的商品信息动态检索方法，不仅提高了商品信息的检索效率，而且还可以根据用户的检索信息量判断出用户的购买需求，并反馈给管理者，为企业的发展起到了导向作用。

[关键词]二叉排序树平衡二叉树平衡因子一、问题的提出目前大多数的网上购物系统采用的是B/S(浏览器/服务器)结构的管理软件，其数据库表的查询操作大部分使用的是顺序查找法，即从第一行记录顺序的查找到满足查询条件的记录，这种查找方法算法简单，对表结构无任何要求但是当数据量的很大时，查找的时间复杂度很大，查找效率会很低。

为此本文提出了基于二叉排序树的商品信息动态检索方法。

二、问题的分析与实现1.构造二叉排序树二叉排序树，又称BST树，它是一种特殊的二叉树，其具有的特点：(1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；(2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；(3)左、右子树本身又各是一棵二叉排序树。

根据数据库商品表中商品名称的首字母信息(字符ASCII码的大小)，构造二叉排序树。

例如我们在商品表中搜索到五条记录分别是：海尔冰箱、诺基亚手机、富士宝电磁炉、燕京啤酒、喜之郎果冻。

提取出它们名称首字母的前两项，构造一个线性表(HE,NJ,FS,YJ,XZ),以表中第一个元素HE为根结点，以后的各个数据，逐个插入结点，在插入过程的每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求，构造出二叉排序树如图1所示，并按照二叉排序树的原理建立对应的二叉树商品关系表，如表1所示。

其中COMMODITYNAME表示商品名称；COMMODITYPY表示商品名称首字母；Father表示该结点的父结点信息，当字段值为NULL时表示该结点为根结点；SonInfo表示该结点与父结点关系信息，字段中用0或1分别表示该结点为其父结点的左子树和右子树，这就和二叉树的内存表示对应起来。

数据结构课程设计一、引言数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。

该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。

通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力。

数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。

学习数据结构的最终目的是为了获得求解问题的能力。

对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。

实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。

相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，我们都会有不同程度上的提高。

二、课程设计目的本课程是数据结构课程的实践环节。

主要目的在于加强学生在课程中学习的相关算法和这些方法的具体应用，使学生进一步掌握在C++或其他语言中应用这些算法的能力。

通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解。

三、内容设计要求二叉排序树的实现：用顺序和二叉链表作存储结构1）以回车（‘\n’）为输入结束标志，输入数列L,生成一棵二叉排序树T;2)对二叉排序树T作中序遍历，输出结果；3）输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历（执行操作2）；否则输出信息“无x”。

（一）问题分析和任务定义对问题的描述应避开具体的算法和涉及的数据结构，它是对要完成的任务作出明确的回答，强调的是做什么，而不是怎么做。

（二）详细的设计和编码算法的具体描述和代码的书写。

（三）上机调试源程序的输入和代码的调试。

基于二叉排序树的商品信息查询算法的设计与实现问题描述查找是数据处理的重要操作。

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

完成信息的查询、插入、删除、查询频度的统计等功能。

4、基本要求（1）以链表作为存储结构，设计并实现基于二叉排序树的商品信息查询算法。

（2）根据二叉排序树的动态变化，进行二叉树的平衡化处理。

（3）实现信息的查询、插入、删除、查询频度的统计等功能。

5、测试数据随机生成。

6、实现提示（1）初始化：以商品名称为关键字，建立二叉排序树。

（2）用户输入查询商品名称，在二叉排序树上查找，若找到，则显示商品的相关信息，并在相应的表上的相关字段上增加该商品查找次数。

若未找到，则显示未找到信息给用户，并在相应的表上的相关字段上增加该商品查找次数。

（3）根据商品的查找次数，形成商场的经营决策信息，反馈给决策者。

（4）进行二叉树的平衡化处理，提高查找效率。

#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define LH +1 // 左高#define EH 0 // 等高#define RH -1 // 右高#define LNAME 5 //商品名称长度#define BUYM 3 //用户查询次数超过这个值后会提醒商家多进货#define BUYI 2 //用户查询次数超过这个值后会提醒商家进货typedefstruct good{struct good* lchild;char item[LNAME];int count;int bf;struct good* rchild;}*BSTree;typedefstructtempg{char item[LNAME];int count;structtempg *next;};structtempg *headt;BSTreedt;structtempg *tnow=NULL;structtempg *tg;intInit();intInitTree(BSTree *DT) ;voidDestroyTree(BSTree *DT) ;intInsertAVL(BSTree *T,char *e,int *taller,int x); voidLeftBalance(BSTree *T);voidRightBalance(BSTree * T);voidL_Rotate(BSTree *p);voidR_Rotate(BSTree *p);intCharInput(char *a);int Compare(char *a,char *b);void print(char *a);int Input();intSearchTemp(char *e);voidTempSearch();intInsertbytemp(char *a);BSTreeGoodSearch(BSTreeT,char *e); voidTravelprint(BSTreeDT,void(*Visit)(char *a)); voidRightProcess(BSTree *p,int *taller); voidLeftProcess(BSTree *p,int *taller); intDeleteAVL(BSTree *p,char *e,int *taller);void Delete2(BSTreeq,BSTree *r,int *taller); intInsertchar(char *a,char *b);int main(){headt=(structtempg*)malloc(sizeof(structtempg));headt->next=NULL;Init();Input();DestroyTree(&dt);return 1;}intInitTree(BSTree *DT){*DT=NULL;return 1;}voidDestroyTree(BSTree *DT){if(*DT) // 非空树{if((*DT)->lchild) // 有左孩子DestroyTree(&(*DT)->lchild); // 销毁左孩子子树if((*DT)->rchild) // 有右孩子DestroyTree(&(*DT)->rchild); // 销毁右孩子子树free(*DT); // 释放根结点*DT=NULL; // 空指针赋0}}intInit(){int k;int state;InitTree(&dt);printf("初始化超市,开始录入商品，请您输入商品名字，结束请输入end:\n");while(1){char temp[LNAME];CharInput(temp);if(temp[0]=='e'&&temp[1]=='n'&&temp[2]=='d'){printf("录入结束!\n");return 1;}state=InsertAVL(&dt,temp,&k,0);if(state==1){printf("录入成功!\n");Travelprint(dt,print);printf("\n");}else if(state==0){printf("已有此商品，请重新录入\n");}}}intInsertAVL(BSTree *T,char *e,int *taller,int x){if(!*T){*T=(BSTree)malloc(sizeof(struct good));Insertchar((*T)->item,e);//字符串赋值函数(*T)->lchild=(*T)->rchild=NULL;(*T)->bf=EH;(*T)->count=x;*taller=1;}else{if(Compare(e,(*T)->item)==0){*taller=0;return 0;}else if(Compare(e,(*T)->item)==-1){if(!InsertAVL(&(*T)->lchild,e,taller,x)){return 0;}if(*taller){ switch((*T)->bf){case LH:LeftBalance(T);*taller=0;break;case EH:(*T)->bf=LH;*taller=1;break;case RH:(*T)->bf=EH;*taller=0;}}}else{if(!InsertAVL(&(*T)->rchild,e,taller,x)){return 0;}if(*taller){switch((*T)->bf){case LH:(*T)->bf=EH;*taller=0;break;case EH:(*T)->bf=RH;*taller=1;break;case RH:RightBalance(T);*taller=0;}}}}return 1;}voidLeftBalance(BSTree *T){BSTreelc,rd;lc=(*T)->lchild; // lc指向*T的左子树根结点switch(lc->bf){ // 检查*T的左子树的平衡度，并作相应平衡处理case LH: // 新结点插入在*T的左孩子的左子树上，要作单右旋处理(*T)->bf=lc->bf=EH;R_Rotate(T);break;case RH: // 新结点插入在*T的左孩子的右子树上，要作双旋处理rd=lc->rchild; // rd指向*T的左孩子的右子树根switch(rd->bf){ // 修改*T及其左孩子的平衡因子case LH:(*T)->bf=RH;lc->bf=EH;break;case EH:(*T)->bf=lc->bf=EH;break;case RH:(*T)->bf=EH;lc->bf=LH;}rd->bf=EH;L_Rotate(&(*T)->lchild); // 对*T的左子树作左旋平衡处理R_Rotate(T); // 对*T作右旋平衡处理}}voidRightBalance(BSTree *T){BSTreerc,rd;rc=(*T)->rchild; // rc指向*T的右子树根结点switch(rc->bf){ // 检查*T的右子树的平衡度，并作相应平衡处理case RH: // 新结点插入在*T的右孩子的右子树上，要作单左旋处理(*T)->bf=rc->bf=EH;L_Rotate(T);break;case LH: // 新结点插入在*T的右孩子的左子树上，要作双旋处理rd=rc->lchild; // rd指向*T的右孩子的左子树根switch(rd->bf){ // 修改*T及其右孩子的平衡因子case RH: (*T)->bf=LH;rc->bf=EH;break;case EH: (*T)->bf=rc->bf=EH;break;case LH: (*T)->bf=EH;rc->bf=RH;}rd->bf=EH;R_Rotate(&(*T)->rchild); // 对*T的右子树作右旋平衡处理L_Rotate(T); // 对*T作左旋平衡处理}}voidL_Rotate(BSTree *p){BSTreerc;rc=(*p)->rchild; // rc指向p的右子树根结点(*p)->rchild=rc->lchild; // rc的左子树挂接为p的右子树rc->lchild=*p;*p=rc; // p指向新的根结点}voidR_Rotate(BSTree *p){BSTreelc;lc=(*p)->lchild; // lc指向p的左子树根结点(*p)->lchild=lc->rchild; // lc的右子树挂接为p的左子树lc->rchild=*p;*p=lc; // p指向新的根结点}intInsertchar(char *a,char *b){inti;for(i=0;i<LNAME;i++){a[i]=b[i];}return 1;}intCharInput(char *a){inti;scanf("%c",&a[0]);if(a[0]=='\n'){i=0;}else{i=1;}for(;i<LNAME;i++){scanf("%c",&a[i]);if(a[i]==' '||a[i]=='\n'){for(;i<LNAME;i++){a[i]=' ';}return 1;}}return 1;}int Compare(char *a,char *b){inti;for(i=0;i<LNAME;i++){if(a[i]>b[i])return 1;else if(a[i]<b[i])return -1;elsecontinue;}return 0;}void print(char *a){inti;for(i=0;i<LNAME;i++){printf("%c",a[i]);}}int Input(){intwant,k,state,x;BSTree p;while(1){char temp[LNAME];printf("\n请输入操作：查询输入1，增加商品输入2，删除商品输入3，结束使用输入4\n");scanf("%d",&want);switch(want){case 1:printf("请输入你想要查询的商品名称:\n");CharInput(temp);p=GoodSearch(dt,temp);if(p){printf("查询到的商品为:\n");print(p->item);printf("查询次数:%d\n",p->count);break;}else{//TempSearch();printf("对不起，没有您要查询的商品!\n");break;}case 2:printf("请输入你想要增加的商品的名称:\n");CharInput(temp);x=Insertbytemp(temp);state=InsertAVL(&(dt),temp,&k,x);if(state==1){printf("增加成功!库中商品有:\n");Travelprint(dt,print);break;}else if(state==0){printf("库中已有此商品!\n");break;}case 3:printf("请输入你想要删除的商品的名称:\n");CharInput(temp);k=0;state=DeleteAVL(&dt,temp,&k);if(state==0){printf("对不起，没有找到您要删除的商品，请核对\n!");break;}else{printf("删除成功!库中剩余商品为:");Travelprint(dt,print);break;}case 4:printf("谢谢使用!");return 1;default:printf("错误输入!程序结束!");return 1;}}}intInsertbytemp(char *a){structtempg *tx;tx=headt;tg=headt->next;while(tg!=NULL){if(Compare(tg->item,a)==0){tx->next=tg->next;if(tnow==tg){tnow=tx;}return (tg->count);}tx=tg;tg=tg->next;}return 0;}intSearchTemp(char *e){if(tnow==NULL){tnow=(structtempg*)malloc(sizeof(structtempg));headt->next=tnow;}else{tg=headt->next;while(tg!=NULL){if(Compare(tg->item,e)==0){tg->count++;if(tg->count>=BUYI){printf("\n(to boss:这种商品市场前景好，可采购!)");}return 1;}tg=tg->next;}tg=(structtempg*)malloc(sizeof(structtempg));tnow->next=tg;tnow=tg;}tnow->next=NULL;tnow->count=1;Insertchar(tnow->item,e);return 1;}BSTreeGoodSearch(BSTreeT,char *e){if((!T)){SearchTemp(e);return T;}else if((Compare(e,T->item)==0)){ T->count++;if(T->count>=BUYM){printf("\n(to boss:这种商品销量好，可多采购!)\n");}return T;}else if(Compare(e,T->item)==-1)returnGoodSearch(T->lchild,e);elsereturnGoodSearch(T->rchild,e);}voidTempSearch(){tg=headt->next;while(tg!=NULL){print(tg->item);printf(" %d ",tg->count);tg=tg->next;}}voidTravelprint(BSTreeDT,void(*Visit)(char *a)){if(DT){Travelprint(DT->lchild,Visit); // 先中序遍历左子树Visit(DT->item); // 再访问根结点printf("查询次数:%d ",DT->count);Travelprint(DT->rchild,Visit); // 最后中序遍历右子树}}intDeleteAVL(BSTree *p,char *e,int *taller){int k;BSTree q;if (!*p)return 0;else if (Compare(e,(*p)->item)==-1){k=DeleteAVL(&(*p)->lchild,e,taller);if (*taller==1)LeftProcess(&(*p),taller);return k;}else if (Compare(e,(*p)->item)==1){k=DeleteAVL(&(*p)->rchild,e,taller);if (*taller==1)RightProcess(&(*p),taller);return k; }else /*找到了关键字为x的结点,由p指向它*/{q=*p;if ((*p)->rchild==NULL) /*被删结点右子树为空*/{*p=(*p)->lchild;free(q);*taller=1;}else if ((*p)->lchild==NULL) /*被删结点左子树为空*/{*p=(*p)->rchild;free(q);*taller=1;}else /*被删结点左右子树均不空*/{Delete2(q,&q->lchild,taller);if (*taller==1)LeftProcess(&q,taller);*p=q;}return 1;}}void Delete2(BSTreeq,BSTree *r,int *taller)/*由DeleteAVL()调用,用于处理被删结点左右子树均不空的情况*/ {if ((*r)->rchild==NULL){Insertchar(q->item,(*r)->item);q=*r;*r=(*r)->lchild;free(q);*taller=1;}else{Delete2(q,&(*r)->rchild,taller);if (*taller==1)RightProcess(&(*r),taller);}}void LeftProcess(BSTree *p,int *taller) /*在删除结点时进行左处理*/ {BSTree p1,p2;if ((*p)->bf==1){(*p)->bf=0;*taller=1;}else if ((*p)->bf==0){(*p)->bf=-1;*taller=0;}else /*p->bf=-1*/{p1=(*p)->rchild;if (p1->bf==0) /*需作RR调整*/{(*p)->rchild=p1->lchild;p1->lchild=*p;p1->bf=1;(*p)->bf=-1;*p=p1;*taller=0;}else if (p1->bf==-1) /*需作RR调整*/ {(*p)->rchild=p1->lchild;p1->lchild=*p;(*p)->bf=p1->bf=0;*p=p1;*taller=1;}else /*需作RL调整*/{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;*taller=1;}}}void RightProcess(BSTree *p,int *taller) /*在删除结点时进行右处理*/ {BSTree p1,p2;if ((*p)->bf==-1){(*p)->bf=0;*taller=-1;}else if ((*p)->bf==0){(*p)->bf=1;*taller=0;}else /*p->bf=1*/{p1=(*p)->lchild;if (p1->bf==0) /*需作LL调整*/{(*p)->lchild=p1->rchild;p1->rchild=*p;p1->bf=-1;(*p)->bf=1;*p=p1;*taller=0;}else if (p1->bf==1) /*需作LL调整*/{(*p)->lchild=p1->rchild;p1->rchild=*p;(*p)->bf=p1->bf=0;*p=p1;*taller=1;}else /*需作LR调整*/{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;*taller=1;}}}。

课程设计报告设计题目：基于二叉排序树的图书信息检索学院：电子工程学院专业：电子信息工程班级： ****** 学号： ********学生姓名：**电子邮件：****************时间： 2014 年 10 月 17成绩：指导教师：c语言程序设计课程设计报告目录1 前言 (1)1.1课程设计的目的 (1)1.2 图书借阅管理系统的设计与实现的基本要求 (1)1．3数据结构相关知识的阐述 (1)2 功能描述 (2)3 系统设计 (2)4 算法设计 (3)4.1 节点数据的设计 (3)4.1.1 图书的存储结构模型 (3)4.1.1 管理员存储模型 (3)4.2 公共参变量说明 (4)4.2.1 administer *admins,*current_admin=NULL (4)4.2.2 libcard *clients,*current_client=NULL; (4)4.3 二叉排序树的插入模块的设计 (4)4.4二叉排序树的创建模块的设计 (5)4.5二叉排序树的查找模块设计 (6)4.6二叉排序树的删除模块设计 (7)4.7 主函数的设计 (9)5 详细设计 (10)5.1 采用排序二叉树作为存储结构 (10)5.2创建链表的二叉树 (10)5.3 二叉排序树的插入模块，采用递归算法实现 (11)5.4 本模块实现二叉排序树的建立 (12)5.5 二叉排序树的查找算法 (14)5.6 二叉排序树的删除算法 (15)6 调试分析 (18)6.1 进入系统 (18)6.2成进入系统之后你就可以进行相关操作了 (18)7 课程设计总结 (21)8 参考文献 (22)1 前言1.1课程设计的目的通过数据结构课程设计能更加熟练的掌握C语言以及数据结构的相关知识，能宏观的把握数据结构的各个相关部分的知识，深入的理解各个分支结构的作用和运用，特别是通过本此课程设计更能熟练的掌握和运用二叉树的相关知识，如通过二叉树能实现查找、删除、排序等从而实现对图书借阅管理。

基于二叉排序树的商品信息查询算法的设计与实现数据结构实验报告五信计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:凹入法打印二叉树。