C++构建权重节点树时父节点将自身作为子节点的问题排查

问题根因 #

你的代码核心问题是存储了指向std::vector内部元素的指针，后续vector的修改操作导致指针悬空。

对应你的代码执行流程具体说明：

1. 创建新节点时，你直接取&nodes[size - 1]、&nodes[size - 2]作为子节点指针存入新节点，这两个指针指向vector当前存储的两个Node实例的内存地址
2. 执行两次pop_back后，这两个尾端的Node实例被销毁，对应的内存被释放，你之前存的两个子节点指针变成野指针，访问它们的内容属于C++未定义行为
3. 紧接着执行push_back(newNode)时，vector会申请内存存储新的Node实例，大概率会复用刚才被释放的两个尾端元素的其中一块内存，这就导致你之前存的某个野指针刚好指向了刚插入的新节点本身，也就出现了调试信息里子节点ID等于父节点ID的情况

std::vector在增删元素时会自动管理内部内存，只要你对vector做增删操作，之前指向vector内部元素的指针就有概率失效，这是std::vector的常规特性，不属于逻辑bug，是用法不符合规范。

修复方案 #

推荐两种可行的修改思路：

• 方案一：将vector的存储类型从Node改为Node*，所有节点都通过new动态分配内存，只要你不主动delete节点，节点的内存地址就不会发生变化，存储的子节点指针始终有效。注意整个流程结束后要手动遍历树释放所有节点避免内存泄漏。
• 方案二：新增一个全局的vector<Node>用来永久存储所有创建过的节点，原来用于排序的vector只存节点在全局存储vector中的索引值，取子节点时通过索引去全局存储vector里取，这样节点的内存地址也不会因为排序vector的增删操作发生变化。

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