二叉排序树的查找实验报告

数据结构实验报告班级：信息与计算科学专业1102班学号： 1108060214姓名：朱晓东设计日期：2013.6.6西安科技大学计算机学院1.实验报告编写一个演示运用二叉排序树进行数据的的排序、插入、删除、查找等操作的程序。

2.需求分析本演示程序用vc6.0编写，完成数据的排序功能，同时能够进行数据的创建、插入、删除、查找。

（1）输入的形式和输入值的范围：创建二叉排序树时输入较多的值；插入元素时需要输入插入的元素的值；删除元素时输入元素的值；查找操作时需要输入元素的值。

所有输入中，元素的值都是整数。

（2）输出的形式：在创建、插入、删除的操作后，均显示操作后的元素的排序状况，有小到大排序。

（3）程序所能达到的功能：完成二叉排序树的生成、插入、删除、查找操作。

（4）测试数据：①插入操作中依次输入10 9 11 8 12 0（本程序是以0元素为为结束标志）；②查找操作中输入13；③插入操作中输入13；3概要设计本程序包含8个函数：（1）主函数main()（2）创建二叉排序树函数BSTCreate(BiTree* bt)（3）显示操作菜单函数menu()（4）显示二叉排序树的内容函数BSTShow(BiTree bt)（5）插入元素函数BSTInsert(BiTree* bt,DataType key)（6）删除元素函数BSTDelete(BiTree* bt,DataType key)（7）查找元素函数BSTSearch(BiTree bt,DataType key)（8）查找要删除的元素的函数DeleteNode(BiTree* bt)各函数之间的关系如下：BSTCreate(BiTree* bt)menu()BSTShow(BiTree bt)mainBSTInsert(BiTree* bt,DataType key)BSTDelete(BiTree* bt,DataType key) DeleteNode(BiTree* bt)BSTSearch(BiTree bt,DataType key)4.详细设计实现概要设计中定义的所有数据类型，对每个操作给出伪码算法。

实验报告课程名：数据结构（C语言版）实验名：二叉排序树姓名：班级：学号：撰写时间：2014.12.18一实验目的与要求1.掌握二叉排序树上进行插入和删除的操作2.利用 C 语言实现该操作二实验内容•对于一个线形表, 利用不断插入的方法, 建立起一株二叉排序树•从该二叉排序树中删除一个叶子节点, 一个只有一个子树的非叶子节，一个有两个子树的非叶子节点。

