C++实现BST插入第164个对象时栈溢出崩溃求助

我是计算机科学专业大学生，正在做趣味项目：读取《黑暗之魂3》武器属性.csv文件，用二叉搜索树（BST）整理武器列表。现有189个武器，但addNode()函数处理到第163个后崩溃，Weapon是含27个变量的结构体。

崩溃时错误信息：

Unhandled exception at 0x00007FF79DA7667E in DS3BuildTracker.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x0000005589C03FF8)

调试指向new_scalar.cpp中的operator new代码块，相关核心代码如下：

struct Weapon {
    int weaponID = -1; // unique identifier
    ...
};

void BinarySearchTree::Insert(Weapon weapon) {
    if (root == nullptr) {
        root = new Node(weapon);
    }
    else {
        addNode(root, weapon);
    }
}

void BinarySearchTree::addNode(Node* node, Weapon weapon) {
    if (node->weapon.weaponID > weapon.weaponID) {
        if (node->left == nullptr) {
            node->left = new Node(weapon);
        }
        else {
            this->addNode(node->left, weapon);
        }
    }
    else {
        if (node->right == nullptr) {
            node->right = new Node(weapon);
        }
        else {
            this->addNode(node->right, weapon);
        }
    }
}

void loadWeapons(string csvPath, BinarySearchTree* bst) {
    cout << "\n--- Loading file " << csvPath << " ---\n" << endl;

    vector<string> fileLines;
    ifstream weaponsFile;
    weaponsFile.open(csvPath);

    if (weaponsFile.is_open()) {
        while (weaponsFile.good()) {
            string line;
            getline(weaponsFile, line);
            if (line != "")
                fileLines.push_back(line);
        }
        weaponsFile.close();

        if (fileLines.size() == 0) {
            cout << "No data was found in " << csvPath << "." << endl;
        }

        cout << "File read successfully.\n" << endl;
    }

    if (fileLines.size() != 0) {
        cout << "Allocating data...\n" << endl;
        for (size_t i = 2; i < fileLines.size(); ++i) {
            Weapon weapon; // new weapon object
            string currLine = fileLines.at(i);
            vector<string> brokenStrings = splitString(currLine, ',');
            if (brokenStrings.size() == 0) {
                cout << "Incorrect file format." << endl;
                return;
            }
            
            weapon.weaponID = i - 1;
            weapon.weaponName = brokenStrings.at(0);
            // 省略27个变量的赋值逻辑...
            brokenStrings.clear();
            bst->Insert(weapon);
            displayWeapon(weapon);
            cout << endl;
        }
        cout << "Weapon data has been stored successfully.\n" << endl;
    }
    else {
        cout << "Unable to open " << csvPath << ".\n" << endl;
    }
    fileLines.clear();
}

displayWeapon()可正常打印武器属性，测试时能输出到weaponID 163，之后触发崩溃。

原因分析 #

栈溢出的核心原因是递归调用深度过大：

• addNode采用递归实现，当武器ID按递增顺序插入时，BST会退化成单链表结构，递归调用的深度等于已插入节点数。
• 每次递归调用addNode时，都会在栈上复制完整的Weapon结构体（27个变量），进一步快速消耗栈空间。当插入到第163个节点时，栈空间被耗尽，触发栈溢出错误。

修复方案 #

1. 改用迭代实现addNode（彻底解决栈溢出） #

迭代方式不会占用递归调用栈，是最稳妥的解决方案：

void BinarySearchTree::addNode(Node* node, Weapon weapon) {
    Node* current = node;
    while (true) {
        if (current->weapon.weaponID > weapon.weaponID) {
            if (current->left == nullptr) {
                current->left = new Node(weapon);
                break;
            } else {
                current = current->left;
            }
        } else {
            if (current->right == nullptr) {
                current->right = new Node(weapon);
                break;
            } else {
                current = current->right;
            }
        }
    }
}

2. 优化参数传递，减少栈消耗（配合递归使用） #

将Weapon参数改为const引用传递，避免每次递归都复制整个结构体：

// 修改Insert函数参数
void BinarySearchTree::Insert(const Weapon& weapon) {
    if (root == nullptr) {
        root = new Node(weapon);
    } else {
        addNode(root, weapon);
    }
}

// 修改addNode函数参数
void BinarySearchTree::addNode(Node* node, const Weapon& weapon) {
    if (node->weapon.weaponID > weapon.weaponID) {
        if (node->left == nullptr) {
            node->left = new Node(weapon);
        } else {
            this->addNode(node->left, weapon);
        }
    } else {
        if (node->right == nullptr) {
            node->right = new Node(weapon);
        } else {
            this->addNode(node->right, weapon);
        }
    }
}

这种方法能减少栈空间消耗，让递归能处理更多节点，但如果数据是严格递增/递减的，最终还是可能触发栈溢出，迭代方案更彻底。

3. 额外CSV读取优化 #

原代码中while (weaponsFile.good())存在逻辑问题，可能读取到无效行，建议修改为：

string line;
while (getline(weaponsFile, line)) {
    if (!line.empty()) {
        fileLines.push_back(line);
    }
}

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