数据结构课程设计--二叉排序树的实现.docx

课 程 设 计

课程名称 数据结构课程设计
题目名称 二叉排序树的实现
学 院 应用数学学院
专业班级
学 号
学生姓名
指导教师

2013 年 12 月 26 日
1.设计任务
1） 实现二叉排序树，包括生成、插入，删除；
2） 对二叉排序树进行先根、中根、和后根非递归遍历；
3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上
用树的形状表示出来。
4） 分别用二叉排序树和数组去存储一个班(50人以上)的成员信
息(至少包括学号、姓名、成绩3项),对比查找效率，并说明
为什么二叉排序树效率高（或者低）。

2. 函数模块：
2.1.主函数main模块功能
1.通过bstree CreatTree()操作建立二叉排序树。
2.在二叉排序树t中通过操作bstree InsertBST(bstree t,int
key,nametype name,double grade)插入一个节点。
3. 从二叉排序树t中通过操作void Delete(bstree &p)删除任意节点。
4. 在二叉排序树t中通过操作bstnode *SearchBST(bstree t,keytype key)查找节点。
5. 在二叉排序树t中通过操作p=SearchBST(t,key)查询，并修改节点信息
6. 非递归遍历二叉排序树。
7. 定义函数void compare()对数组和二叉排序树的查找效率进行比较比较。

2.2创建二叉排序树CreatTree模块
从键盘中输入关键字及记录，并同时调用插入函数并不断进行插入。最后，返回根节点T。
2.3删除模块：
二叉排序树上删除一个阶段相当于删去有序系列中的一个记录，只要在删除某个节点之后依旧保持二叉排序树的性质即可。假设二叉排序树上删除节点为*p（指向节点的指针为p），其双亲节点为*f（节点指针为f）。若*p节点为叶子节点，则即左右均为空树，由于删去叶子节点不破坏整棵树的结构，则只需修改其双亲节点的指针即可；若*p节点只有左子树或只有右子树，此时只要令左子树或右子树直接成为其双亲节点*f的左子树即可；若*p节点的左子树和右子树均不为空，其一可以令*p的左子树为*f的左子树，而*p的右子树为*s的右子树，其二可以令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。在二叉排序树中删除一个节点的算法为
void DeleteData(bstree &t,keytype key)
若二叉排序树t中存在关键字等于key的数据元素，则删除该数据元素节点，并返回TRUE，否则返回FALSE。
2.4插入模块
二叉排序树是一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值得节点时在进行插入。新插入的节点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子的节点。一个无序系列可以通过构造一棵二叉排序树而变成一个有序系列，构造树的过程即为对无序系列进行排序的过程， 并且每次插入的节点都是二叉排序树上新的叶子节点，则在进行插入操作时，不必移动其他节点，仅需改变某个节点的指针由空变为非空即可。二叉排序树的插入算法为
bstree InsertBST(bstree t,int key,nametype name,double grade)
若二叉排序树中不存在关键字等于key的数据元素时，插入元素并返回TRUE。
2.5查找模块
二叉排序树又称二叉查找树，当二叉排序树不为空时，首先将给定的值和根节点的关键字比较，若相等则查找成功，否则将依据给定的值和根节点关键字之间的大小关系，分别在左子树或右子树上继续进行查找。为此定义一个二叉排序树的查找算法为
bstnode *SearchBST(bstree t,keytype key)
在根指针t所指向的二叉排序树中查找关键字等于key的数据元素，如成功，返回指向该元素节点的指针，否则返回空指针。
2.6效率比较compare模块
void compare()对数组和二叉排序树的查找效率进行比较比较。
2.7二叉排序树的遍历
先序遍历也叫做先根遍历。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。其实过程为：先遍历左子树root->left->left->left...->null，由于是先序遍历，因此一遇到节点，便需要立即访问；由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。其一可以用栈记忆在访问途中将依次遇到的节点保存下来。根据栈的先进后出、后进先出的特点特点。则可以用栈保存。每次都将遇到的节点压入栈，当左子树遍历完毕后从栈中弹出最后一个访问的节点，然后访问其右子树。
基本算法思想：
1.先访问根节点，将根节点入栈
2.重复执行两大步骤：如果该节点左孩子存在，则访问该左孩子节点，并将其指针入栈。重复以上操作，直到节点的左孩子不存在。将栈顶的元素，即其指针出栈，回到父节点，如果该指针节点的右孩子存在，则将该指针指向的右孩子节点重复执行以上步骤，直到桟为空为止。
操作函数为void x_print(Tree T)
中序遍历：中序遍历和先序遍历访问的顺序不同。中序遍历访问顺序为中序遍历左子数，在访问根节点，最后中序遍历右子树。先序遍历是先访问,再入栈；而中序遍历则是先入栈，弹栈后再访问。将二叉树的根节点入栈，如果该节点有左孩子，将左孩子直接入栈，重复该操作，直到该节点无左孩子；在将栈顶元素出栈，并访问该节点指向的节点，如果该指针指向的右孩子存在，则将当前指针指向右孩子节点。重复执行步骤直到栈为空为止。
操作函数为void z_print(Tree T )。
后序遍历：先后序遍历左子树，在后序遍历右子树，最后访问根节点。先将根节点入栈，如果该节点左孩子节点存在，将该节点左孩子节点入栈。重复执行此操作，直到节点左孩子节点为空。取栈顶元素，并赋值给P，如果P的右孩子为空或P的右孩子等于q（即如果p的右孩子已访问，则访问根节点，即p指向的节点，并用q来记录刚刚访问的节点的指针），若p有右孩子，且右孩子没有别访问过，则p=p->rchild。
操作函数为void h_print(Tree T)

