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

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

我已经改变了这个函数，但只要它返回NULL，它就会出错。我能想到的最好的解决方案是让它返回int、bool或char *，这样我就不必处理返回NULL结构的问题。

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

Answer 1

不是每个节点都有一个左子节点和一个右子节点。有些人两者都没有，有些人会有一个或另一个。因此，如果正在搜索的值不在树中，则代码最终将调用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;
}

Answer 2

我想说的是，缺少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((是否返回Null(未找到(或指针(节点(。

出现分段错误的原因是，如果键不在树中，则使用Null调用search((。search((所做的第一件事是检索带有p->单词，但p不是有效地址，导致异常。