C++：基于向量的二叉树插入后节点值打印异常问题

我来帮你排查这个问题，大概率是索引计算溢出或者vector越界访问导致的，咱们一步步拆解可能的原因和解决办法：

最可能的原因1：有符号整数索引溢出 #

你用2i和2i+1计算子节点索引时，如果i是int类型，当树的深度足够大，i超过INT_MAX/2时，2i会直接溢出变成负数（有符号整数溢出属于未定义行为，通常会绕回成负数）。这时候访问vector[负数索引]会读取到内存里的垃圾值，自然就出现了负数异常。

原因2：Vector未扩容导致的越界访问 #

如果你的插入逻辑是直接给vec[2i]或vec[2i+1]赋值，但此时vector的size()还没到目标索引的位置，operator[]不会自动扩容，直接访问会触发越界，覆盖内存中的其他数据，也会出现莫名其妙的负数。

原因3：索引起始值混乱 #

很多2i/2i+1的二叉树存储算法是从索引1开始的（根节点i=1，左子21=2，右子21+1=3），如果你的根节点存在索引0，计算左子节点时会得到0，直接覆盖根节点，也会导致数据异常。

对应的解决办法 #

1. 改用无符号整数存储索引 #

把索引类型换成size_t（vector的size()返回值就是这个类型），它是无符号的，就算数值很大也不会变成负数，从根源避免溢出问题：

// 计算左子节点索引时用size_t类型
size_t left_idx = 2 * parent_idx;

2. 插入前确保Vector足够大 #

在给子节点位置赋值前，先检查vector的大小是否大于等于目标索引+1，如果不够就用resize()扩容，同时给空节点设置默认标识（比如ID=-1），方便区分有效节点和空节点：

void insert_right_child(std::vector<TreeNode>& tree, size_t parent_idx, TreeNode child) {
    size_t right_idx = 2 * parent_idx + 1;
    // 扩容到目标索引+1，确保位置合法
    if (right_idx >= tree.size()) {
        tree.resize(right_idx + 1, {-1, 0, ""}); // 空节点默认ID=-1
    }
    tree[right_idx] = child;
}

3. 统一索引起始规则 #

要么从索引1开始（根节点放在tree[1]，tree[0]留空当占位符），要么修改子节点计算规则（如果根节点在0，左子是2i+1，右子是2i+2），别混用两种规则。

验证示例 #

这里给个简单的可运行示例，你可以参考调整自己的代码：

#include <vector>
#include <string>
#include <iostream>

struct TreeNode {
    int ID = -1;
    int Age = 0;
    std::string name = "";
};

// 插入左子节点，根节点从索引1开始
void insert_left(std::vector<TreeNode>& tree, size_t parent_idx, TreeNode child) {
    size_t left_idx = 2 * parent_idx;
    if (left_idx >= tree.size()) {
        tree.resize(left_idx + 1, {-1, 0, ""});
    }
    tree[left_idx] = child;
}

int main() {
    std::vector<TreeNode> tree(1); // 索引0留空
    // 插入根节点
    tree[1] = {1, 30, "Charlie"};
    // 插入根节点的左子
    insert_left(tree, 1, {2, 27, "Diana"});
    
    // 打印所有有效节点
    for (size_t i = 1; i < tree.size(); ++i) {
        if (tree[i].ID != -1) {
            std::cout << "Idx " << i << ": ID=" << tree[i].ID << ", Age=" << tree[i].Age << ", Name=" << tree[i].name << "\n";
        }
    }
    return 0;
}

先按这几点排查，应该能解决你遇到的负数异常问题～

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