二叉搜索树（BST）remove方法实现异常，寻求技术排查建议

问题背景 #

编写二叉搜索树的remove()方法时，出现节点删除不彻底、树中大量重复元素的问题。以下是实现代码、逻辑说明及错误输出：

原实现代码 #

template <typename Comparable>
void BinarySearchTree<Comparable>::remove(BinaryNode *&t)
{
    //Add you code here
    int random = rand() % 100 + 1;

    if(t == nullptr){
        return; //item not found, do nothing. 
    }else if(t->left != nullptr && t->right == nullptr){
        t->element = findMax(t->left)->element;
        remove (t->left);
    }else if(t->right != nullptr && t->left == nullptr){
        t->element = findMin(t->right)->element;
        remove (t->right);
    }else if(t->left != nullptr && t->right != nullptr){
        // int random = rand() % 100 + 1;
        if(random % 2 == 0)
            t->element = findMax(t->left)->element;
            remove (t->left);
        if(random % 2 != 0)   
            t->element = findMin(t->right)->element;
            remove (t->right);
    }
}

预期逻辑 #

• 若t为nullptr则直接返回；
• 若节点t左子树非空、右子树为空：用左子树最大值节点元素替换t的元素，递归删除左子树的最大值节点；
• 若节点t右子树非空、左子树为空：用右子树最小值节点元素替换t的元素，递归删除右子树的最小值节点；
• 若左右子树均非空：生成1-100的随机整数，偶数时用左子树最大值替换并删除对应节点，奇数时用右子树最小值替换并删除对应节点。

错误输出 #

The built binary search tree (BST) is (preorder traversal):
50 30 20 15 25 40 35 45 70 60 55 65 80 75 85 

The updated binary search tree (BST) is (preorder traversal):
45 35 15 15 25 35 35 45 65 55 55 65 85 75 85 

The updated binary search tree (BST) is (preorder traversal):
55 35 15 15 25 45 35 45 65 55 55 65 90 78 78 90 90 

The updated binary search tree (BST) is (preorder traversal):
45 26 26 10 10 26 26 35 35 45 65 65 55 65 90 78 78 90 90 

问题排查 #

1. 分支逻辑错误：缺少花括号导致代码执行顺序混乱
   在左右子树均非空的分支中，if(random%2==0)和if(random%2!=0)语句没有用花括号包裹代码块。这会导致：

   • 无论随机数是奇是偶，remove(t->left)和remove(t->right)都会被执行；
   • 节点元素会被两次替换（先左子树最大值，再右子树最小值，或反之），最终导致树中出现大量重复元素。

2. 叶子节点处理缺失
   代码未覆盖t->left == nullptr && t->right == nullptr的情况（叶子节点），此时无法直接删除节点，导致叶子节点残留，后续递归也无法正确清理。

3. 随机数生成位置不合理
   随机数在函数开头就生成，但只有左右子树均非空时才需要，属于不必要的计算。

修复方案 #

以下是修正后的代码，针对上述问题逐一修复：

template <typename Comparable>
void BinarySearchTree<Comparable>::remove(BinaryNode *&t)
{
    if(t == nullptr){
        return; // 未找到节点，直接返回
    }
    // 处理叶子节点：直接删除并置空
    else if(t->left == nullptr && t->right == nullptr){
        delete t;
        t = nullptr;
    }
    else if(t->left != nullptr && t->right == nullptr){
        // 左子树非空，右子树为空：用左子树最大值替换
        t->element = findMax(t->left)->element;
        remove(t->left);
    }
    else if(t->right != nullptr && t->left == nullptr){
        // 右子树非空，左子树为空：用右子树最小值替换
        t->element = findMin(t->right)->element;
        remove(t->right);
    }
    else if(t->left != nullptr && t->right != nullptr){
        // 左右子树均非空时才生成随机数
        int random = rand() % 100 + 1;
        if(random % 2 == 0){
            // 偶数：左子树最大值替换 + 删除对应节点
            t->element = findMax(t->left)->element;
            remove(t->left);
        } else {
            // 奇数：右子树最小值替换 + 删除对应节点
            t->element = findMin(t->right)->element;
            remove(t->right);
        }
    }
}

修复说明 #

• 给分支语句添加花括号，确保每个条件下的代码块仅在满足条件时执行；
• 新增叶子节点处理分支，直接删除节点并将指针置空，彻底移除叶子节点；
• 将随机数生成移至左右子树均非空的分支内，避免不必要的计算；
• 将第二个if改为else，避免重复判断（随机数非偶即奇，无需二次判断）。

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