c-二进制搜索树(BST)-遍历搜索

Question

编写一个函数，根据使用的时间，如果给定的二进制搜索树包含给定的值，则返回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));
}

Answer 1

当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 
}

Answer 2

在else条件下，您不会转到右分支，而是转到左分支。

else if (value > root->value)
{
if (root->right == NULL)
return 0;
return contains(root->left, value);
}

在值较大的情况下使用下面的行来修复

return contains(root->right, value);