1


我正在尝试使用递归函数使用二叉树（不，它不是二叉搜索树，只是二叉树）来制作搜索方法。如果数据在二叉树上，我希望它返回节点，如果不是，我希望它返回一个NULL值。我已经制作了搜索功能，并且它完美地完成了它的工作。但问题是，该函数似乎不会返回节点。

这是struct二叉树的：

struct data
{
    int number;
    struct data *left, *right;
}*root = NULL;

这是我正在谈论的搜索功能：

data* search(struct data *node, int key)
{
    if(node == NULL)
        return NULL;
    else
    {
        printf("\n%d %d -", node->number, key);

        if(node->number== key)
            return node;

        search(node->left, key);
        search(node->right, key);
    }
}

当我像这样调用搜索函数时：search(root, 6);它表示它正在返回一个NULL值，尽管我已经将一个6数字推入二叉树（并且搜索函数return node;也停在该行，所以我假设该函数是返回一个NULL。）

我在这里看到了二叉树的教程 ，使用并更改了一些代码，但它仍然是一样的。我在这里拼命寻求帮助:(

4

4 回答 4

4

您的函数将始终返回NULL，除非顶部节点包含键。您的函数不会对其递归调用的结果做任何事情；事实上，控制流可能会在没有命中return语句的情况下“掉线”。

您应该检查递归调用的返回值，并在适当的时候传递它们：

if (node == NULL)
    return NULL;
else if (node->number == key)
    return node;
else {
    data *left = search(node->left, key);
    return left? left: search(node->right, key);
}

注意“三元运算符”（if-then-else 表达式）?:。

于 2012-05-15T13:58:31.940 回答
1

除非您使用您的返回值，否则它不会返回搜索到的节点search

把它改成这样。

data* search(struct data *node, int key)
{
  if(node == NULL)
    return NULL;
  else
  {
    printf("\n%d %d -", node->number, key);

    if(node->number== key)
        return node;
    struct data *tmp;
    tmp = search(node->left, key);
    /* node found ? */
    if (tmp)
        return tmp;
    tmp = search(node->right, key);
    /* node found ? */
    if (tmp)
        return tmp;
  }
  /* search didn't find anything */
  return NULL;
}
于 2012-05-15T13:59:35.327 回答
1

您永远不会真正返回递归调用搜索的结果。

您需要检查这些调用的返回值，如果他们找到了节点，则返回它

data* search(struct data *node, int key)
{
    data* found = NULL;

    if(node == NULL)
        return NULL;

    printf("\n%d %d -", node->number, key);

    if(node->number== key)
        return node;

    found = search(node->left, key);
    if (found)
        return found;

    found = search(node->right, key);
    if (found)
       return found;

    return NULL;
}
于 2012-05-15T14:00:26.587 回答
0

有一种更简单、更有效的方法来制作二叉树，那就是简单地使用向量/数组。

i 是访问您的向量的 int 。向右走，i=i*2。向左走，i=i*2+1。他们永远不会共享同一个地点，并假设每个地点的分配均等。

于 2012-05-15T14:08:07.317 回答