内容发布更新时间 : 2025/1/11 9:26:32星期一 下面是文章的全部内容请认真阅读。

数据结构实验报告

一． 题目要求

1） 编程实现二叉排序树，包括生成、插入，删除； 2） 对二叉排序树进行先根、中根、和后根非递归遍历；

3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?

二． 解决方案

对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include

#include \ //栈的头文件，没有用上 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(keydata){

InsertBST(T->lChild,key); }

BiTree CreateBST(int a[],int n){//创建二叉树函数 BiTree bst=NULL;

int i=0; while(i

InsertBST(bst,a[i]); i++; }

else if(key>T->data){ } else

return 0;

InsertBST(T->rChild,key);

资料

}

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){ }

(T)->data=s->data; //s指向被删除结点的前驱 if(q!=T)

q->rChild=s->lChild; q=s; s=s->rChild;

资料