写出二叉排序树的查找算法的代码。要求如下①若查找树为空,查找失败。②查找树非空,将给定值key与查找树的根结点关键码比较。③若相等,查找成功,结束查找过程,否则,a.当给key小于根结点关键码,查找将在以左子女为根的子树上继续进行,转①b.当给key大于根结点关键码,查找将在以右子女为根的子树上继续进行,转①
时间: 2023-12-06 08:05:45 浏览: 55
好的,下面是二叉排序树的查找算法的代码实现,符合你的要求:
```python
def search_bst(root, key):
if not root: # 若查找树为空,查找失败
return None
if key == root.val: # 若相等,查找成功,结束查找过程
return root
elif key < root.val: # 当给key小于根结点关键码,查找将在以左子女为根的子树上继续进行
return search_bst(root.left, key)
else: # 当给key大于根结点关键码,查找将在以右子女为根的子树上继续进行
return search_bst(root.right, key)
```
其中,`root`表示二叉排序树的根节点,`key`表示要查找的关键字。如果查找成功,则返回对应的节点;如果查找失败,则返回`None`。
相关问题
写出二叉排序树的查找算法的代码。要求如下①若查找树为空,查找失败。②查找树非空,将给定值key与查找树的根结点关键码比较。③若相等,查找成功,结束查找过程,否则,a.当给key小于根结点关键码,查找将在以左子女为根的子树上继续进行,转①b.当给key大于根结点关键码,查找将在以右子女为根的子树上继续进行,转①,写出主函数
以下是二叉排序树查找算法的代码实现,包括了主函数:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的数据结构
typedef struct BSTNode {
int key; // 关键字
struct BSTNode *left; // 左子节点
struct BSTNode *right; // 右子节点
} BSTNode, *BSTree;
// 二叉排序树查找算法
BSTNode* BST_Search(BSTree tree, int key) {
if (tree == NULL) { // 查找树为空,查找失败
return NULL;
} else if (key == tree->key) { // 查找成功,返回当前节点
return tree;
} else if (key < tree->key) { // 在左子树中查找
return BST_Search(tree->left, key);
} else { // 在右子树中查找
return BST_Search(tree->right, key);
}
}
// 插入节点到二叉排序树中
void BST_Insert(BSTree *tree, int key) {
if (*tree == NULL) { // 如果树为空,插入新节点
*tree = (BSTree) malloc(sizeof(BSTNode));
(*tree)->key = key;
(*tree)->left = NULL;
(*tree)->right = NULL;
} else if (key < (*tree)->key) { // 在左子树中插入节点
BST_Insert(&((*tree)->left), key);
} else if (key > (*tree)->key) { // 在右子树中插入节点
BST_Insert(&((*tree)->right), key);
} else { // 关键字已经存在,不进行任何操作
return;
}
}
int main() {
BSTree tree = NULL;
int keys[] = {5, 3, 7, 1, 4, 6, 8, 2, 9}; // 待插入的关键字
int n = sizeof(keys) / sizeof(int);
// 插入关键字到二叉排序树中
for (int i = 0; i < n; i++) {
BST_Insert(&tree, keys[i]);
}
// 查找关键字
int key = 6;
BSTNode *node = BST_Search(tree, key);
if (node == NULL) {
printf("Key %d not found in the tree.\n", key);
} else {
printf("Key %d found in the tree.\n", key);
}
return 0;
}
```
在主函数中,我们首先声明一个空的二叉排序树 `tree`,然后将待插入的关键字 `{5, 3, 7, 1, 4, 6, 8, 2, 9}` 依次插入到二叉排序树中。之后,我们使用关键字 `6` 来查找二叉排序树中是否存在该关键字,如果存在则输出 `"Key 6 found in the tree."`,否则输出 `"Key 6 not found in the tree."`。