C++二叉搜索树无法定位条目：输入有效ID均提示未找到

已确认accounts.dat文件可正常定位并打开，文件内容如下：

Record# AccountID FirstName LastName Balance
0 6274 James Johnson 415.56
1 2843 Marcus Wilson 9217.23
2 2892 Maureen Albright 51462.56
3 8837 Debra Douglas 27.26
4 1892 Mary Smith 918.26
5 9523 Bruce Gold 719.32
6 3165 John Carlson 1496.24
7 3924 Simon Becker 386.85
8 6023 John Edgar 9.65
9 5290 George Truman 16110.68
10 8529 Ellen Fairchild 86.77
11 1144 Donald Williams 4114.26

对应的C++代码如下：

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

struct Account
{
    int acctID;      // Account identifier
    string firstName;
    string lastName;
    double balance;
};

struct IndexEntry
{
    int acctID;      // (key) Account identifier
    long recNum;     // Record number
};

struct TreeNode {
    IndexEntry data;
    TreeNode* left;
    TreeNode* right;
};

// Function to insert a new node into the index tree
void insertNode(TreeNode*& root, IndexEntry data)
{
    IndexEntry record;
    record.acctID = data.acctID;
    record.recNum = data.recNum;
    if (root == nullptr) {
        root = new TreeNode;
        root->data = record;
        root->left = root->right = nullptr;
    }
    else if (data.acctID < root->data.acctID) {
        insertNode(root->left, record);
    }
    else if (data.acctID > root->data.acctID) {
        insertNode(root->right, record);
    }
}

// Function to search for a node with a given account ID in the index tree
TreeNode* searchNode(TreeNode* root, int acctID)
{
    if (root == nullptr || root->data.acctID == acctID) {
        return root;
    }
    else if (acctID < root->data.acctID) {
        return searchNode(root->left, acctID);
    }
    else {
        return searchNode(root->right, acctID);
    }
}

// Function to retrieve an account record from the database file
void getAccountRecord(ifstream& file, long recNum)
{
    file.seekg(recNum * sizeof(Account));
    Account record;
    file.read(reinterpret_cast<char*>(&record), sizeof(record));
    cout << record.acctID << "	" << record.firstName << "	" << record.lastName << "	" << record.balance << endl;
}

int main()
{
    // Open the database file for reading
    ifstream file("accounts.dat", ios::binary);
    if (!file) {
        cerr << "Error opening database file!" << endl;
        return 1;
    }

    // Build the index tree by reading through the database file
    TreeNode* indexTree = nullptr;
    IndexEntry record;
    long recNum = 0;
    while (file.read(reinterpret_cast<char*>(&record), sizeof(record))) {
        record.recNum = recNum;
        insertNode(indexTree, record);
        recNum++;
    }

    // Search for account records based on account ID
    int acctID;
    cout << "Enter account ID to retrieve record: ";
    cin >> acctID;
    TreeNode* node = searchNode(indexTree, acctID);
    if (node == nullptr) {
        cout << "Account record not found!" << endl;
    }
    else {
        getAccountRecord(file, node->data.recNum);
    }

    // Clean up
    file.close();
    return 0;
}

怀疑问题出在二叉搜索树构建环节。

核心错误有两个：

1. 文件读取结构不匹配：accounts.dat存储的是Account结构体数据，但代码构建索引时却用IndexEntry结构体读取，导致读取的acctID完全无效，二叉树中插入的都是错误ID，自然无法搜索到有效记录。
2. 文件指针位置错误：构建索引时已将文件读到末尾，后续调用getAccountRecord时未重置文件指针，即使搜索到记录也无法正确读取。

1. 修正索引构建的读取逻辑 #

将读取IndexEntry改为读取Account结构体，从中提取有效acctID构造IndexEntry：

// 原错误代码
// IndexEntry record;
// long recNum = 0;
// while (file.read(reinterpret_cast<char*>(&record), sizeof(record))) {
//     record.recNum = recNum;
//     insertNode(indexTree, record);
//     recNum++;
// }

// 修正后代码
Account account;
long recNum = 0;
while (file.read(reinterpret_cast<char*>(&account), sizeof(account))) {
    IndexEntry entry;
    entry.acctID = account.acctID;
    entry.recNum = recNum;
    insertNode(indexTree, entry);
    recNum++;
}

2. 重置文件指针 #

在getAccountRecord函数中先重置文件指针并清除EOF标志，确保读取操作正常：

void getAccountRecord(ifstream& file, long recNum)
{
    file.clear(); // 清除文件末尾标志
    file.seekg(0, ios::beg); // 重置指针到文件开头
    file.seekg(recNum * sizeof(Account));
    Account record;
    file.read(reinterpret_cast<char*>(&record), sizeof(record));
    cout << record.acctID << "\t" << record.firstName << "\t" << record.lastName << "\t" << record.balance << endl;
}

3. 额外优化：修复内存泄漏 #

原代码未释放二叉树节点，添加递归销毁函数清理内存：

void destroyTree(TreeNode*& root)
{
    if (root != nullptr) {
        destroyTree(root->left);
        destroyTree(root->right);
        delete root;
        root = nullptr;
    }
}

// 在main函数return前调用
destroyTree(indexTree);

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