0

我对这个逻辑有问题。如何搜索整个树（因为我不能依赖任何订单搜索）并且只返回一个匹配值（如果存在）？如果我返回递归调用，一旦它到达第一片叶子并且没有找到匹配项，它会不会失败？

使用下面的函数时，会进行调用，直到找到匹配项或到达树的末尾，并且无论匹配项如何，都会返回最左侧的节点。

我的递归函数，按顺序遍历：

tnode *find(tnode *ptr, const char *str)
{
    if (ptr == NULL) return ;

    if(strcmp (str,ptr->str) == 0)
        return ptr;


    else 
    {
        //search left subtree
        if (ptr->left != NULL)
            find(ptr->left, str) ;


        // search right subtree
        if (ptr->right != NULL)
            find(ptr->right, str) ;
    }

   return;

}
4

2 回答 2

2

首先：

if (ptr == NULL) return ;

您应该根据函数原型（tnode *find(tnode *ptr, const char *str)）返回一个值。

第二：

find(ptr->right, str);

您不使用返回值，因此无论如何结果都会不正确。

第三：

return;

和第一个一样。

如果你能解决所有问题，它应该可以工作。

BTWif (ptr->left != NULL)不是必需的，因为您ptr == 0在函数的开头进行检查。

最后一个请注意编译器警告。

于 2013-04-22T14:24:32.790 回答
1

如果左子树查找返回非 NULL，则您有一个匹配项并且应该返回它。目前，您甚至都不看它是否找到任何东西。

如果它没有找到任何东西，你可以返回右子树查找的结果（如果它是 NULL，你到处找，没有找到任何东西）。

tnode *find(tnode *ptr, const char *str)
{
    ptr *found;

    if (ptr == NULL) return NULL; /* nothing to see here */

    if(strcmp (str,ptr->str) == 0)
        return ptr; /* it is here! */

    /* try left subtree */
    found = find(ptr->left, str);
    if (found) return found; /* it was on the left */

    /* try right subtree */
    return find(ptr->right, str);
}
于 2013-04-22T14:23:27.263 回答