C:二叉树搜索方法

Question

我正在尝试使用递归函数使用二叉树(不，它不是二叉树，只是二叉树)来创建一种搜索方法。如果数据在二叉树上，我希望它返回节点，如果不在二叉树上，我希望它返回一个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)。

我在here中看过二叉树的教程，使用并修改了其中的一些代码，但它仍然是一样的。我正拼命地在这里寻求帮助：

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

Answer 2

实际上，您永远不会从搜索的递归调用中返回结果。

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

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

Answer 3

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

I是访问你的向量的整数。向右转，i=i*2。向左转，i=i*2+1。它们永远不会共享同一个点，假设每个点都是均匀分布的。