二叉搜索树search函数返回值异常：部分已存在ID返回false

问题现象 #

用C++实现的二叉搜索树包含节点插入与ID搜索功能，当前存在以下异常：

• 输入不存在的ID（如444）：search函数正确返回false并输出"Record not found"
• 输入根节点ID（1021）：正确返回true并输出对应姓名"John Williams"
• 输入其他已存在的ID（如1899，对应姓名"Ashley Smith"）：函数返回false

实现代码 #

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    int Identification;
    string full_name;
    Node *left;
    Node *right;
};

Node *newNode(int id, string name)
{
    Node *temp = new Node;
    temp->Identification = id;
    temp->full_name = name;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

Node* insert(Node* node, int id, string name)
{
    if ( node == NULL)
    {
        return newNode(id,name);
    }
    
    if(id < node->Identification)
    {
        node->left = insert(node->left, id, name);
    }
    else if (id > node->Identification)
    {
        node->right = insert(node->right, id, name);
    }
    
    return node;
}

bool search(Node* root, int id)
{
    if (root == NULL || root->Identification == id)
    {
        cout << root->full_name << endl;
        return true;
    }
    else if (root != NULL && root->Identification != id)
    {
        cout << "Record not found";
        return false;
    }
    
    
    if (root->Identification < id)
    {
        return search(root->right, id);
    }
    return search(root->left, id);
    
}


int main()
{
    int searching;
    Node *root = NULL;

    root = insert(root, 1021, "John Williams");
    root = insert(root, 1057, "Bill Witherspoon");
    root = insert(root, 2487, "Jennifer Twain");
    root = insert(root, 3769, "Sophia Lancaster");
    root = insert(root, 1017, "Debbie Reece");
    root = insert(root, 1275, "George McMullen");
    root = insert(root, 1899, "Ashley Smith");
    root = insert(root, 4218, "Josh Plemmons");
  
    cout << "Enter ID to find employe name ";
    cin >> searching;
    search(root, searching);

    return 0;
}

问题原因 #

search函数的逻辑分支存在严重错误，导致递归搜索的代码完全无法执行：

1. 第一个条件if (root == NULL || root->Identification == id)：当root为NULL时，直接访问root->full_name会触发空指针引用（未定义行为）；同时该条件仅能匹配根节点的目标ID。
2. 第二个条件else if (root != NULL && root->Identification != id)：只要当前节点不是目标ID，无论是否存在子节点，直接返回false并输出提示，完全跳过了递归搜索左右子树的步骤。这就是非根存在ID无法被找到的核心原因。

修正后的代码 #

调整search函数的逻辑顺序，确保先判断空节点、再匹配目标、最后递归搜索子树：

bool search(Node* root, int id)
{
    // 空节点，说明未找到
    if (root == NULL)
    {
        cout << "Record not found" << endl;
        return false;
    }
    // 当前节点匹配目标ID
    if (root->Identification == id)
    {
        cout << root->full_name << endl;
        return true;
    }
    
    // 根据二叉搜索树规则递归搜索子树
    if (root->Identification < id)
    {
        return search(root->right, id);
    }
    return search(root->left, id);
}

修正说明 #

• 先判断节点是否为空，避免空指针引用问题，同时明确未找到的分支
• 匹配到目标ID时直接返回结果
• 未匹配时，根据二叉搜索树的特性（左子树节点ID小于当前节点，右子树大于）递归搜索对应子树，确保所有存在的节点都能被遍历到

内容的提问来源于stack exchange，提问作者Juan Martinez