数据结构大作业实验报告.pdfVIP

数据结构大作业实验报告--第1页

物理与信息工程学院

数据结构实验大作业报告

专业：计算机科学与技术

班级：19计算机科学与技术

学号：

姓名：

2020年12月

数据结构大作业实验报告--第1页

数据结构大作业实验报告--第2页

树表的查找

一、问题描述：

由于折半查找中要求表中记录按关键字有序排列，且不能

用链表做存储结构，因此，当表的插入或删除操作频繁时，为

维护表的有序性，需要移动表中很多记录。这种由移动记录引

起的额外时间开销，就会抵消折半查找的优点。所以，线性表

的查找更适用于静态查找表，若要对动态查找表进行高效率的

查找，可采取集中特殊的二叉树作为查找表的组织形式，在此

将它们叫做树表。

二、设计：

二叉排序树（BinarySortTree）

1．二叉排序树的定义

二叉排序树，又叫二叉查找树或二叉有哪些信誉好的足球投注网站树。它或是一棵空树；或

是具有下列性质的二叉树：

（1）若它的左子树不空，则左子树上所有结点的值均小于它

的根结点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于它

的根结点的值；

（3）它的左、右子树也分别为二叉排序树。

2.二叉链表存储表示算法实现如下：

数据结构大作业实验报告--第2页

数据结构大作业实验报告--第3页

TypedefintKeyType；

typedefstructnode

{

KeyTypekey;/*关键字的值*/

structnode*lchild,*rchild;/*左右指针*/

}BSTNode,*BSTree;

3.二叉排序树的创建

可以将树结点逐个插入到二叉排序树（一开始可以是一颗空树）中，

只要保证插入后，依然满足二叉排序树的特点，就可以创建一个二叉

排序树。

设树结点的关键字值为key

算法思想：

（1）若二叉排序树是空树，则将key结点成为二叉排序树的根结点。

（2）若二叉排序树非空树，则将key与二叉排序树的根进行比较：

a.如果key的值等于根结点的值，则停止插入。

b.如果key的值小于根结点的值，则将key所在结点插入左子树。

c.如果key的值大于根结点的值，则将key所在结点插入右子树。

算法实现：

voidInsertBST(BSTree*bst,KeyTypekey)

/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/

{

BSTrees;

数据结构大作业实验报告--第3页

数据结构大作业实验报告--第4页

if(*bst==NULL)/*递归结束条件*/

{

s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/

s-key=key;

s-lchild=NULL;