三实验结果与分析#include<stdio.h>#include<stdlib.h>//二叉查找树结点描述typedef int KeyType;typedef struct Node{KeyType key; //关键字struct Node * left; //左孩子指针struct Node * right; //右孩子指针struct Node * parent; //指向父节点指针}Node,*PNode;//往二叉查找树中插入结点//插入的话，可能要改变根结点的地址，所以传的是二级指针void inseart(PNode * root,KeyType key){//初始化插入结点PNode p=(PNode)malloc(sizeof(Node));p->key=key;p->left=p->right=p->parent=NULL;//空树时，直接作为根结点if((*root)==NULL){*root=p;return;}//插入到当前结点（*root）的左孩子if((*root)->left == NULL && (*root)->key > key){ p->parent=(*root);(*root)->left=p;return;}//插入到当前结点（*root）的右孩子if((*root)->right == NULL && (*root)->key < key){ p->parent=(*root);(*root)->right=p;return;}if((*root)->key > key)inseart(&(*root)->left,key);else if((*root)->key < key)inseart(&(*root)->right,key);elsereturn;}//查找元素,找到返回关键字的结点指针，没找到返回NULL PNode search(PNode root,KeyType key){if(root == NULL)return NULL;if(key > root->key) //查找右子树return search(root->right,key);else if(key < root->key) //查找左子树return search(root->left,key);elsereturn root;//查找最小关键字,空树时返回NULLPNode searchMin(PNode root){if(root == NULL)return NULL;if(root->left == NULL)return root;else //一直往左孩子找，直到没有左孩子的结点 return searchMin(root->left);}//查找最大关键字,空树时返回NULLPNode searchMax(PNode root){if(root == NULL)return NULL;if(root->right == NULL)return root;else //一直往右孩子找，直到没有右孩子的结点 return searchMax(root->right);//查找某个结点的前驱PNode searchPredecessor(PNode p){//空树if(p==NULL)return p;//有左子树、左子树中最大的那个if(p->left)return searchMax(p->left);//无左子树,查找某个结点的右子树遍历完了 else{if(p->parent == NULL)return NULL;//向上寻找前驱while(p){if(p->parent->right == p)break;p=p->parent;}return p->parent;}}//查找某个结点的后继PNode searchSuccessor(PNode p){//空树if(p==NULL)return p;//有右子树、右子树中最小的那个if(p->right)return searchMin(p->right);//无右子树,查找某个结点的左子树遍历完了 else{if(p->parent == NULL)return NULL;//向上寻找后继while(p){if(p->parent->left == p)break;p=p->parent;}return p->parent;}}//根据关键字删除某个结点,删除成功返回1,否则返回0//如果把根结点删掉，那么要改变根结点的地址，所以传二级指针int deleteNode(PNode* root,KeyType key){PNode q;//查找到要删除的结点PNode p=search(*root,key);KeyType temp; //暂存后继结点的值//没查到此关键字if(!p)return 0;//1.被删结点是叶子结点，直接删除if(p->left == NULL && p->right == NULL){//只有一个元素，删完之后变成一颗空树if(p->parent == NULL){free(p);(*root)=NULL;}else{//删除的结点是父节点的左孩子if(p->parent->left == p)p->parent->left=NULL;else //删除的结点是父节点的右孩子 p->parent->right=NULL;free(p);}}//2.被删结点只有左子树else if(p->left && !(p->right)){p->left->parent=p->parent;//如果删除是父结点，要改变父节点指针 if(p->parent == NULL)*root=p->left;//删除的结点是父节点的左孩子else if(p->parent->left == p)p->parent->left=p->left;else //删除的结点是父节点的右孩子p->parent->right=p->left;free(p);}//3.被删结点只有右孩子else if(p->right && !(p->left)){p->right->parent=p->parent;//如果删除是父结点，要改变父节点指针if(p->parent == NULL)*root=p->right;//删除的结点是父节点的左孩子else if(p->parent->left == p)p->parent->left=p->right;else //删除的结点是父节点的右孩子p->parent->right=p->right;free(p);}//4.被删除的结点既有左孩子，又有右孩子//该结点的后继结点肯定无左子树(参考上面查找后继结点函数) //删掉后继结点,后继结点的值代替该结点else{//找到要删除结点的后继q=searchSuccessor(p);temp=q->key;//删除后继结点deleteNode(root,q->key);p->key=temp;}return 1;}//创建一棵二叉查找树void create(PNode* root,KeyType *keyArray,int length) {int i;//逐个结点插入二叉树中for(i=0;i<length;i++)inseart(root,keyArray[i]);}int main(void){int i;PNode root=NULL;KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9}; create(&root,nodeArray,11);for(i=0;i<2;i++)deleteNode(&root,nodeArray[i]);printf("%d\n",searchPredecessor(root)->key); printf("%d\n",searchSuccessor(root)->key); printf("%d\n",searchMin(root)->key);printf("%d\n",searchMax(root)->key);printf("%d\n",search(root,13)->key);return 0;}图1：二叉树排序实验结果。

实验报告：二叉树第一篇：实验报告：二叉树实验报告二叉树一实验目的1、进一步掌握指针变量，动态变量的含义；2、掌握二叉树的结构特性以及各种存储结构的特点及适用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

4、熟悉各种存储结构的特征以及如何应用树结构解决具体问题。

二实验原理树形结构是一种应用十分广泛和重要的非线性数据结构，是一种以分支关系定义的层次结构。

在这种结构中，每个数据元素至多只有一个前驱，但可以有多个后继；数据元素之间的关系是一对多的层次关系。

树形结构主要用于描述客观世界中具有层次结构的数据关系，它在客观世界中大量存在。

遍历二叉树的实质是将非线性结构转为线性结构。

三使用仪器，材料计算机 2 Wndows xp 3 VC6.0四实验步骤【问题描述】建立一个二叉树，请分别按前序，中序和后序遍历该二叉树。

【基本要求】从键盘接受输入（按前序顺序），以二叉链表作为存储结构，建立二叉树（以前序来建立），并采用递归算法对其进行前序，中序和后序遍历，将结果输出。

【实现提示】按前序次序输入二叉树中结点的值（一个整数），0表示空树，叶子结点的特征是其左右孩子指针为空。

