6-7 二叉排序树查找操作 分数 6 作者 DS课程组 单位 临沂大学 本题要求实现二叉排序树的查找操作。 函数接口定义: BSTree SearchBST(BSTree T,ElemType e); 其中BSTree结构定义如下: typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *lchild,*rchild; }BSTNode,*BSTree; 裁判测试程序样例: #include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *lchild,*rchild; }BSTNode,*BSTree; BSTree CreateBST();/* 二叉排序树创建,由裁判实现,细节不表 */ BSTree SearchBST(BSTree T,ElemType e); void Inorder(BSTree T);/* 中序遍历,由裁判实现,细节不表 */ int main() { BSTree T,result; ElemType n,e; T = CreateBST(); printf("Inorder:"); Inorder(T); printf("\n"); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&e); result = SearchBST(T,e); if(result) printf("%d is found\n",result->data); else printf("%d is not found\n",e); } return 0; } /* 你的代码将被嵌在这里 */ 输入样例: 输入第一行以-1结束的整数,为二叉排序树中元素初始序列,第二行为一个整数n,代表要查询的元素个数,第三行为n个整数,代表要查询的元素值。 例如创建如下二叉排序树,输入为: 二叉排序树.png 4 3 5 1 2 7 6 8 -1 4 1 8 0 9 输出样例: Inorder: 1 2 3 4 5 6 7 8 1 is found 8 is found 0 is not found 9 is not found
时间: 2024-03-17 13:44:21 浏览: 29
下面是实现二叉排序树的查找操作的代码:
```
BSTree SearchBST(BSTree T, ElemType e) {
while (T != NULL) {
if (e == T->data) {
return T;
} else if (e < T->data) {
T = T->lchild;
} else {
T = T->rchild;
}
}
return NULL;
}
```
具体实现中,我们采用了迭代的方式进行查找操作。首先将当前节点指向根节点,然后不断比较要查找的值和当前节点的值的大小关系,根据比较结果更新当前节点的指向,直到找到该节点或者遍历到空节点为止。如果最终遍历到空节点,则表示没有找到该节点,查找失败,返回空指针。
在主函数中,我们先使用 CreateBST 函数创建了一棵二叉排序树,并对其进行了中序遍历,然后读入要查询的元素个数和具体的元素值,并依次调用 SearchBST 函数进行查找操作。如果查找成功,则输出该节点的值,否则输出“not found”。
完整代码如下:
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)