编写一个函数,在使用时间方面高效,如果给定的二叉搜索树包含给定值,则返回 1,否则返回 0。
例如,对于下面的树:
- n1(值:1,左:null,右:null)
- n2(值:2,左:n1,右:n3)
- n3(值:3,左:null,右:null)
调用 contains(&n2, 3) 应该返回 1,因为根节点为 n2 的树包含数字 3。
该函数应返回 1,但它返回 0 或根本不返回任何内容。
#include <stdlib.h>
#include <stdio.h>
typedef struct Node
{
int value;
struct Node *left;
struct Node *right;
} Node;
int contains(const Node *root, int value)
{
if (root->value == value)
return 1;
else if (value < root->value)
{
if (root->left == NULL)
return 0;
return contains(root->left, value);
}
else if (value > root->value)
{
if (root->right == NULL)
return 0;
return contains(root->left, value);
}
}
int main()
{
Node n1 = {.value=1, .left=NULL, .right=NULL};
Node n3 = {.value=3, .left=NULL, .right=NULL};
Node n2 = {.value=2, .left=&n1, .right=&n3};
printf("%d", contains(&n2, 3));
}
最佳答案
当 value > root->value
时,你不返回 root->right, value
吗?
else if (value < root->value)
{
if (root->left == NULL)
return 0;
return contains(root->left, value);
}
else if (value > root->value)
{
if (root->right == NULL)
return 0;
return contains(root->right, value); //You need to go to the right branch
}
关于c - 二叉搜索树 (BST) - 遍历搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53166724/