二叉搜索树查找的输出结果

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

- Max

---

当你进行递归调用时，你返回什么？ - Some programmer dude

你可能想要写成 return (lookup(n,x->right)); 而不是仅仅写 lookup(n,x->right);。 - Stef

抱歉，@Stef。我在打字时没有看到你的评论。结果证明是相同的，但我实际上并没有复制你的输入。请随意给出您自己的解释性答案，我们可以比赛争取赞数。;-) - Yunnosch

我想我现在明白了。所以“return 1”退出了lookup的递归调用，但由于我没有返回它，第一次调用仍然到达“return 0”？非常有帮助，谢谢。 - Max

sb2346 请稍等一下，等待Stefs可能即将到来的答案，然后再决定接受哪一个。他值得一点耐心。 - Yunnosch

嗨@Yunnosch，不要介意，我没有打算写一个答案。 - Stef

Answer 1

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

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

- Yunnosch

---

如果Stef在这里也有一个解释清楚的答案，请给那个点赞。 - Yunnosch

我已经做了 - 我喜欢你的方式。如果还需要，随意提出。不过我更希望你能在评论中提出更多的建议。 - Yunnosch

Answer 2

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

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

控制权将在if-else语句后传递到最后一个return语句。

    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 );

- Vlad from Moscow

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。

- CiaPan