搜索二叉树的一些最佳实践是什么？

Question

我正在学习 C 中的二叉树，我编写了一个函数来搜索我的树，这是一棵字符串树。它有效，但是，如果字符串不在树中，它会出现错误，我正在努力弄清楚如何对其进行错误检查。我想知道是否有任何搜索树的最佳实践。

tnode *search(tnode *p, char *w)
{
    if (p->word == NULL || strcmp(w, p->word) == 0)
        return p;
    else if (strcmp(w, p->word) < 0)
        return search(p->left, w);
    else
        return search(p->right, w);
}

我已经对这个函数做了很多更改，但只要它 returns NULL 它就会出错。我能想到的最好的解决方案是让它 return 一个 int 或 bool 或 char * 这样我就不必处理 returning一个 NULL 结构。

有没有办法让它与这个函数一起工作，或者最好不要return一个结构？

Answer 1

我会说只有 p 等于 Null 缺失的守卫。

tnode*
search(tnode *p, char *w)
{
    if(p == NULL || w == NULL) return NULL;

    if (strcmp(w, p->word) == 0)
        return p;
    else if (strcmp(w, p->word) < 0)
        return search(p->left, w);
    else
        return search(p->right, w);
}

然后调用函数必须检查 search() returns Null（未找到）或指针（节点）。

你得到分段错误的原因是，如果键不在树中，那么你用 Null 调用 search()。 search() 做的第一件事是使用 p->word 检索单词，但 p 不是有效地址，导致异常。

Answer 2

并不是每个节点都有一个左节点和一个右节点child。有些人两者都没有，有些人两者都有。因此，如果要搜索的值不在树中，代码最终将调用 search(NULL, w)。这是未处理的。

可以进行其他改进：

有人可能想尝试搜索空树 (p == NULL)，所以应该检查一下。我们将利用相同的检查来解决主要问题。
节点的值 NULL 没有意义 (p->word)，因此检查它没有意义。
搜索NULL也没有意义。我们也可以避免这种检查。
让我们避免对 strcmp 进行两次相同的调用。
让我们将字符串标记为常量。

tnode *search(tnode *p, const char *w) {
    if (p == NULL)
        return NULL;

    int cmp = strcmp(w, p->word);
    if      (cmp < 0) return search(p->left, w);
    else if (cmp > 0) return search(p->right, w);
    else              return p;
}

最后，没有理由在这里使用递归。

tnode *search(tnode *p, const char *w) {
    while (p != NULL) {
        int cmp = strcmp(w, p->word);
        if      (cmp < 0) p = p->left;
        else if (cmp > 0) p = p->right;
        else              return p;
    }

    return NULL;
}

搜索二叉树的一些最佳实践是什么？

What are some best practices for searching a binary tree?

c

search

binary-tree

struct

data-structures