编写程序实现二叉排序树查找
时间: 2023-07-20 11:12:45 浏览: 62
好的,以下是二叉排序树查找的 Python 代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def searchBST(root, val):
if not root or root.val == val:
return root
elif root.val > val:
return searchBST(root.left, val)
else:
return searchBST(root.right, val)
```
其中,`TreeNode` 为二叉树的节点类,`searchBST` 函数为二叉排序树的查找函数,参数 `root` 为根节点,`val` 为需要查找的值。如果根节点为空或者等于需要查找的值,返回根节点;如果根节点的值大于需要查找的值,则在左子树中递归查找;如果根节点的值小于需要查找的值,则在右子树中递归查找。
相关问题
用C语言结构体编写程序实现二叉排序树查找
下面是一个用C语言结构体编写的二叉排序树查找程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的结构体
struct BSTNode {
int data;
struct BSTNode *left;
struct BSTNode *right;
};
// 插入节点
struct BSTNode* insert(struct BSTNode *node, int data) {
// 如果当前节点为空,创建一个新节点
if (node == NULL) {
struct BSTNode *temp = (struct BSTNode*) malloc(sizeof(struct BSTNode));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// 如果当前节点不为空,比较插入值和当前节点的值
if (data <= node->data) {
node->left = insert(node->left, data);
} else {
node->right = insert(node->right, data);
}
return node;
}
// 查找节点
struct BSTNode* search(struct BSTNode *node, int data) {
// 如果当前节点为空或者当前节点的值就是要查找的值,返回当前节点
if (node == NULL || node->data == data) {
return node;
}
// 如果要查找的值小于当前节点的值,递归查找左子树
if (data < node->data) {
return search(node->left, data);
}
// 如果要查找的值大于当前节点的值,递归查找右子树
return search(node->right, data);
}
int main() {
struct BSTNode *root = NULL;
int n, i, x;
printf("请输入节点个数:");
scanf("%d", &n);
printf("请输入节点值:");
for (i = 0; i < n; ++i) {
scanf("%d", &x);
root = insert(root, x);
}
printf("请输入要查找的值:");
scanf("%d", &x);
struct BSTNode *result = search(root, x);
if (result == NULL) {
printf("未找到该节点\n");
} else {
printf("找到该节点,值为 %d\n", result->data);
}
return 0;
}
```
程序中定义了一个`BSTNode`结构体,其中包含了节点的值、左子树指针和右子树指针。`insert`函数实现了插入节点的功能,`search`函数实现了查找节点的功能。在`main`函数中,首先输入节点个数和节点值,然后输入要查找的值,最后调用`search`函数查找节点并输出结果。
编写程序实现二叉排序树的查找c语言
以下是一个简单的二叉排序树的查找程序,C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的节点结构体
struct BSTNode {
int data; // 节点的数据
struct BSTNode *left; // 左子树指针
struct BSTNode *right; // 右子树指针
};
// 创建一个新节点
struct BSTNode *createNode(int data) {
struct BSTNode *newNode = (struct BSTNode *)malloc(sizeof(struct BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 将一个节点插入到二叉排序树中
void insertNode(struct BSTNode **root, int data) {
if (*root == NULL) {
*root = createNode(data);
return;
}
if (data < (*root)->data) {
insertNode(&((*root)->left), data);
} else if (data > (*root)->data) {
insertNode(&((*root)->right), data);
}
}
// 在二叉排序树中查找某个节点
struct BSTNode *findNode(struct BSTNode *root, int data) {
if (root == NULL) {
return NULL;
}
if (root->data == data) {
return root;
} else if (data < root->data) {
return findNode(root->left, data);
} else {
return findNode(root->right, data);
}
}
int main() {
struct BSTNode *root = NULL;
insertNode(&root, 50);
insertNode(&root, 30);
insertNode(&root, 70);
insertNode(&root, 20);
insertNode(&root, 40);
insertNode(&root, 60);
insertNode(&root, 80);
printf("Enter a value to search: ");
int value;
scanf("%d", &value);
struct BSTNode *result = findNode(root, value);
if (result == NULL) {
printf("Value not found\n");
} else {
printf("Value found: %d\n", result->data);
}
return 0;
}
```
在这个程序中,我们首先定义了一个二叉排序树的节点结构体 `BSTNode`,其中包含了节点的数据 `data`,以及左右子树的指针 `left` 和 `right`。
然后,我们实现了两个函数。`createNode` 函数用于创建一个新的节点,`insertNode` 函数用于将一个节点插入到二叉排序树中。这两个函数都是递归实现的。
最后,我们实现了 `findNode` 函数,用于在二叉排序树中查找某个节点。这个函数也是递归实现的。
在 `main` 函数中,我们首先创建了一个二叉排序树,并插入了一些节点。然后,从用户输入中读取一个值,调用 `findNode` 函数查找这个值是否在二叉排序树中存在。如果存在,就输出节点的数据;否则,输出“Value not found”。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)