二叉树查找是否存在值为x的结点
时间: 2023-06-10 19:04:00 浏览: 59
二叉树查找是否存在值为x的结点的方法是先判断根节点是否为x,如果是,则返回True。如果不是,则分别在左子树和右子树中寻找是否有值为x的节点。如果左子树中找到,则返回True,否则在右子树中寻找。如果右子树中找到,则返回True,否则返回False。
相关问题
写出C语言代码在二叉树查找是否存在值为x的结点
当然,我可以为你提供代码。请看下面:
```
#include <stdio.h>
#include <stdlib.h>
struct node
{
int key;
struct node *left, *right;
};
// 创建新节点并返回
struct node* newNode(int item)
{
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// 二叉树查找
struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
// 插入节点
struct node* insert(struct node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
// 打印中序遍历结果
void inorder(struct node* root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
// 主程序
int main()
{
struct node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("中序遍历结果:\n");
inorder(root);
printf("\n");
int x = 40;
struct node* result = search(root, x);
if(result)
{
printf("%d存在于二叉树中\n", x);
}
else
{
printf("%d不在二叉树中\n", x);
}
return 0;
}
```
这个代码基本上是一个二叉查找树的模板,它能够插入节点、进行中序遍历、查找特定节点。你可以将其中的节点值改为自己想要查找的值,修改一下就可以使用了。
二叉树查找值为x的结点
你好,很高兴为你解答这个问题。二叉树查找值为x的节点,可以采用递归或者非递归的方式进行实现。具体的实现方法可以参考以下代码:
递归实现:
```
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL || root->val == val) return root;
return (val < root->val) ? searchBST(root->left, val) : searchBST(root->right, val);
}
```
非递归实现:
```
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* searchBST(TreeNode* root, int val) {
while (root != NULL && root->val != val) {
root = (val < root->val) ? root->left : root->right;
}
return root;
}
```
希望这个回答能对你有所帮助。如果你还有其他问题,可以继续问我。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)