3.源代码
#include<stdio.h>
#include<iostream>
#include<string>
#include<time.h>
#include <iomanip>
using namespace std;
typedef string nametype;
typedef unsigned long keytype;

typedef struct node //结点的结构体
{
keytype key;
nametype name;
int grade;
struct node *lchild,*rchild;
}bstnode;
typedef bstnode *bstree;

//栈的定义//
typedef struct{ //栈结构
bstree *base;
bstree *top;
int stacksize;
}Sqstack;

int InitStack (Sqstack &s) //建立一个空栈
{
s.base=(bstree*)malloc(1000 * sizeof(int));

s.top=s.base;
return 1;
};

int Push(Sqstack &s ,node *e)//在栈顶插入元素（进栈）
{
*s.top=e;
s.top=s.top+1;
return 1;
};

int Pop(Sqstack &s, bstree &e)//出栈
{
if(s.top==s.base)return 0;
else s.top=s.top-1;
e=*s.top;
return 1;
};
//非递归历遍并输出结点信息//
/*---------------先序非递归遍历---------------*/
void x_print(node *t)
{
Sqstack s;
InitStack(s);
bstnode *p;
p=t;
while(p||!(s.top==s.base))
{
if(p)
{
Push(s,p);
cout<<p->key<<"\t"<<setw(20);
cout<<p->name<<"\t"<<setw(20);
cout<<p->grade<<"\t"<<endl;
p=p->lchild;
}
else
{
Pop(s,p);
p=p->rchild;

}
}
}

/*---------------中序非递归遍历---------------*/
void z_print(node *t)
{
Sqstack s;
InitStack(s);
bstnode *p;
p=t;
while(p||!(s.top==s.base))
{
if(p)
{
Push(s,p);
p=p->lchild;
}
else
{
Pop(s,p);
cout<<p->key<<"\t"<<setw(20);
cout<<p->name<<"\t"<<setw(20);
cout<<p->grade<<"\t"<<endl;
p=p->rchild;

}
}
}

