二叉搜索树（BST）遍历结果与预期不符问题求助

问题根源 #

你的代码遍历逻辑本身没有错误，完全符合中序、前序、后序遍历的定义。问题出在删除根节点时的替换策略：

• 当前代码采用「右子树最小节点替换待删除节点」的实现
• 而你预期的结果基于「左子树最大节点替换待删除节点」的策略

两种策略都是BST删除节点的合法方式，但会生成不同结构的树，最终导致遍历序列出现差异。

操作后的树结构对比 #

你的代码生成的树（删除7后）

根节点为右子树最小节点8，结构如下：

8
    /   \
   1     9
    \     \
     2     10

对应遍历结果：

• 前序：8 1 2 9 10
• 后序：2 1 10 9 8

预期的树结构（删除7后）

根节点为左子树最大节点2，结构如下：

2
    /   \
   1     9
        /  \
       8    10

对应遍历结果：

• 前序：2 1 9 8 10
• 后序：1 8 10 9 2

解决方法 #

修改deleteRecursive函数中的替换逻辑，将「找右子树最小节点」改为「找左子树最大节点」：

步骤1：添加findMax辅助函数 #

在BST类的private区域添加以下函数：

Node *findMax(Node *root)
{
    while (root->right != nullptr)
    {
        root = root->right;
    }
    return root;
}

步骤2：修改删除逻辑中的替换部分 #

将deleteRecursive函数中替换节点的代码段：

Node *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteRecursive(root->right, temp->data);

替换为：

Node *temp = findMax(root->left);
root->data = temp->data;
root->left = deleteRecursive(root->left, temp->data);

修改后的验证 #

完成修改后，按照你的操作流程执行：

1. 初始插入7、9、1、2、10
2. 插入已存在的2（提示已存在）
3. 插入8（提示已插入）
4. 删除不存在的12（提示未找到）
5. 删除根节点7（提示已删除）

此时遍历结果将完全符合你的预期：

• 中序遍历：1 2 8 9 10
• 前序遍历：2 1 9 8 10
• 后序遍历：1 8 10 9 2

内容的提问来源于stack exchange，提问作者mehrab.4