五实验过程原始记录基本数据结构描述； 2 函数间的调用关系；用类C语言描述各个子函数的算法；附录：源程序。

六试验结果分析将实验结果分析、实验中遇到的问题和解决问题的方法以及关于本实验项目的心得体会，写在实验报告上。

第二篇：数据结构-二叉树的遍历实验报告实验报告课程名：数据结构（C语言版）实验名：二叉树的遍历姓名：班级：学号：时间：2014.11.03一实验目的与要求1.掌握二叉树的存储方法2.掌握二叉树的三种遍历方法3.实现二叉树的三种遍历方法中的一种二实验内容• 接受用户输入一株二叉树• 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序三实验结果与分析//*********************************************************** //头文件#include #include //*********************************************************** //宏定义#define OK 1 #define ERROR 0 #define OVERFLOW 0//*********************************************************** typedef struct BiTNode { //二叉树二叉链表存储结构char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//******************************** *************************** int CreateBiTree(BiTree &T){ //按先序次序输入二叉中树结点的值，空格表示空树//构造二叉链表表示的二叉树T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;Creat eBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构，先序遍历二叉树的递归算法if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrd erTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，中序遍历二叉树的递归算法if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderT raverse(T->rChild);} }//*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉链表存储结构，后序遍历二叉树的递归算法if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild) ;printf(“%c”,T->data);} }//*********************************************************** void main(){ //主函数分别实现建立并输出先、中、后序遍历二叉树printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍历二叉树:”);PreOrderTraverse(Tree);printf(“n中序遍历二叉树:”);InOrderTraverse(Tree);printf(“n后序遍历二叉树:”);PostOrderTraverse(Tree);}图1:二叉树的遍历运行结果第三篇：数据结构二叉树操作验证实验报告班级：计算机11-2 学号：40 姓名：朱报龙成绩：_________实验七二叉树操作验证一、实验目的⑴ 掌握二叉树的逻辑结构；⑵ 掌握二叉树的二叉链表存储结构；⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。

软件学院数据结构实验报告2012 ～2013 学年第一学期 2011 级水利信息管理专业班级：学号：姓名：实验六查找算法实验一、实验目的1、掌握静态查找表的查找算法2、掌握二叉排序树的查找算法3、掌握哈希函数的构造和哈希表的查找4、了解查找表的广泛应用二、实验内容1、有序表的查找1.1 数据结构的设计有序表的存储结构（数组表示)#define Max 20int a[Max] = {05,13,19,21,37,56,64,75,80,88,92}1.2 基本思想：折半查找算法在有序表中，取中间的记录作为比较对象，如果要查找记录的关键字等于中间记录的关键字，则查找成功；若要查找记录的关键字小于中间记录的关键字，则在中间记录的左半区继续查找；若要查找记录的关键字大于中间记录的关键字，则在中间记录的右半区继续查找。

不断重复上述查找过程，直到查找成功，或有序表中没有所要查找的记录，查找失败。

