二叉搜索树插入重复值时节点重复生成问题排查

问题复现 #

需求规则：实现二叉搜索树插入逻辑，当插入值已存在时，将重复值设为当前节点的左子节点，原结构按预期下移。

初始树结构：

5
      /   \
     3     6
    / \     \
   2   4     9
  /
 1

插入重复值3的预期结构：

5
          /   \
         3     6
        /       \
       3         9
      / \
     2   4
    /
   1

原有代码运行得到的错误结构：

5
              /   \
             3     6
            / \     \
           3   4     9
          /
         2
        /
       2
      /
     1
    /
   1

原有错误代码：

tree *insert(tree *tree, int data){
    if(tree == NULL){
        return new(data);
    }

    if(data > tree->data){
        tree->right = insert(tree->right, data);
    }
    else if(data < tree->data){
        tree->left = insert(tree->left, data);
    }
    else if(data == tree->data){
        if(tree->left == NULL){
            tree->left = insert(tree->left, data);
        }
        else if(tree->left != NULL){
            struct tree *temp = copy(tree->left);

            
            tree->left->data = data;

            tree->left->left = insert(temp, temp->data);
        }
    }

    return tree;
}

错误原因 #

• 递归逻辑滥用：处理重复值时，你对复制得到的原左子树temp调用insert(temp, temp->data)，会递归遍历左子树所有节点，给每个节点都触发一次重复插入逻辑，导致左子树所有节点被逐层复制，这就是2、1节点重复出现的核心原因。
• 非法修改原有节点数据：代码直接修改了原左子节点的data值，破坏了原有树的结构，完全偏离了“新建节点承接原有子树”的需求。
• 冗余的copy操作：重复值插入不需要复制原有子树，直接调整指针即可，copy操作反而增加了内存开销和逻辑复杂度。

修正方案 #

重复值插入不需要递归，仅需新建节点后调整指针即可，完全匹配预期结构：

• 遇到值相等的节点时，直接创建值为data的新节点
• 将当前节点原有的左、右子树全部挂载到新节点上（匹配预期中4节点下移到新3节点右侧的效果）
• 将新节点设为当前节点的左子节点，同时清空当前节点的右指针

修正后的完整代码：

tree *insert(tree *tree, int data){
    if(tree == NULL){
        return new(data);
    }

    if(data > tree->data){
        tree->right = insert(tree->right, data);
    }
    else if(data < tree->data){
        tree->left = insert(tree->left, data);
    }
    else {
        // 处理重复值，无需递归
        struct tree *new_node = new(data);
        // 新节点承接当前节点原有所有子树
        new_node->left = tree->left;
        new_node->right = tree->right;
        // 当前节点左指针指向新节点，右指针置空
        tree->left = new_node;
        tree->right = NULL;
    }

    return tree;
}

验证说明 #

修正后的代码插入重复值3时，会在原3节点下新建值为3的节点，把原3节点的左（2子树）、右（4节点）全部挂到新节点下，原3节点仅保留左指针指向新节点，最终结构和预期完全一致，不会触发递归复制子节点的问题。

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