数据结构大作业实验报告
- 格式：docx
- 大小：96.07 KB
- 文档页数：9
物理与信息工程学院
数据结构实验大作业报告
专 业：计算机科学与技术
班 级：19计算机科学与技术
学 号：
姓 名：
2020 年 12 月 树表的查找
一、 问题描述：
由于折半查找中要求表中记录按关键字有序排列，且不能用链表做存储结构，因此，当表的插入或删除操作频繁时，为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消折半查找的优点。所以，线性表的查找更适用于静态查找表，若要对动态查找表进行高效率的查找，可采取集中特殊的二叉树作为查找表的组织形式，在此将它们叫做树表。
二、 设计：
二叉排序树（Binary Sort Tree）
1． 二叉排序树的定义
二叉排序树，又叫二叉查找树或二叉搜索树。它或是一棵空树；或是具有下列性质的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）它的左、右子树也分别为二叉排序树。
2.二叉链表存储表示算法实现如下： Typedef int KeyType；
typedef struct node
{
KeyType key ; /*关键字的值*/
struct node *lchild,*rchild;/*左右指针*/
}BSTNode, *BSTree;
3.二叉排序树的创建
可以将树结点逐个插入到二叉排序树（一开始可以是一颗空树）中，只要保证插入后，依然满足二叉排序树的特点，就可以创建一个二叉排序树。
设树结点的关键字值为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插入右子树*/
}
}
4.二叉排序树的查找
因为二叉排序树是可以看作是一个有序表，所以其查找过程和折半查找类似。
算法思想： 首先将待查关键字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; /*查找失败*/
}
5.二叉排序树的删除
首先从二叉排序树的根节点开始查找关键字为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）设计的经验和体会
1.吴沁蝈的感受体会：我比较喜欢使用递归，我在写PreOrder（）算法的时候，用了递归的方法，三条语句实现了该函数的遍历功能，该程序主要是二叉排序树的查找，但是我们在算法中增加了删除功能，虽然删除的功能不是很齐全，我们实现删除功能就是你输入查找的数据，执行查找功能，后实现删除算法，然后输出该二叉排序树的先序序列。但是程序中有很多不足的地方，我们会在以后的时间进行改进。做完这次程序给我最大的感受就是团队合作的重要性，一个程序一个人虽然可能写得完，但是两个人的话往往更能解决其中所遇到的问题。
2．冉朝彬的感受体会：通过本次作业，我充分认识到了自己的不足之处，很多知识点不够清晰，条理不顺。遇到某些问题时，没有头任何绪，感受到了自己的无能为力，大多数时候都是靠队友的帮助。在做完本次程序后，也明白了原来一些知识点还能这样理解，处理。一些平时不明白的知识盲点，也慢慢变得顺畅了。以前走入的误区也减少了许多。最后，很感谢我的队友在此次大作业过程中对我的帮助，将一些我不明白、不清楚的知识为我解释清楚，使我对于以前的知识有了很大的巩固和提升。