例：输入：查找记录的关键字 k = 13，k =37，k =99输出：k=13，查找成功；k=37，查找成功；k=99，查找不成功1.3 实验步骤：源程序：1.4 运行结果：2、二叉排序树的查找2.1 数据结构的设计二叉链表的存储结构表示：typedef int datatype;struct bi_search_tree{datatype key;struct bi_search_tree *left, *right;}bst_tree;2.2 基本思路先将输入的数据记录序列通过二叉排序树的插入算法建立一个二叉排序树，然后在二叉排序树中查找某个给定的关键字，返回查找成功或者不成功的结果输入：（1）数据记录序列{37,56,05,13,19,21, 64, 88, 75,80,92}建立二叉排序树，（2）查找记录的关键字 k = 13，k =37，k =99输出：k=13，查找成功；k=37，查找成功；k=99，查找不成功2.3 实验步骤：主要函数声明：主函数代码：2.4 运行结果：三、问题讨论1、折半查找有哪些特点？2、二叉排序树有那些特点？四、实验心得实验源码：（折半查找）#include <stdio.h>#define LENGTH 20void Search(int *fp,int data,int length);void main(){int count,i,choise;int arr[LENGTH];printf("请输入你的数据的个数:\n");scanf("%d",&count);printf("请输入%d个有序的数据\n",count);for(i=0;i<count;i++){scanf("%d",&arr[i]);}printf("请输入你要查找的数据:\n");scanf("%d",&choise);Search(arr,choise,count);}void Search(int *fp,int data,int length){int i=0;int low,high,middle;low=0; high=length;while (low<=high){middle=(low+high)/2;i++;if(fp[middle]<data){low=middle+1;}else if(fp[middle]>data){high=middle-1;}else{printf("经过%d次查找，查找到数据:%d.\n",i,data);return;}}printf("经过%d次查找，未能查找到数据:%d.\n",i,data);}二叉排序树：#include <stdio.h>#include <stdlib.h>#include <string.h>#define EQ(a,b) ((a)==(b))#define LT(a,b) ((a)< (b))#define LQ(a,b) ((a)<=(b))#define TRUE 1#define FALSE 0#define OVERFLOW -2typedef int KeyType;typedef int Status;typedef struct{KeyType key; /*关键字域*/}SElemType;typedef struct BitNode{SElemType data; /*存储空间基址,建表时按实际长度分配，0号单元留空*/ struct BitNode *lchild,*rchild;}BitNode,* BiTree;/*二叉排序树的插入*/Status InsertBST(BiTree T, KeyType key){BiTree s;if(!T){s=(BiTree)malloc(sizeof(BitNode));s->data.key=key;s->lchild=s->rchild=NULL;T=s;}else if LT(key,T->data.key)InsertBST(T->lchild,key);else InsertBST(T->rchild,key);return TRUE;}/*创建二叉排序树*/void CreateBST(BiTree T){KeyType key;T=NULL;scanf("%d",&key);while(key!=0){InsertBST(T,key);scanf("%d",&key);}}/*中序遍历*/void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);printf("%4d",T->data.key);InOrderTraverse(T->rchild);}}/*打印二叉树*/Status PrintTree(BiTree T,int n){int i=0;if(T == NULL)return FALSE;PrintTree(T->rchild,n+1);for(i=0;i<n;i++)printf(" ");printf("%d\n",T->data.key);PrintTree(T->lchild,n+1);return TRUE;}/*二叉排序树的查找*/BiTree SearchBST(BiTree T,KeyType key){if(!T){printf("Can not find!!\n");return T;}else if EQ(key,T->data.key){return T;}else if LT(key,T->data.key) return SearchBST(T->lchild,key); else return SearchBST(T->rchild,key);}/*二叉排序树的删除*/Status Delete(BiTree p){BiTree q,s;if(!p->rchild){q=p;p=p->lchild;free(q);}else if(!p->lchild){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;// delete s;}return TRUE;}Status DeleteBST(BiTree T,KeyType key){if(!T)return FALSE;else{if (EQ(key,T->data.key))return Delete(T);elseif(LT(key,T->data.key))return DeleteBST(T->lchild,key);else return DeleteBST(T->rchild,key);}}void main() {BiTree b1,b2;KeyType key;int t;begin:printf("1:创建二叉排序树\n");printf("2:打印排序树\n");printf("3:查找结点\n");printf("4:中序遍历\n");printf("5:插入结点\n");printf("6:删除结点\n");printf("0:退出\n");printf("请选择要进行的操作:");scanf("%d",&t);switch(t){case 1:printf("Input every key (0 to quit):");CreateBST(b1);PrintTree(b1,0);//排序树的结果打印出来goto begin;case 2:PrintTree(b1,0);goto begin;case 3:printf("Input the key to search:");scanf("%d",&key);if(key!=0){b2=SearchBST(b1,key);//把 key 为根的子树打印出来PrintTree(b2,0);printf("\nThe root is the key to search!!\n\n");}else printf("Can not find!!\n");goto begin;case 4:InOrderTraverse(b1);goto begin;case 5:printf("输入要插入的数据：");scanf("%d",&key);if(InsertBST(b1, key))printf("\n插入完毕！\n");else printf("插入失败\n");goto begin;case 6:printf("输入要删除的数据：");scanf("%d",&key);if(DeleteBST(b1, key))printf("\n删除完毕！\n");else printf("删除失败\n");goto begin;case 0: break;default: printf("输入错误\n");}}。

二叉排序树的实验报告二叉排序树的实验报告引言：二叉排序树（Binary Search Tree，简称BST）是一种常用的数据结构，它将数据按照一定的规则组织起来，便于快速的查找、插入和删除操作。

本次实验旨在深入了解二叉排序树的原理和实现，并通过实验验证其性能和效果。

