二叉搜索树查找输出

Question

我正在尝试为二叉搜索树实现查找功能。如果我查找树的根，它 return 为真，但当我查找树中的其他条目时，它 return 为假。当我调试它时，函数似乎是 return 1，但随后会继续运行，最后是 return 0。据我了解，该函数应该在 return 具有任何值后立即终止，所以我不确定为什么会这样。

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

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

Answer 2

该函数的行为不正确，因为它return在这些 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 语句的 sub-statement

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

不会执行。

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

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

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

所以控制权会在最后一个else语句里面传递

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

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

    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

你进行了递归调用，但你不是return它的结果！

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

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 是 returned，否则查找会进入左分支或右分支。当路径结束时 (x == NULL) 未找到该值，并且 0 是 returned.

结果从递归向上传播 return。

最简单的迭代版本：

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 指针向下移动树。如果在分支结束之前找到该值，则 returned 为 1。否则当扫描走过树叶时结果为 0。

二叉搜索树查找输出

Binary search tree lookup output

c

recursion

struct

binary-search-tree

function-definition