使用Vector触发Out Of Range错误：基于Vector实现BST的插入异常

嘿，我来帮你搞定这个Vector实现BST时的越界问题！你遇到的out_of_bounds错误，大概率是因为操作Vector索引时没考虑它的动态特性，或者BST插入逻辑和Vector的存储方式没匹配好。咱们一步步拆解：

可能的错误原因 #

• 直接访问未初始化的Vector索引：如果你是用数组式的索引模拟BST结构（比如父节点i的左孩子是2i+1、右孩子是2i+2），插入第二个节点时，可能直接去访问超出当前Vector大小的索引。比如第一个节点存在索引0，插入左孩子时想直接赋值给索引1，但此时Vector的size是1，索引1根本不存在，自然抛出越界错误。
• 插入逻辑中索引计算错误：如果你的BST是通过维护节点的左右孩子索引来实现的，可能在查找插入位置时，错误地指向了一个无效的索引位置，导致访问Vector时越界。

对应的解决方案 #

1. 数组式存储BST时，提前扩展Vector大小 #

如果坚持用完全二叉树的数组存储方式，插入节点前必须先检查目标索引是否超出Vector当前的有效范围，若超出则先扩展Vector的大小：

// 假设要插入到索引pos
if (pos >= bst.size()) {
    bst.resize(pos + 1); // 扩展Vector到能容纳pos的大小
}
bst[pos] = newNode; // 现在赋值就不会越界了

比如插入第二个节点（作为第一个节点的左孩子，索引1），先判断Vector的size是否小于等于1，是的话resize到2，再赋值。

2. 改用“节点+索引指针”的安全存储方式 #

更推荐的做法是，每个节点存储左右孩子的索引（初始为-1表示空），插入时用push_back()安全添加新节点，再更新父节点的索引指向。这样完全不会出现越界问题，示例代码如下：

#include <vector>
#include <string>

// 定义节点结构，包含左右孩子的索引
struct BSTNode {
    int id;
    int age;
    std::string name;
    int left_idx;
    int right_idx;
    BSTNode(int i, int a, std::string n) 
        : id(i), age(a), name(n), left_idx(-1), right_idx(-1) {}
};

std::vector<BSTNode> bst;

void insertNode(int id, int age, std::string name) {
    BSTNode new_node(id, age, name);
    // 空树直接插入根节点
    if (bst.empty()) {
        bst.push_back(new_node);
        return;
    }

    int current_idx = 0;
    while (true) {
        if (id < bst[current_idx].id) {
            // 左孩子为空，插入新节点并更新父节点左索引
            if (bst[current_idx].left_idx == -1) {
                bst.push_back(new_node);
                bst[current_idx].left_idx = bst.size() - 1;
                break;
            } else {
                current_idx = bst[current_idx].left_idx;
            }
        } else {
            // 右孩子为空，插入新节点并更新父节点右索引
            if (bst[current_idx].right_idx == -1) {
                bst.push_back(new_node);
                bst[current_idx].right_idx = bst.size() - 1;
                break;
            } else {
                current_idx = bst[current_idx].right_idx;
            }
        }
    }
}

// 测试代码
int main() {
    insertNode(104, 10, "Bob");
    insertNode(102, 11, "Steve"); // 这里不会再抛出越界错误
    return 0;
}

总结 #

核心问题就是你操作Vector时没保证索引的有效性——要么提前扩展Vector的大小适配索引，要么用push_back()安全添加节点后维护索引关系。上面的第二种方法更灵活，也不容易出错，建议你试试。

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