c++ - C++ 中的 BST 搜索键

Question

我正在尝试实现 BST 搜索方法以在 BST 中查找 key 。下面是代码。

node* search_key(node **root,int key)
{
    if (*root == NULL || (*root)->data == key ){
        return (*root);
    } 
    if ( key < (*root)->data ) {
         search_key(&(*root)->left, key); 
    }
    else{
         search_key(&(*root)->right, key);
    }
}

除了搜索根节点之外，上面的代码总是返回 null。我将代码修改为以下内容，并且运行良好。谁能解释一下这里涉及的递归？

node* search_key(node **root,int key)
{
    if (*root == NULL || (*root)->data == key ){
        return (*root);
    } 
    if ( key < (*root)->data ) {
         return search_key(&(*root)->left, key); // note return 
    }
    else{
         return search_key(&(*root)->right, key);
    }
}

Answer 1

在第一个代码片段中，您有一个应该返回某些内容的函数，但在某些情况下不会这样做。这将导致未定义的行为。

在第二个片段中，您实际上在函数的所有路径中返回了一些东西。