C++实现AVL树时多删除文件无输出的调试求助

阿华AIGC实验室

2026-5-14

问题分析与修复方案

从你的描述和代码来看，程序处理后续删除文件时无响应，大概率是死循环或者内存操作错误导致的。我仔细检查了你的avl_delete及其辅助函数，发现了几个关键问题：

1. 寻找后继节点时的死循环

在处理双孩子节点删除的代码块中，寻找直接后继的逻辑完全错误：

// 错误代码
temp = sub_root->right;
while (sub_root->left != NULL){
 temp = sub_root->left;
}

你一直在判断sub_root->left是否为空，而不是遍历temp的左子树。如果当前节点有左孩子，这个循环会无限执行，直接导致程序卡死。

修复方案：
将循环条件改为遍历temp的左子节点：

// 修正后的代码
temp = sub_root->right;
while (temp->left != NULL){ // 改为遍历temp的左子树
 temp = temp->left;
}

2. 单孩子节点删除时的内存错误

在处理只有左/右孩子的节点删除时，指针操作逻辑错误，会导致野指针和树结构破坏：

// 错误代码（无左孩子情况）
else if (sub_root->left == NULL){
 temp = sub_root->right;
 sub_root = temp;
 delete temp; // 这里删除了新的sub_root节点
 shorter = true;
}

这段代码把sub_root指向右孩子后，立刻删除这个右孩子，导致sub_root变成野指针，后续操作必然出错。

修复方案：
先保存当前要删除的节点，再将sub_root指向子节点，最后删除原节点：

// 修正后的无左孩子情况
else if (sub_root->left == NULL){
 Binary_node<Record>* temp = sub_root; // 保存当前待删除节点
 sub_root = sub_root->right; // 将sub_root指向右孩子
 delete temp; // 删除原节点
 shorter = true;
}

同理，无右孩子的情况也要做相同修正：

else if (sub_root->right == NULL){
 Binary_node<Record>* temp = sub_root;
 sub_root = sub_root->left;
 delete temp;
 shorter = true;
}

3. 递归删除后继节点时未处理返回值

在删除双孩子节点的后继时，你调用了递归删除，但没有处理返回值。如果后继节点不存在（理论上不该发生，但代码需要健壮性），会导致后续平衡逻辑错误执行。

修复方案：
接收递归调用的返回值，若为not_present则直接返回：

// 修正后的双孩子节点处理
else {
 // 寻找直接后继
 Binary_node<Record> *temp = sub_root->right;
 while (temp->left != NULL){
  temp = temp->left;
 }
 // 替换当前节点的值为后继的值
 sub_root->data = temp->data;
 // 删除后继节点
 Error_code res = avl_delete(sub_root->right, temp->data, shorter);
 if (res == not_present) return res; // 处理异常情况
}

同样，在递归删除左/右子树的分支中，也需要处理返回值：

else if (old_data < sub_root->data){
 Error_code res = avl_delete(sub_root->left, old_data, shorter);
 if (res == not_present) return res;
}
else if (old_data > sub_root->data){
 Error_code res = avl_delete(sub_root->right, old_data, shorter);
 if (res == not_present) return res;
}

4. 平衡调整时的逻辑错误

在平衡调整部分，你用old_data和sub_root->data的大小关系来判断删除发生在左还是右子树，这在删除后继节点的场景下是错误的——此时old_data是后继节点的值，和当前sub_root的大小关系不能反映实际删除的分支。

修复方案：
需要跟踪删除操作是发生在当前节点的左子树还是右子树，而不是用old_data比较。可以修改递归调用的逻辑，传递一个标记：

// 修改递归调用部分，记录删除分支
bool deleted_in_left = false;
if (old_data < sub_root->data){
 Error_code res = avl_delete(sub_root->left, old_data, shorter);
 if (res == not_present) return res;
 deleted_in_left = true;
}
else if (old_data > sub_root->data){
 Error_code res = avl_delete(sub_root->right, old_data, shorter);
 if (res == not_present) return res;
 deleted_in_left = false;
}
// ... 后续平衡处理时用deleted_in_left代替old_data比较

然后在平衡调整部分：

if (shorter) {
 shorter = false;
 if (sub_root->get_balance() == equal_height) {
  if (deleted_in_left) // 删除在左子树，右子树相对更高
   sub_root->set_balance(right_higher);
  else // 删除在右子树，左子树相对更高
   sub_root->set_balance(left_higher);
 }
 else if (sub_root->get_balance() == right_higher) {
  if (deleted_in_left){ // 删除左子树导致失衡，需要右平衡
   right_balance(sub_root);
   if (sub_root->get_balance() == equal_height)
    shorter = true;
  }
  else { // 删除右子树，高度降低，平衡因子重置
   sub_root->set_balance(equal_height);
   shorter = true;
  }
 }
 else if (sub_root->get_balance() == left_higher) {
  if (deleted_in_left){ // 删除左子树，高度降低，平衡因子重置
   sub_root->set_balance(equal_height);
   shorter = true;
  }
  else { // 删除右子树导致失衡，需要左平衡
   left_balance(sub_root);
   if (sub_root->get_balance() == equal_height)
    shorter = true;
  }
 }
}