將重復數字添加到二叉搜索樹

所以我試圖為二叉搜索樹創建一個函式，如果你輸入一個已經存在的數字，這個數字會被添加到左子樹中，左子樹會被下推一步。

可視化這個

如果我們有一棵看起來像的樹

        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

以下是我到目前為止的代碼。

#include <stdio.h>
#include <stdlib.h>

typedef struct tree{
    int data;
    struct tree *left;
    struct tree *right;
} tree;

tree *new(int num){
    tree *temp = (struct tree *)(malloc(sizeof(tree)));

    temp->data = num;
    temp->left = NULL;
    temp->right = NULL;

    return temp;
}

tree *copy(tree *root){
    if(root == NULL){
        return NULL;
    }

    tree *newnode = new(root->data);
    
    newnode->left = copy(root->left);
    newnode->right = copy(root->right);

    return newnode;
}


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

void print(tree *root){
    if(root == NULL){
        return;
    }
    print(root->left);
    printf("%d ", root->data);
    print(root->right);
}

int main(){

    tree *root = NULL;

    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 6);
    root = insert(root, 9);
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 3);

    print(root);

}

謝謝你的幫助！

旁注：我也嘗試過這樣的插入功能版本，沒有復制功能。

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 = tree->left;
            
            tree->left->data = data;

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

    return tree;
}

但是這個版本將重復后的每個數字都變成了這樣的數字：

            5
          /   \
         3     6
        / \     \
       3   4     9
      /
     3
    /
   3

uj5u.com熱心網友回復：

嘗試以下版本的插入功能。為了您的方便，我添加了評論。希望你會明白。

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

讓我知道它是否有效。快樂編碼:)

標籤：C 二叉树 二叉搜索树

上一篇：EXC_BAD_ACCESS(code=259)當我在arm64上開發我的協程時

下一篇：如何從CoreFoundationCFDataRef中獲取最左邊的位？