二叉树中的递归搜索

Question

我是一个初学者，我被一个函数卡住了，这个函数会在无序的二进制树中搜索给定的键。节点由值和指向左节点和右节点的指针组成。这是我的代码：

node *btree::search(int key, node *leaf){
if(leaf != NULL)
{
if(key == leaf->value)
{
return leaf;
}
search(key, leaf->left);
search(key, leaf->right);
}
else
{
return NULL;
}
}
node *btree::search(int key){
return search(key, root);
}

在某些情况下，我的函数返回正确的节点，但在其他情况下，它是运行时错误。这有什么问题，可以做些什么来解决这个问题？我不允许使用任何外部库，如队列或其他库。

Answer 1

这是初学者常见的错误。递归函数返回一个节点指针，但在进行递归调用时会忽略返回值。

search(key, leaf->left);
search(key, leaf->right);

它应该看起来像这个

node* ptr = search(key, leaf->left);
if (ptr != NULL)
return ptr;
else
return search(key, leaf->right);

即，返回通过在左侧子树中搜索找到的节点，但如果为NULL，则搜索右侧子树并返回在那里找到的节点(如果有(。

在编写递归代码时，您不仅要考虑递归调用，还要考虑递归调用的结果。

Answer 2

您调用未定义的行为，因为并非递归函数的所有代码路径都返回值。这可能会导致"运行时错误"、崩溃，或者只是一些不可预测的结果。

顺便说一句，搜索树的优势通常是，您可以获得对运行时复杂度为n*log(n(的元素的平均访问时间。但为此，树必须是有序的，我无法想象无序二叉树的有效用例；在这种情况下，一个链表也可以完成这项工作。

如果是有序树：

node *btree::search(int key, node *leaf){
if(leaf != NULL)
{
if(key == leaf->value) {
return leaf;
} else if (key < leaf->value) {
return search(key, leaf->left);
} else {
return search(key, leaf->right);
}
}
else
{
return NULL;
}
}

如果是无序树：

node *btree::search(int key, node *leaf){
if(leaf != NULL)
{
if(key == leaf->value) {
return leaf;
}
leaf = search(key, leaf->left);
if (! leaf) {
leaf = search(key, leaf->right);
}
return leaf;
}
else
{
return NULL;
}
}