编写查找二叉树结点的函数。
时间: 2024-05-13 15:18:31 浏览: 25
下面是查找二叉树结点的函数的 C++ 代码实现:
```cpp
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) {
return root;
}
if (val < root->val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
```
该函数的参数包括二叉树的根节点指针 `root` 和需要查找的目标值 `val`。在函数内部,首先判断当前节点是否为空或者当前节点的值是否等于目标值,如果是,则直接返回当前节点指针;如果不是,则根据目标值的大小关系,递归搜索左子树或右子树。如果最终没有找到目标节点,则返回 `NULL`。
相关问题
数据结构c语言实现编写查找二叉树结点的函数。编写查找二叉树结点的函数。
以下是在C语言中实现查找二叉树结点的函数的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 查找二叉树结点的函数
TreeNode* searchBST(TreeNode* root, int val) {
// 如果当前节点为空,说明没有找到,返回NULL
if (root == NULL) {
return NULL;
}
// 如果当前节点的值等于要查找的值,返回当前节点
if (root->val == val) {
return root;
}
// 如果当前节点的值大于要查找的值,递归查找左子树
if (root->val > val) {
return searchBST(root->left, val);
}
// 如果当前节点的值小于要查找的值,递归查找右子树
if (root->val < val) {
return searchBST(root->right, val);
}
return NULL;
}
int main() {
// 构造一个二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 4;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 1;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 3;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 7;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 6;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 9;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 调用查找函数查找值为3的节点
TreeNode* res = searchBST(root, 3);
if (res != NULL) {
printf("找到值为%d的节点\n", res->val);
} else {
printf("没找到\n");
}
return 0;
}
```
此代码中,我们首先定义了一个二叉树结构体,并在`searchBST`函数中使用递归的方式进行二叉树的查找,如果当前节点为空,说明没有找到,返回`NULL`;如果当前节点的值等于要查找的值,返回当前节点;如果当前节点的值大于要查找的值,递归查找左子树;如果当前节点的值小于要查找的值,递归查找右子树。最后在`main`函数中构造一个二叉树,并调用查找函数查找值为3的节点。
c语言编写二叉树接口函数
以下是一个简单的二叉树结构定义及基本接口函数的示例:
```c
// 二叉树结点定义
typedef struct TreeNode {
int val; // 结点值
struct TreeNode* left; // 左子树指针
struct TreeNode* right; // 右子树指针
} TreeNode;
// 创建一个新结点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入结点
void insertNode(TreeNode** root, int val) {
if (*root == NULL) {
*root = createNode(val);
} else if (val < (*root)->val) {
insertNode(&(*root)->left, val);
} else {
insertNode(&(*root)->right, val);
}
}
// 查找结点
TreeNode* searchNode(TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
} else if (val < root->val) {
return searchNode(root->left, val);
} else {
return searchNode(root->right, val);
}
}
// 删除结点
TreeNode* deleteNode(TreeNode* root, int val) {
if (root == NULL) {
return root;
} else if (val < root->val) {
root->left = deleteNode(root->left, val);
} else if (val > root->val) {
root->right = deleteNode(root->right, val);
} else {
if (root->left == NULL) {
TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
free(root);
return temp;
}
TreeNode* temp = findMinNode(root->right);
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
return root;
}
// 查找最小值结点
TreeNode* findMinNode(TreeNode* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
```
这里给出了二叉树的基本操作:创建结点、插入结点、查找结点、删除结点、查找最小值结点。这些函数可以组合使用来实现更复杂的操作,如遍历、查找最大值结点等。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)