将重复数字添加到二进制搜索树

Question

因此，我正在尝试为二进制搜索树创建一个函数，如果您输入一个已经存在的数字，则该数字将添加到左子树中，而左子树被推下一个步骤。

则可以看到这

如果我们有一棵看起来像

        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;
}

谢谢您的帮助！

Answer 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);
            struct tree *newNode = new(data); // creating new node with the data
            newNode->left = temp; // newNode's left will point to the copied left tree
            tree->left = newNode; // and tree left will now points to newNode
        }
    }

    return tree;
}

让我知道它是否有效。愉快的编码:)