/*---------------非递归后序遍历---------------*/
void h_print(node *t)
{
Sqstack s;
InitStack(s);
node *p,*q;
p=t;
q=NULL;
while(p || !(s.top==s.base))
{
if(p){
Push(s,p);
p=p->lchild;
}else
{
p=*(s.top-1);
if(p->rchild==q)
{
Pop(s,q);p=NULL;
cout<<q->key<<"\t"<<setw(20);
cout<<q->name<<"\t"<<setw(20);
cout<<q->grade<<"\t"<<endl;

}else
{
p=p->rchild;q=NULL;
}
}
}
}
//递归查找二叉树//
/*---归查找，若找到就返回指向该结点的指针，否则返回空---*/
bstnode *SearchBST(bstree t,keytype key) {
if(t==NULL||key==t->key)
return t;
if(key<t->key)
return SearchBST(t->lchild ,key);
else
return SearchBST(t->rchild ,key);
}
//-------------------给定学生信息插入到二叉树中-------------------//
bstree InsertBST(bstree t,int key,nametype name,double grade)
{
bstree p,q;
if(t==NULL) //树初始为空，新建二叉树
{
t=new bstnode();
t->key=key;
t->name=name;
t->grade=grade;
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
{
cout<<endl;
cout<<"树中已有该节点:"<<key<<endl;
cout<<endl;
return t;
}
}
p=new bstnode(); //找不到结点就新建一个结点插入到二叉排序树中
p->key=key;
p->name=name;
p->grade=grade;

p->lchild=p->rchild=NULL;
if(q->key>key)
q->lchild=p;
else
q->rchild=p;
}
return t;
}
//-------------------二叉树排序树的构建-------------------//
bstree CreatTree() //不断输入学生信息以插入到二叉树中
{
bstree t=NULL;
keytype key;
nametype name;
double grade;
cout<<"请输入---学号---姓名---成绩---（输入0时结束）:"<<endl;
cin>>key;
if(key==0)
return t;
cin>>name;
cin>>grade;

while(key) //key==0时退出
{
t=InsertBST(t,key,name,grade);
cout<<"请输入---学号---姓名---成绩---（输入0时结束）:"<<endl;
cin>>key;
if(key==0)
break;
cin>>name;
cin>>grade;

}
return t;
}
//-------------------删除树中的结点-------------------//
void Delete(bstree &p) //删除结点的函数
{
bstree q,s;
if(!p->rchild)
{
q=p;
p=q->lchild ;
delete q;
}
else if(!p->lchild)
{
q=p;
p=p->rchild;
delete q;
}
else
{
q=p;
s=p->lchild;
while(s->rchild)
{
q=s;
s=s->rchild;
}
p->name=s->name;
if(q!=p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;
delete s;
}

}

void DeleteData(bstree &t,keytype key)
{
if(!t){
cout<<"没有该信息，请重新输入！";
cin>>key;
DeleteData(t,key);
}
else
{
if(t->key==key)
{
Delete(t); //若找到结点直接删除
cout<<"删除成功！"<<endl;
}
else if(t->key>key)
DeleteData(t->lchild,key); //结点数据比查找关键字大，继续在其左子树中查找
else
DeleteData(t->rchild,key); //结点数据比查找关键字小，继续在其右子树中查找
}
}
//数组和二叉排序树的查找效率比较//
void compare()
{
bstree t=NULL;
clock_t start,end,start1,end1;
int num=0;
int a=0;
int b=0;
int c=0;
int d=1;
bstree p;
string key,name;
double grade;
nametype str [100][3];
//cout<<"（输入0时结束）"<<endl;
cout<<"请输入---学号---姓名---成绩---（输入0时结束）:"<<endl;
cin>>key;
if(key=="0")
return ;
cin>>name;
cin>>grade;

while(key!="0")
{
str[num][0]=key;
str[num][1]=name;
str[num][2]=grade;
int key1=atoi(key.c_str()); //用库函数将字符串转化为关键字的int型
t=InsertBST(t,key1,name,grade); //插入结点
cout<<"请输入---学号---姓名---成绩---（输入0时结束）:"<<endl;
cin>>key;
if(key=="0")
break;
cin>>name;
cin>>grade;
num++;
}
cout<<endl;
cout<<"进行数组和二叉排序树的查询效率比较（比较：1 不比较：0）";
cin>>d;
while(d!=NULL)
{
switch(d)
{
case 0:
cout<<"返回选择界面"<<endl;
break;

case 1:
cout<<"数组查询！"<<endl;
cout<<"请输入查询的成绩："<<endl;
cin>>key;
start=clock();
while(a<=10000000) //循环模拟数组查找
{
while(b<=99)
{
if(str[b][0]==key)
{b=100;}
else
b++;
}
b=0;
a++;
}
end=clock();
if(num>=100)
cout<<"数组查询：无查询信息，花费时间: "<<end-start<<" 毫秒"<<endl;
else
cout<<"数组查询：查到信息，花费时间: "<<end-start<<" 毫秒"<<endl;
int key1=atoi(key.c_str()); //同上转化
start1=clock();
while(c<=10000000) //用循环来模拟树中查找
{
p=SearchBST(t,key1);
c++;
}
end1=clock();
if(p==NULL)
cout<<"树查询：无查询信息，花费时间: "<<end1-start1<<" 毫秒"<<endl;
else
cout<<"树查询：查到信息，花费时间: "<<end1-start1<<" 毫秒"<<endl;
a=0;
b=0;
c=0;
break;
}
cout<<"是否继续进行操作（是：1 否：0）：";
cin>>d;
}
}
//二叉树的深度
int TreeDepth(bstree t)
{
int left,right,max;
if(t!=NULL)
{
left=TreeDepth(t->lchild);
right=TreeDepth(t->rchild);
max=left>right?left:right;
return max+1;
}else
{
return 0;
}
}
//树状输出二叉树
void PrintTree(bstree t,int layer)
{
int k;
if(t==NULL)
return ;
PrintTree(t->rchild,layer+1);
for(k=0;k<layer;k++)
cout<<" ";
cout<<t->key<<"\n";
PrintTree(t->lchild,layer+1);
}

//-------------------主函数测试-------------------//
int main()
{
int d;
keytype key;
bstree t=NULL;
t=CreatTree();
d=TreeDepth(t);
cout<<"二叉排序树的树形表示如下"<<endl;
PrintTree(t,d);
char choose;
nametype name;
bstree p;
double grade;
cout<<" "<<endl;
cout<<"-----------------------------请输入你要选择的操作-------------------------------"<<endl;
cout<<" |-------------------------------------|"<<endl;
cout<<" ||-----------------------------------||"<<endl;
cout<<" || a 插入信息 ||"<<endl;
cout<<" || b 删除信息 ||"<<endl;
cout<<" || c 查询信息 ||"<<endl;
cout<<" || d 修改信息 ||"<<endl;
cout<<" || 0 退出 ||"<<endl;
cout<<" || e 对二叉排序树进行非递归遍历 ||"<<endl;
cout<<" || f 进行数组和二叉树查找效率实验||"<<endl;
cout<<" ||-----------------------------------||"<<endl;
cout<<" |-------------------------------------|"<<endl;
cout<<endl;
cout<<"需要选择的操作为：";
cin>>choose;
cout<<endl;
while(choose)
{
switch(choose)
{

case 'a':
//cout<<"输入学生信息信息（学号为0时结束）."<<endl;
cout<<"请输入---学号---姓名---成绩---（输入0时结束）:"<<endl;
cin>>key;
if(key==0) /*{
PrintTree(t,d);
break;}*/
cin>>name;
cin>>grade;

while(key)
{
t=InsertBST(t,key,name,grade);
cout<<"请输入---学号---姓名---成绩---:"<<endl;
cin>>key;
if(key==0)
break;
cin>>name;
cin>>grade;
}
break;
case 'b':
cout<<"请输入要删除信息学生的成绩："<<endl;
cin>>key;
DeleteData(t,key);
d=TreeDepth(t);
cout<<"删除结点后二叉树的树形显示如下"<<endl;
PrintTree(t,d);
break;
case 'c':
cout<<"请输入要查询的成绩："<<endl;
cin>>key;
p=SearchBST(t,key);
if(p==NULL)
cout<<"无查询的关键字："<<key<<endl;
else
cout<<"成绩"<<"\t"<<setw(20)<<"姓名"<<"\t"<<setw(20)<<"学号"<<endl;
cout<<p->key<<"\t"<<setw(20);
cout<<p->name<<"\t"<<setw(20);
cout<<p->grade<<endl;
break;
case 'd':
cout<<"请输入要修改的学号："<<endl;
cin>>key;
p=SearchBST(t,key);
if(p==NULL)
cout<<"无你所要修改的关键字："<<key<<endl;
else
{
cout<<"请输入修改的姓名：";
cin>>name;
cout<<"请输入修改的成绩：";
cin>>grade;
p->name=name;
p->grade=grade;
}
break;
case 'e':
if(!t)
cout<<"没有任何信息，请先输入信息！";
else
{
cout<<"学号"<<"\t"<<setw(20)<<"姓名"<<"\t"<<setw(20)<<"成绩"<<endl;
cout<<"------------------非递归先序遍历----------------"<<endl;
cout<<endl;
x_print(t);
cout<<"------------------非递归中序遍历-----------------"<<endl;
cout<<endl;
z_print(t);
cout<<"------------------非递归后序遍历-----------------"<<endl;
cout<<endl;
h_print(t);
}
break;
case 'f':
cout<<"***此实验为独立实验，实验数据独立于外部数据***"<<endl;
cout<<"***请重新输入相关信息***"<<endl;
compare();
break;

default:
cout<<"选择错误！";
break;
}
cout<<endl;
cout<<endl;
cout<<" "<<endl;
cout<<"-----------------------------请输入你要选择的操作-------------------------------"<<endl;
cout<<" |-------------------------------------|"<<endl;
cout<<" ||-----------------------------------||"<<endl;
cout<<" || a 插入信息 ||"<<endl;
cout<<" || b 删除信息 ||"<<endl;
cout<<" || c 查询信息 ||"<<endl;
cout<<" || d 修改信息 ||"<<endl;
cout<<" || 0 退出 ||"<<endl;
cout<<" || e 对二叉排序树进行非递归遍历 ||"<<endl;
cout<<" || f 进行数组和二叉树查找效率实验||"<<endl;
cout<<" ||-----------------------------------||"<<endl;
cout<<" |-------------------------------------|"<<endl;
cout<<endl;
cout<<"选择的操作位：";
cin>>choose;
cout<<endl;
}
return 0;
}

4.运行结果及截图
从键盘读入数据

以0作为结束标志可得二叉排序树树状表示

主菜单选择模块

需要在树种添加节点则执行操作a

需要在书中删除节点执行操作b

需要查询节点信息执行操作c

修改某一节点信息执行操作d

执行操作0退出程序执行

执行操作e对树进行先序遍历、后序遍历、中序遍历运行结果如下图

需要对树和数组的查询效率比较执行操作f

4.实验结论
栈是仅表尾进行插入和删除的线性表，栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，并同时附设指针top指示栈顶元素在顺序栈中的位置。
从数组查询和树查询的时间可得出，树的查询比数组的查询时间快得多。但是二叉树的平均查找长度和树的形态有关，当先后插入的关键字是有序树时，构造的二叉树蜕变为单边树。这时假设树的深度为n，其平均查找长度为n+1/2,这时和顺序查找相同。数组的查找效率为O(logN），而二叉排序树的查找最快的是其树的形状和折半查找的判定情况相同，其平均查找程度和log2N成正比。