数据结构实验报告
一． 题目要求
1） 编程实现二叉排序树，包括生成、插入，删除；
2） 对二叉排序树进行先根、中根、和后根非递归遍历；
3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?
二． 解决方案
对于前三个题目要求，我们用一个程序实现代码如下
#include<windows.h>
#include <stdio.h>
#include <malloc.h>
#include "Stack.h" //栈的头文件，没有用上
typedef int ElemType; //数据类型
typedef int Status; //返回值类型
//定义二叉树结构
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lChild, *rChild;//左右子树域
}BiTNode, *BiTree;
int InsertBST(BiTree &T,int key){//插入二叉树函数
if(T==NULL)
{
T = (BiTree)malloc(sizeof(BiTNode));
T->data=key;
T->lChild=T->rChild=NULL;
return 1;
}
else if(key<T->data){
InsertBST(T->lChild,key);
}
else if(key>T->data){
InsertBST(T->rChild,key);
}
else
return 0;
}
BiTree CreateBST(int a[],int n){//创建二叉树函数
BiTree bst=NULL;
int i=0;
while(i<n){
InsertBST(bst,a[i]);
i++;
}
return bst;
}
int Delete(BiTree &T)
{
BiTree q,s;
if(!(T)->rChild){ //右子树为空 重接它的左子树
q=T;
T=(T)->lChild;
free(q);
}else{
if(!(T)->lChild){ //若左子树空 则重新接它的右子树
q=T;
T=(T)->rChild;
}else{
q=T;
s=(T)->lChild;
while(s->rChild){
q=s; s=s->rChild;
}
(T)->data=s->data; //s指向被删除结点的前驱
if(q!=T)
q->rChild=s->lChild;
else
q->lChild=s->lChild;
free(s);
}
}
return 1;
}
//删除函数，在T中 删除key元素
int DeleteBST(BiTree &T,int key){
if(!T) return 0;
else{
if(key==(T)->data) return Delete(T);
else{
if(key<(T)->data)
return DeleteBST(T->lChild,key);
else
return DeleteBST(T->rChild,key);
}
}
}
int PosttreeDepth(BiTree T){//求深度
int hr,hl,max;
if(!T==NULL){
hl=PosttreeDepth(T->lChild);
hr=PosttreeDepth(T->rChild);
max=hl>hr?hl:hr;
return max+1;
}
else
return 0;
}
void printtree(BiTree T,int nlayer){//打印二叉树
if(T==NULL) return ;
printtree(T->rChild,nlayer+1);
for(int i=0;i<nlayer;i++){
printf(" ");
}
printf("%d\n",T->data);
printtree(T->lChild,nlayer+1);
}
void PreOrderNoRec(BiTree root)//先序非递归遍历
{
BiTree p=root;
BiTree stack[50];
int num=0;
while(NULL!=p||num>0)
{
while(NULL!=p)
{
printf("%d ",p->data);
stack[num++]=p;
p=p->lChild;
}
num--;
p=stack[num];
p=p->rChild;
}
printf("\n");
}
void InOrderNoRec(BiTree root)//中序非递归遍历
{
BiTree p=root;
int num=0;
BiTree stack[50];
while(NULL!=p||num>0)
{
while(NULL!=p)
{
stack[num++]=p;
p=p->lChild;
}
num--;
p=stack[num];
printf("%d ",p->data);
p=p->rChild;
}
printf("\n");
}
void PostOrderNoRec(BiTree root)//后序非递归遍历
{
BiTree p=root;
BiTree stack[50];
int num=0;
BiTree have_visited=NULL;
while(NULL!=p||num>0)
{
while(NULL!=p)
{
stack[num++]=p;
p=p->lChild;
}
p=stack[num-1];
if(NULL==p->rChild||have_visited==p->rChild)
{
printf("%d ",p->data);
num--;
have_visited=p;
p=NULL;
}
else
{
p=p->rChild;
}
}
printf("\n");
}
int main(){//主函数
printf(" ---------------------二叉排序树的实现-------------------");
printf("\n");
int layer;
int i;
int num;
printf("输入节点个数:");
scanf("%d",&num);
printf("依次输入这些整数（要不相等）");
int *arr=(int*)malloc(num*sizeof(int));
for(i=0;i<num;i++){
scanf("%d",arr+i);
}
BiTree bst=CreateBST(arr,num);
printf("\n");
printf("二叉树创建成功!");
printf("\n");
layer=PosttreeDepth(bst);
printf("树状图为:\n");
printtree(bst,layer);
int j;
int T;
int K;
for(;;){
loop:
printf("\n");
printf(" ***********************按提示输入操作符************************:");
printf("\n");
printf(" 1:插入节点 2:删除节点 3:打印二叉树 4:非递归遍历二叉树 5:退出");
scanf("%d",&j);
switch(j){
case 1:
printf("输入要插入的节点:");
scanf("%d",&T);
InsertBST(bst,T);
printf("插入成功!");
printf("树状图为:\n");
printtree(bst,layer);
break;
case 2:
printf("输入要删除的节点");
scanf("%d",&K);
DeleteBST(bst,K);
printf("删除成功!");
printf("树状图为:\n");
printtree(bst,layer);
break;
case 3:
layer=PosttreeDepth(bst);
printtree(bst,layer);
break;
case 4:
printf("非递归遍历二叉树");
printf("先序遍历:\n");
PreOrderNoRec(bst);
printf("中序遍历:\n");
InOrderNoRec(bst);
printf("后序遍历:\n");
PostOrderNoRec(bst);
printf("树状图为:\n");
printtree(bst,layer);
break;
case 5:
printf("程序执行完毕!");
return 0;
}
goto loop;
}
return 0;
}
对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为
typedef int ElemType; //数据类型
typedef string SlemType;
typedef int Status; //返回值类型
//定义二叉树结构
typedef struct BiTNode{
SlemType name;
ElemType score;
ElemType no; //数据域
struct BiTNode *lChild, *rChild;//左右子树域
}BiTNode, *BiTree;
参数不是key,而是另外三个
int InsertBST(BiTree &T,int no,int score,string name){//插入二叉树函数
if(T==NULL)
{
T = (BiTree)malloc(sizeof(BiTNode));
T->no=no;T->name=name;T->score=score;
T->lChild=T->rChild=NULL;
return 1;
}
else if(no<T->no){
InsertBST(T->lChild,no,score,name);
}
else if(key>T->data){
InsertBST(T->rChild, no,score,name);
}
else
return 0;
}
其他含参函数也类似
即可完成50个信息存储
用数组存储50个信息，查看以往代码
#include<iostream>
#include<string>
using namespace std;
class student{
private:
int num;
string name;
int ob1;
int ob2;
int ara;
public:
void set(int a,string b,int c,int d);
void show();
int average();
};
void student ::set(int a,string b,int c,int d){
num=a;
name=b;
ob1=c;
ob2=d;
ara=(c+d)/2;
}
void student::show(){
cout<<"学号："<<num<<" 姓名："<<name<<" 科目一："<<ob1<<" 科目二："<<ob2<<" 平均成绩："<<ara<<endl;}
int student::average(){
return ara;}
int main(){
cout<<" 欢迎来到学生管理系统"<<endl;
cout<<" 0.查询学号信息："<<endl;
cout<<" 1.删除学号信息："<<endl;
cout<<" 2.添加学号新信息"<<endl;
cout<<" 3.按平均分降序显示所有学生信息"<<endl;
cout<<" 4. 退出"<<endl;
student *ptr=new student[21];
ptr[1].set(1,"小明",88,67);//已存入的学生信息
ptr[2].set(2,"小李",68,82);
ptr[3].set(3,"小王",68,62);
ptr[4].set(4,"小陈",79,82);
ptr[5].set(5,"小张",63,82);
ptr[6].set(6,"小红",68,73);
ptr[7].set(7,"小木",62,77);
ptr[8].set(8,"小添",65,86);
ptr[9].set(9,"小天",68,82);
ptr[10].set(10,"张三",88,82);
ptr[11].set(11,"李四",98,82);
ptr[12].set(12,"王五",88,81);
ptr[13].set(13,"小月",58,82);
ptr[14].set(14,"小鑫",78,80);
ptr[15].set(15,"小良",68,92);
ptr[16].set(16,"小成",68,82);
ptr[17].set(17,"小敏",98,92);
ptr[18].set(18,"小问",88,88);
ptr[19].set(19,"小文",48,82);
ptr[20].set(20,"小瑞",98,62);//已存入的学生信息
int numlock;
int j=0;
int i,k,m;
int q,e,r;
string w;
while(1){
cout<<" 按0,1,2,3,4进行操作"<<endl;
cin>>numlock;
switch(numlock){
case 0:
cout<<"输入想查询的学号"<<endl;
cin>>i;
if(i==j){
cout<<"该学号信息已被删除"<<endl;
break;}
ptr[i].show();
break;
case 1:
cout<<"输入想删除的学号"<<endl;
cin>>j;
delete[j]ptr;
cout<<"删除成功"<<endl;
break;
case 2:
cout<<"输入想添加的学号信息"<<endl;
cin>>k;
if(k!=j){
cout<<"该学号信息已经存在，添加失败"<<endl;
break;
}
cout<<"重新输入添加的学号"<<endl;
cin>>q;
cout<<"输入姓名"<<endl;
cin>>w;
cout<<"输入科目一的成绩"<<endl;
cin>>e;
cout<<"输入科目二的成绩"<<endl;
cin>>r;
ptr[k].set(q,w,e,r);
break;
case 3:
for( m=1;m<20;m++){
for(int n=m+1;n<20;n++){
if(ptr[m].average()<ptr[n].average()){
student a;
a=ptr[m];
ptr[m]=ptr[n];
ptr[n]=a;
}}
ptr[m].show();
}
break;
case 4:
cout<<"谢谢使用"<<endl;
return 0;
default:
cout<<"number out of 0 to 4"<<endl;
break;
}}
return 0;
}
三． 测试结果
二叉排序树储存数据界面（储存学生信息略）
创建二叉树：
插入节点：
删除节点：
非递归遍历：
退出：
数组储存学生信息界面
分析查找效率：
因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。
四． 总结与改进
这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。
一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。
递归遍历的实现比非递归的遍历真的简单很多。
开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。