一、实验背景二叉排序树是一种二叉树，其中每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。

这种特性使得在二叉排序树中进行查找操作时，可以通过比较节点的值来确定查找的方向，从而提高查找效率。

二、实验目的1. 理解二叉排序树的基本原理和性质；2. 掌握二叉排序树的构建、插入和删除操作；3. 验证二叉排序树在查找、插入和删除等操作中的性能和效果。

三、实验过程1. 构建二叉排序树首先，我们需要构建一个空的二叉排序树。

在构建过程中，我们可以选择一个节点作为根节点，并将其他节点插入到树中。

插入节点时，根据节点的值与当前节点的值进行比较，如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。

重复这个过程，直到所有节点都被插入到树中。

2. 插入节点在已有的二叉排序树中插入新的节点时，我们需要遵循一定的规则。

首先，从根节点开始，将新节点的值与当前节点的值进行比较。

如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。

如果新节点的值与当前节点的值相等，则不进行插入操作。

3. 删除节点在二叉排序树中删除节点时，我们需要考虑不同的情况。

如果要删除的节点是叶子节点，即没有左右子树，我们可以直接删除该节点。

如果要删除的节点只有一个子树，我们可以将子树连接到要删除节点的父节点上。

如果要删除的节点有两个子树，我们可以选择将其右子树中的最小节点或左子树中的最大节点替代该节点，并删除相应的替代节点。

四、实验结果通过对二叉排序树的构建、插入和删除操作的实验，我们得到了以下结果：1. 二叉排序树可以高效地进行查找操作。

深圳大学实验报告
课程名称：数据结构实验与课程设计
实验项目名称：二叉排序树实验
学院：计算机与软件学院
专业：
指导教师：
报告人：学号：班级： 3班
实验时间： 2012-11-28 实验报告提交时间： 2012-12-5
教务部制
int main(int argc,char *argv[])
{
int t[32];
int i,j,Key;
int TestNum,SampleNum;
// freopen("cin.txt","r",stdin);
// freopen("cout.txt","w",stdout);
BiSortTree *BST=new BiSortTree;
cin>>TestNum;
for(i=0;i<TestNum;i++){
cin>>SampleNum;
for(j=0;j<SampleNum;j++) cin>>t[j];
BST->CreateBST(t,SampleNum);
cin>>Key;
BST->SearchBST(Key);
cout<<BST->BisSuccess<<" "<<BST->BisPos <<" "<<BST->BisCount<<endl;
}
return 0;
}
运行截图：
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。

《数据结构》实验报告◎实验题目: 利用二叉排序树对一组数据排序并查找元素◎实验目的：(1)熟悉二叉排序树的生成算法；(2)了解将排序二叉树转化为有序排列的方法；(3)学会在一组数据中查找元素。

◎实验内容：建立一组数据的二叉排序树，然后中序遍历，并查找待查找元素。

一、需求分析1．输入的形式和输入值的范围:本程序要求输入待排序数的个数，并逐个输入待排序数，最后输入待查找元素的值。

2．输出的形式:按从小到大的顺序输出排过序的数，并输出查找结果，如果存在，还需输出待查找数在已排序序列中的位置。

3．程序所能达到的功能:对确定个数的一组数实现递增排序，并查找待查找元素。

4．测试数据：待排序数个数:5;待排序数:12 43 23 54 8;已存在元素查找:23;不存在的元素查找:10二概要设计1.二叉排序树的生成模块:根据二叉排序树的定义，任一节点如果有左子树，其左子树各节点的数据必须小于该节点的数据；任一节点如果有右子树，其右子树各节点的数据必须等于或大于该节点的数据。

则可将第一个数据作为整个二叉排序树的根节点，以后的数据都从根节点起，由上而下逐层与原有节点的数据相比较，若较原节点数值小，则进而与其左孩子节点的数值比，否则与其右孩子节点数据比，直至找到一个节点相应的指针是空指针了，即将新结点插入此处作为终端节点。

2.已排序序列的输出与查找元素模块:根据排序二叉树的结构特点，只要对该二叉树进行中序遍历，即可按从小到大的顺序访问这些数据节点，再在访问这些节点的时候与待查找元素比较，如果找到，记下该数据位置，如果访问完了还没找到，则待查找元素不存在。

