插入節點

我試圖寫一個函數來插入到二叉搜索樹中的節點，我有以下幾點：插入節點

typedef struct Node { 
    int key; 
    struct Node *left; 
    struct Node *right; 
} Node; 

Node *createNode(int key) 
{ 
    Node *newNode = (Node *)malloc(sizeof(Node)); 
    newNode->key = key; 
    newNode->left = NULL; 
    newNode->right = NULL; 

    return newNode; 
} 

Node *insert(Node *node, int key) 
{ 
    if (node==NULL) 
    { 
     node = createNode(key); 
    } 
    else 
    { 
     if (node->key > key) 
     { 
      node->left = insert(node->left, key); 
     } 
     else 
     { 
      node->right = insert(node->right, key); 
     } 
    } 
    return node; 
} 

int main(int argc, char* argv[]) 
{ 
    Node *root = NULL; 
    root = insert(root, 10); 

    return 0; 
}

我知道這個工作的，如果我想插入5到根節點root的樹，我可以寫root = insert(root, 5);。我的問題是，如何編寫insert的另一個版本，只需insert(root, 5);即可實現同樣的功能？我嘗試了以下但無濟於事。

void insert(Node *node, int key) 
{ 
    if (node==NULL) 
    { 
     node = createNode(key); 
    } 
    else 
    { 
     if (node->key > key) 
     { 
      insert(node->left, key); 
     } 
     else 
     { 
      insert(node->right, key); 
     } 
    } 
}

這是什麼問題，爲什麼不工作？任何指針（沒有雙關語意圖）將不勝感激！

來源

2015-11-15 Kevin Hsu

簡短的回答：沒有。有些情況下您需要更改root的值。（例如：樹爲空時，root爲NULL）一種方法是使用返回值的assignmnt（如在您的工作示例中）另一種方式是將指針傳遞給指針。（一個指向root的指針）。 – wildplasser

原因是，當你在BST中插入一個值時，你必須確保BST *仍然是一個BST，（例如，左邊的子節點包含值小於父節點的節點，右邊的子節點只包含節點值大於或等於父項）。這意味着您必須檢查插入時的幾個條件，並且您可能必須移動節點或葉節點（或根節點）以滿足BST約束條件。 –

對我來說，你的第一個解決方案是優雅的。

現在，如果你想插入而不利用返回值，那麼一種方法可能是使用指向指針的指針。

喜歡的東西：

void insert(Node ** node, int key) 
{ 
    if (*node == NULL) 
     *node = createNode(key); 
    else if ((*node)->key > key) 
     insert(&(*node)->left, key); 
    else 
     insert(&(*node)->right, key); 
}

和通話將

insert(&root, 10);

來源

2015-11-15 02:17:38 lrleon

回答

相關問題