二叉树的排序与查找上机实验

数据结构实验报告班级：信息与计算科学专业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.详细设计实现概要设计中定义的所有数据类型，对每个操作给出伪码算法。

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;}}。

叉树排序类及操作(1)实验描述我们知道二叉树或者为空，或者是具有下列性质的二叉树：如根节点的左子树不空，则左子树所有结点的值均小于根结点值；如根节点的右子树不空，则右子树所有结点的值均大于根结点值；根节点的左右子树也分别是二叉排序树。

本实验将进行编写二叉树排序的类和其排序各操作方法实现。

其中包括二叉排序树的插入，删除，查找。

(2)实验过程二叉排序树的插入：依次读入给定序列中的每一个元素；(1) 若当前的二叉排序树为空，则读入的元素为根结点；(2) 若读入的元素值小于根结点值，则将元素插入到左子树中；(3) 若读入的元素值不小于根结点值，则将元素插入到右子树中。

无论是插入到左子树还是右子树，同样按照上述方法处理。

输入：长度为n的无序序列A(1 : n)。

二叉排序树的删除：首先要找到被删元素所在的结点p与它的父结点q：(1)若p为叶子结点，则直接删除该结点，再修改其父结点的指针。

(2)若p为单支子树(即只有左子树或只有右子树)。

此时，如果p是q的左子结点，则将p的单支子树链接到q的左指针上；否则将p的单支子树链接到q 的右指针上。

⑶若p的左子树与右子树均不空。

此时，如果p的左子结点的右子树为空，贝U 将p的左子结点值赋给p的值域，左子结点的左子树链接到结点p的左指针上；否则，从结点p的左子结点开始沿右链进行搜索，直到发现某结点s的右指针空为止，将结点s的值赋给结点p的值域，将结点s的左子树链接到s父结点的右指针上。

二叉排序树的查找：从二叉排序树的根结点开始与被查值进行比较：(1)若被查值等于根结点值，查找成功，查找过程结束。

(2) 若被查值小于根结点值，则到左子树中去查找。

(3) 若被查值大于根结点值，则到右子树中去查找。

在左、右子树中查找时也采用上述方法。

查找过程直到查找成功或所考虑的子树已空为止。

输入：二叉排序树头指针BT以及存储空间；被查元素X。

(3)实验结果及分析二叉排序树的插入：输出：二叉排序树的头指针BT二叉排序树的查找：输出：被查元素x在二叉排序树空间中的存储结点序号p(4)实验结论二叉排序树有一个重要特征：中序遍历二叉排序树可以得到有序序列。

实验七二叉排序树[请参考教材228页算法9.5(b)和算法9.6]一、实验目的熟悉二叉排序树的使用。

掌握如何使用C语言实现二叉树的说明、创建以及二叉排序树的生成等操作。

二、实验要求熟悉C语言编程。

三、实验内容给定一个记录关键字的值，与二叉排序树的根结点值比较，如果小于根结点的值，则向左子树查找；如果大于根结点的值，则向右子树查找。

如果查找到叶子结点leaf，仍没有找到记录，则：如果关键字的值小于leaf的值，则插入该leaf结点的左边，做leaf的左孩子，否则做leaf的右孩子。

四、实验步骤1．用C语言实现二叉树的说明2．直接将输入的值作为根结点的值3．与根结点比较，小于则放到左子树上，大于则放到右子树上。

注：编程指导1、定义二叉树结构：typedef struct BiTNode {int data;struct BiTNode *lChild, *rChild;} BiTNode, *BiTree;#define BSTMAXSIZE 62、变量说明及赋初值：int i, lData, rData;int KeyList[BSTMAXSIZE] = {56,64,92,80,88,75}; // 关键字的值BiTNode BSTNode[BSTMAXSIZE], *BSTree, *p; // 定义静态二叉树各结点，根// 指针，辅助指针BSTNode[0].data = KeyList[0];BSTNode[0].lChild = NULL;BSTNode[0].rChild = NULL;BSTree = &BSTNode[0]; // 树根3、在二叉排序树中依次插入新结点for (i=1; i<BSTMAXSIZE; i++) {BSTNode[i].data = KeyList[i]; // 节点赋值BSTNode[i].lChild = NULL;BSTNode[i].rChild = NULL;p = BSTree;while (1==1) {if (BSTNode[i].data < p->data) {if (p->lChild != NULL) p = p->lChild;else {p->lChild = &BSTNode[i]; break;}}if (BSTNode[i].data > p->data) {if (p->rChild != NULL) p = p->rChild;else {p->rChild = &BSTNode[i]; break;}}if (BSTNode[i].data == p->data) break;}}4、显示结果for (i=0; i<BSTMAXSIZE; i++) {lData = rData = 0;if (!BSTNode[i].lChild==0) lData = BSTNode[i].lChild->data;if (!BSTNode[i].rChild==0) rData = BSTNode[i].rChild->data;printf("%6x: data=%d, l=%02d[%6x], r=%02d[%6x]\n",&BSTNode[i], BSTNode[i].data, lData, BSTNode[i].lChild, rData, BSTNode[i].rChild);}。