实现含插入查找删除的BST时出现Exit Status 137资源耗尽错误
2026-8-20
二叉搜索树实现触发资源耗尽错误（exit status 137）的修复
我尝试实现一个具备插入（insert）、查找（contains）、删除（remove）功能的二叉搜索树（BST），但运行程序时抛出错误：Killed exit status 137 -- Out Of Resources --，相关C++代码如下：
#include <vector> using namespace std; class BST { public: int value; BST *left; BST *right; BST(int val) { value = val; left = nullptr; right = nullptr; } BST& insert(int val) { BST *current = this; while (current != nullptr) { if (val < current->value) { if (current->left == nullptr) { current->left = new BST(val); break; } else current = current->left; } if (val > current->value) { if (current->right == nullptr) { current->right = new BST(val); break; } else current = current->right; } } return *this; } bool contains(int val) { BST *current = this; while (current != nullptr) { if (val < current->value) { current = current->left; } else if (val > current->value) { current = current->right; } else if (val == current->value) return true; //else if(current ==nullptr) //return false; } return false; } BST& remove(int val) { BST *current = this; BST *parent = nullptr; while (current != nullptr) { if (val < current->value) { parent = current; current = current->left; } if (val > current->value) { parent = current; current = current->right; } if (val == current->value) { if (current->left != nullptr && current->right != nullptr) { fnd(current->right); } else if (parent == nullptr) { if (current->left != nullptr) { current->value = current->left->value; current->right = current->left->right; current->left = current->left->left; } else if (current->right != nullptr) { current->value = current->right->value; current->left = current->right->left; current->right = current->right->right; } else current = nullptr; } else if (parent->left == current) { if (current->left != nullptr) { parent->left = current->left; } else { parent->left = current->right; } } else if (parent->right == current) { if (current->left != nullptr) { parent->right = current->left; } else { parent->right = current->right; } } break; } } return *this; } void fnd(BST *current) { BST *trav = current; BST *parent; while (trav->left != nullptr) { parent = trav; trav = trav->left; } current->value = trav->value; parent->left = nullptr; } };
问题根源分析
- insert函数死循环：当插入的值等于当前节点值时，没有任何处理逻辑，循环会一直执行（current始终不为nullptr，也不会触发break），导致CPU资源被持续占用，最终触发资源耗尽。
- remove函数分支逻辑错误：三个条件判断（val <、val >、val ==）没有用
else if，导致即使第一个条件成立，后面的条件仍会被判断，可能导致指针混乱或逻辑错误。 - fnd函数野指针与内存泄漏：
parent未初始化，如果传入的节点没有左子树，parent是野指针，执行parent->left = nullptr会引发未定义行为；同时找到最小节点后仅断开链接，未释放内存，造成泄漏，且如果该节点有右子树，会直接丢失这部分结构。
修复后的代码
#include <vector> using namespace std; class BST { public: int value; BST *left; BST *right; BST(int val) { value = val; left = nullptr; right = nullptr; } BST& insert(int val) { BST *current = this; while (current != nullptr) { if (val < current->value) { if (current->left == nullptr) { current->left = new BST(val); break; } else current = current->left; } else if (val > current->value) { if (current->right == nullptr) { current->right = new BST(val); break; } else current = current->right; } else { // 处理重复值，这里直接返回（BST通常不允许重复） break; } } return *this; } bool contains(int val) { BST *current = this; while (current != nullptr) { if (val < current->value) { current = current->left; } else if (val > current->value) { current = current->right; } else { return true; } } return false; } BST& remove(int val) { BST *current = this; BST *parent = nullptr; while (current != nullptr) { if (val < current->value) { parent = current; current = current->left; } else if (val > current->value) { parent = current; current = current->right; } else { // 找到要删除的节点 if (current->left != nullptr && current->right != nullptr) { // 找右子树最小节点，替换值并删除该节点 BST *trav = current->right; BST *minParent = current; while (trav->left != nullptr) { minParent = trav; trav = trav->left; } current->value = trav->value; // 删除最小节点 if (minParent == current) { minParent->right = trav->right; } else { minParent->left = trav->right; } delete trav; } else if (parent == nullptr) { // 删除根节点 BST *temp = current; if (current->left != nullptr) { current->value = current->left->value; current->right = current->left->right; temp = current->left; current->left = current->left->left; } else if (current->right != nullptr) { current->value = current->right->value; current->left = current->right->left; temp = current->right; current->right = current->right->right; } else { // 树只有根节点，这里需要外部处理，因为不能删除this指针 // 可以设置为nullptr，但类内无法直接修改外部指针 } if (temp != current) delete temp; } else if (parent->left == current) { parent->left = current->left != nullptr ? current->left : current->right; delete current; } else if (parent->right == current) { parent->right = current->left != nullptr ? current->left : current->right; delete current; } break; } } return *this; } };
修复要点
- insert函数：添加重复值的处理分支，避免死循环。
- remove函数：将条件判断改为
else if，确保每次只执行一个分支；处理双子女节点时，正确删除找到的最小节点，避免内存泄漏和子树丢失；释放被删除节点的内存，避免内存泄漏。 - 移除fnd函数：将其逻辑整合到remove中，避免野指针问题。
内容的提问来源于stack exchange，提问作者codingwolf
相关产品推荐
相关产品推荐