三详细设计1.定义结构体变量typedef struct node{int data;struct node *lchild;struct node *rchild;}Lnode,*Linklist;2.定义指针栈typedef struct{Linklist data[MAXSIZE];int top;}Seqstack;3.初始化栈函数void Initstack(Seqstack &s){s.top=-1;}4.判断栈空函数，如果栈空返回1，否则返回0int StackEmpty(Seqstack &s){if(s.top==-1)return 1;elsereturn 0;}5.入栈函数void push(Seqstack &s,Linklist x){s.top++;s.data[s.top]=x;}6.出栈函数Linklist pop(Seqstack &s){return s.data[s.top--];}7.二叉排序树的生成函数，具体算法为:(1)读取一个待排序数；(2)生成一个新节点，将读入数据赋给新节点；(3)若根节点为空，则另根节点等于该新节点，否则○1如果小于根节点，沿左链域比较；○2否则沿右链域比较；(4)直至到终端，插入该结点。

实习报告一、需求分析1、问题描述利用平衡二叉树实现一个动态查找表。

（1）实现动态查找表的三种基本功能：查找、插入和删除。

（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。

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

在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。

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

（3）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数字{1，2，3······}，关键字出现的顺序没有限制，允许出现重复的关键字，并对其进行相应的提示。

（4）平衡二叉树的显示采用图形界面画出图形。

2、系统功能打开数据文件，用文件中的关键字来演示平衡二叉树操作的过程。

3、程序中执行的命令包括：（1）(L)oad from data file //在平衡的二叉树中插入关键字；（2）(A)ppend new record //在平衡的二叉树中查找关键字；（3）(U)pate special record //显示调整过的平衡二叉树；（4）(D)elete special record //删除平衡二叉树中的关键字；（5）(Q)uit //结束。

4、测试数据：平衡二叉树为：图 1 插入关键字10之前的平衡二叉树插入关键字：10；调整后：图 2 插入关键字10之后的平衡二叉树删除关键字：14；调整后：图 3 删除关键字14后的平衡二叉树查找关键字：11；输出：The data is here!图 3 查找关键字11后的平衡二叉树二、概要设计本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。

动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。

1、动态查找表的抽象数据类型定义为：ADT DynamicSearchTable{数据对象D ：D是具有相同特性的数据元素的集合。

二叉排序树的查找与性能分析二叉排序树的查找与性能分析问题分析：本实验是通过建立一个二叉树，并通过输入报名号，查找出与此报名号对应的学生的其他信息，并通过查找的次数来分析此程序的性能，最后与做平衡二叉树的查找与性能分析的那组比较，分析。

设计思路：首先进行二叉链表的存储表示，将数据类型和基本操作定义好。

一．二叉排序树的查找二叉排序树的查找包含二叉排序树的建立，二叉排序树的插入，二叉树的遍历，二叉排序树的生成，以及二叉排序树的查找等部分。

1．二叉排序树的建立二叉数是每个结点至多只有两颗子树的树形结构即左子树和右子树，在二叉树的第i层上至多有2^(i-1)个结点（i≥1）。

而二叉排序树是动态的，中序遍历后，二叉排序树将是一个递增有序序列。

二叉排序树可以是一个空树，也可以是一个有如下性质的二叉树：（1）左子树非空，左子树上所有结点的值均小于根结点的值；（2）右子树非空，右子树上所有结点的值均大于根结点的值；（3）左右子树本身又各是一颗二叉排序树。

利用链式存储结构，由一个数据元素和分别指向左右结点的指针构成，即二叉链表。

首先可以按线序次序输入二叉树结点的值，如果是空指针（即NULL）则为空树，这样就可以生成根结点，再利用递归构造左子树和右子树。

并将关键字即学号插入二叉排序中;在建立时就可将二叉树中序遍历。

2．二叉排序树的插入在二叉排序树中插入新节点，要保证插入后的二叉树仍然符合二叉排序树的定义。

插入过程如下:若二叉排序树为空，则待插入结点s作为根结点插入到空树中；当非空时，将待插结点关键字s->key和树根关键字t->key进行比较，若s->keyt=t->key，则无需插入；若s->keykey，则插入到根的左子树；若s->key>t->key，则插入到根的右子树。

而子树的插入过程与树中的插入过程相同。

如此进行下去，知道把结点s作为新的树叶插入到二叉排序树中，或者直到发现已相同的关键字（即学号）结点为止。