2025年数据结构大作业实验报告.pdf

该【2025年数据结构大作业实验报告 】是由【小屁孩】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【2025年数据结构大作业实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。 : .
博观而约取，厚积而薄发。——苏轼

物理与信息工程学院
数据结构实验大作业报告




专 业：计算机科学与技术
班 级：19 计算机科学与技术
学 号：
姓 名：





2020 年 12 月
: .
穷则独善其身，达则兼善天下。——《孟子》
树表的查找
一、 问题描述：
由于折半查找中要求表中记录按关键字有序排列，且不能
用链表做存储结构，因此，当表的插入或删除操作频繁时，为
维护表的有序性，需要移动表中很多记录。这种由移动记录引
起的额外时间开销，就会抵消折半查找的优点。所以，线性表
的查找更适用于静态查找表，若要对动态查找表进行高效率的
查找，可采取集中特殊的二叉树作为查找表的组织形式，在此
将它们叫做树表。
二、 设计：
二叉排序树（Binary Sort Tree）
二叉排序树的定义
1．
二叉排序树 ，又叫 二叉查找树 或二叉搜索树 。它或是一棵空树；或
是具有下列性质的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于它
的根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它
的根结点的值；
（3）它的左、右子树也分别为二叉排序树。
： : .
博学之，审问之，慎思之，明辨之，笃行之。——《礼记》
Typedef int KeyType ；
typedef struct node
{
KeyType key ; /* 关键字的值 */
struct node *lchild,*rchild;/* 左右指针 */
}BSTNode, *BSTree;

可以将树结点逐个插入到二叉排序树（一开始可以是一颗空树）中，
只要保证插入后，依然满足二叉排序树的特点， 就可以创建一个二叉
排序树。
设树结点的关键字值为 key
算法思想：
（1）若二叉排序树是空树， 则将 key 结点成为二叉排序树的根结点。
（2）若二叉排序树非空树，则将 key 与二叉排序树的根进行比较：
a. 如果 key 的值等于根结点的值，则停止插入。
b. 如果 key 的值小于根结点的值，则将 key 所在结点插入左子树。
c. 如果 key 的值大于根结点的值，则将 key 所在结点插入右子树。
算法实现：
void InsertBST(BSTree *bst, KeyType key)
/*若在二叉排序树中不存在关键字等于 key 的元素，插入该元素 */
{
BSTree s; : .
博观而约取，厚积而薄发。——苏轼
if (*bst == NULL)/* 递归结束条件 */
{
s=(BSTree)malloc(sizeof(BSTNode));/* 申请新的结点 s*/
s-> key=key;
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}
else {
if (key < (*bst)->key)
InsertBST(&((*bst)->lchild), key);/* 将 s 插入左
子树*/
else
if (key > (*bst)->key)
InsertBST(&((*bst)->rchild), key); /* 将 s 插
入右子树*/
}
}

因为二叉排序树是可以看作是一个有序表， 所以其查找过程和折半查
找类似。
算法思想： : .
士不可以不弘毅，任重而道远。仁以为己任，不亦重乎?死而后已，不亦远乎? ——《论语》
首先将待查关键字 key 与根节点关键字 t 进行比较：
a. 如果 key = t, 则返回根节点指针。
b. 如果 key < t, 则进一步查找左子树。
c. 如果 key > t, 则进一步查找右子树。
（1）递归算法实现：
/*在根指针bst 所指二叉排序树中， 递归查找某关键字等于 key 的元
素，若查找成功，返回指向该元素结点指针，否则返回空指 */
BSTree SearchBST(BSTree bst, KeyType key) {
if (!bst)
return NULL;
else
if (bst->key == key)
return bst;/ * 查找成功 * /
else {
if (bst->key > key)
return SearchBST(bst->lchild, key); /*在左
子树继续查找 */
else
return SearchBST(bst->rchild, key); /*在右
子树继续查找 */
}
} : .
臣心一片磁针石，不指南方不肯休。——文天祥
（2）非递归实现
BSTree SearchBST(BSTree bst, KeyType key)
/*在根指针 bst 所指二叉排序树 bst 上，查找关键字等于 key 的结
点，若查找成功，返回指向该元素结点指针，否则返回空指针 */
{
BSTree q;
q=bst;
while(q)
{
if (q->key == key)
return q; /* 查找成功 */
if (q->key > key)
q=q->lchild; /* 在左子树中查找 */
else
q=q->rchild; /* 在右子树中查找 */
}
return NULL; /* 查找失败 */
}

首先从二叉排序树的根节点开始查找关键字为 key 的待删除结点， 如
果树中不存在该节点则不做任何操作； 假设被删除结点为 *p（指向指
针的指针 p），其双亲结点为 *f ，Pl 和 Pr 分别表示其左子树和右子 : .
海纳百川，有容乃大；壁立千仞，无欲则刚。——林则徐
树。
（1） 如果*p 结点是叶结点。删除叶子结点不破坏整棵树的结构，只
需修改双亲结点的指针节课。 f->lchild=null;
（2） 若*p 结点只有左子树 Pl 或者只有右子树 Pr，这时直接令 Pl 或
者 Pr 为 双 亲 结 点 *f 的 左 子 树 即 可 。
f->lchild=p->lchild;f->lchild=p->rchild;
（3） 若*p 结点的左子树和右子树均不空。 删除*p 结点之前，中序遍
历该二叉树得到的序列， 令*p 的左子树为 *f 的左子树，而*p 的
右子树为*s 的右子树。
l->lchild=p->lchild;s->rchild=p->rchil;
三、测试：
试
: .
臣心一片磁针石，不指南方不肯休。——文天祥

在写 InsertBST 算法时，二叉排序树中不存在关键字等于 key 的元
素，插入该元素时，
InsertBST(&((*bst)->lchild), key);/* 将 s 插 入 左 子 树 */ ；
InsertBST(&((*bst)->rchild), key); /* 将 s 插入右子树 */做了很
多遍，改了很多次，出现没取地址等错误。
四、完成情况和作业小结：
（1）完成情况
吴沁蝈完成的函数： InsertBST() 、PreOrder()
冉朝彬完成的函数： CreateBST() 、SearchBST()
共同完成函数： DelBST() 、main()
（2）设计的经验和体会
： 我比较喜欢使用递归， 我在写 PreOrder （）
算法的时候，用了递归的方法，三条语句实现了该函数的遍历功能，
该程序主要是二叉排序树的查找， 但是我们在算法中增加了删除功能， : .
志不强者智不达，言不信者行不果。——墨翟
虽然删除的功能不是很齐全， 我们实现删除功能就是你输入查找的数
据，执行查找功能，后实现删除算法，然后输出该