C++二叉搜索树递归删除节点破坏遍历算法问题求助

嘿，我看你在实现二叉搜索树的递归删除时遇到了遍历正确性的问题，咱们来捋清楚问题出在哪，再给出修复方案~

你的代码核心问题 #

你当前的remove_rec函数是void类型，而且传递的Node* ptr是传值参数——这意味着递归调用时，你修改的只是指针的副本，上层父节点的left或right指针根本不会被更新。举个例子：当你删除左子树里的某个节点，父节点的left还是指向原来的节点地址，而那个节点已经被你处理了，这直接导致树的结构断裂，遍历自然会出错。另外，你删除节点的逻辑只写了开头，没覆盖BST删除的三种核心场景。

修复后的递归删除实现 #

正确的递归删除需要让函数返回Node*，这样每一层递归都能把更新后的子节点指针返回给父节点，从而维护树的完整结构。下面是完整的实现：

// 辅助函数：找到以ptr为根的子树中的最小节点
Node* find_min(Node* ptr) {
    while (ptr->left != nullptr) {
        ptr = ptr->left;
    }
    return ptr;
}

// 递归删除节点，返回更新后的子树根节点
Node* remove_rec(string word, Node* ptr) { 
    // 递归终止条件：没找到要删除的节点
    if (ptr == nullptr) {
        return nullptr;
    }

    // 向左子树递归查找
    if (word < ptr->data) { 
        ptr->left = remove_rec(word, ptr->left); 
    } 
    // 向右子树递归查找
    else if (word > ptr->data) { 
        ptr->right = remove_rec(word, ptr->right); 
    } 
    // 找到要删除的节点，处理三种情况
    else { 
        // 情况1：节点没有子节点
        if (ptr->left == nullptr && ptr->right == nullptr) {
            delete ptr;
            return nullptr; // 父节点的对应指针设为null
        }
        // 情况2：节点只有右子节点
        else if (ptr->left == nullptr) {
            Node* temp = ptr->right;
            delete ptr;
            return temp; // 返回右子节点给父节点
        }
        // 情况3：节点只有左子节点
        else if (ptr->right == nullptr) {
            Node* temp = ptr->left;
            delete ptr;
            return temp; // 返回左子节点给父节点
        }
        // 情况4：节点有两个子节点——用右子树的最小节点替代（或左子树最大节点）
        Node* temp = find_min(ptr->right);
        // 把最小节点的值复制到当前节点
        ptr->data = temp->data;
        // 递归删除右子树中的那个最小节点
        ptr->right = remove_rec(temp->data, ptr->right);
    }
    // 返回当前节点（未被删除时）
    return ptr;
}

关键修复点说明 #

• 返回Node*类型：每一层递归结束后，把更新后的子节点指针返回给父节点，让父节点的left/right能正确指向新的子树，保证树结构的完整性。
• 覆盖所有删除场景：BST删除节点必须处理无子女、单子女、双子女三种情况，双子女场景需要用后继节点（右子树最小）或前驱节点（左子树最大）替代，再删除那个替代节点。
• 正确释放内存：删除节点后记得用delete释放内存，避免内存泄漏。

这样修改后，你的BST的中序、前序、后序遍历就能恢复正确性了~

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