如何用c语言实现二叉树的插入和查找
时间: 2023-09-22 10:07:49 浏览: 35
二叉树是一种非常重要的数据结构,它可以用来实现各种算法和应用。下面我们将介绍如何用 C 语言实现二叉树的插入和查找操作。
假设二叉树的节点结构如下:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
## 插入操作
二叉树的插入操作就是在二叉树中添加一个新的节点,使得这个节点满足二叉树的性质:左子树中所有节点的值都小于根节点的值,右子树中所有节点的值都大于根节点的值。
```c
void insert(struct TreeNode** root, int val) {
if (*root == NULL) {
*root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
(*root)->val = val;
(*root)->left = NULL;
(*root)->right = NULL;
} else if (val < (*root)->val) {
insert(&((*root)->left), val);
} else {
insert(&((*root)->right), val);
}
}
```
这里使用了二叉树的递归性质,如果当前节点为空,则在这个位置创建一个新节点;如果新插入的值小于当前节点的值,则递归地插入到左子树中;否则递归地插入到右子树中。
## 查找操作
二叉树的查找操作就是在二叉树中寻找一个节点,使得这个节点的值等于给定的值。
```c
struct TreeNode* search(struct TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
} else if (val < root->val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
```
这里同样使用了二叉树的递归性质,如果当前节点为空或者当前节点的值等于给定的值,则返回当前节点;如果给定的值小于当前节点的值,则递归地查找左子树;否则递归地查找右子树。
以上就是使用 C 语言实现二叉树的插入和查找操作的方法。可以通过下面的示例代码进行验证:
```c
int main() {
struct TreeNode* root = NULL;
insert(&root, 5);
insert(&root, 3);
insert(&root, 7);
insert(&root, 1);
insert(&root, 4);
insert(&root, 6);
insert(&root, 8);
struct TreeNode* node = search(root, 4);
if (node != NULL) {
printf("found: %d\n", node->val);
} else {
printf("not found\n");
}
return 0;
}
```
输出结果为:
```
found: 4
```