c语言 - 二叉搜索树查找输出

Question

我正在尝试为二叉搜索树实现查找功能。虽然如果我查找树的根，它确实返回 true，但当我查找树中的其他条目时，它会返回 false。当我调试它时，该函数似乎返回 1，但随后会继续运行，然后在最后返回 0。我的理解是，该函数应在返回任何值后立即终止，所以我不确定为什么会发生这种情况。

int lookup(int n,struct node* x)
{
if (x->data==n)
{
return 1;
}
else if (x->left==NULL && x->right==NULL)
{
return 0;
}
else if (n>x->data && x->right!=NULL)
{
lookup(n,x->right);
}
else
{
lookup(n,x->left);
}
return 0;
}

Answer 1

递归lookup调用返回的值(即lookup(n,x->right);和lookup(n,x->left);) 被忽略，即使它是正确的.
这是因为在函数结束时(即从其中一个调用返回后)，您无条件地return 0;。

用return lookup(n,x->XXX);替换lookup(n,x->XXX);是您想要做的。

Answer 2

该函数的行为不正确，因为它在这些 if 语句中不返回任何内容

else if (n>x->data && x->right!=NULL)
{
lookup(n,x->right);
}
else
{
lookup(n,x->left);
}

也就是说，控制权将传递给 if-else 语句之后的最后一个返回语句

return 0;

但是，如果您要像更新功能一样

int lookup(int n,struct node* x)
{
if (x->data==n)
{
return 1;
}
else if (x->left==NULL && x->right==NULL)
{
return 0;
}
else if (n>x->data && x->right!=NULL)
{
return lookup(n,x->right);
}
else
{
return lookup(n,x->left);
}
return 0;
}

尽管如此，该函数可以调用未定义的行为，因为它不检查指针x是否等于NULL。

例如，假设x->data不等于n，n小于x->data。另外，我们假设x->left等于NULL，x->right不等于NULL。

在这种情况下，第一个 if 语句的子语句

if (x->data==n)
{
return 1;
}

不会被执行。

而第二个if语句的子语句也不会执行，因为x->right不等于NULL。

else if (x->left==NULL && x->right==NULL)
{
return 0;
}

第三个 if 语句也存在同样的问题。

所以控件将在最后一个 else 语句中传递

else
{
lookup(n,x->left);
}

其中，使用空指针x->left调用函数。因此，在函数的第二次调用中，您将尝试使用空指针访问内存

if (x->data==n)
{
return 1;
}

可以按以下方式编写该函数。请注意，由于函数不会更改树本身，因此其第二个参数应使用限定符const声明。

int lookup( int n, const struct node *x )
{
if ( x == NULL )
{
return 0;
}
else if ( n < x->data )
{
return( n, x->left );
}
else if ( x->data < n )
{
return ( n, x->right );
}
else
{
return 1;
}
}

此外，通常使用第一个参数声明这样的函数，该参数指定指向节点(指向树)的指针，第二个参数指定要搜索的内容。那就像

int lookup( const struct node *x, int n );

甚至喜欢

_Bool lookup( const struct node *x, int n );

Answer 3

你做了一个递归调用，但你没有返回它的结果！

代码的最简单递归版本是：

int lookup(int n, struct node* x)
{
if (x == NULL)
return 0;
if (n == x->data)
return 1;
if (n < x->data)
return lookup(n, x->left);
else
return lookup(n, x->right);
}

只要它没有离开分支，它就会测试当前节点 - 当找到值时，返回 1，否则查找将潜入左分支或右分支。当路径结束(x == NULL)时，找不到值，返回0。

结果在从递归返回时向上传播。

最简单的迭代版本：

int lookup(int n, struct node* x)
{
while (x != NULL)
{
if (n == x->data)
return 1;
if (n < x->data)
x = x->left;
else
x = x->right;
}
return 0;
}

它的工作方式与递归类似，只是它不会深入递归，只是将x指针向下移动。如果在分支结束之前找到该值，则返回 1。否则，当扫描经过树叶时，结果为 0。