BST插入值

Question

我很難讓插入功能正常工作。 cout聲明與我的作業不匹配。如果我嘗試插入5，我得到inserted: 5 right child of: 3，但應該是inserted: 5 right child of: 22有人可以幫我嗎？

Node* insert(Node *root, int value){ 
Node *tmp = root; 

while(tmp != NULL){ 
    if (tmp->key == value){ 
     return tmp; 
    } 
    else if (value > tmp->key){ 
     Node *tm = new Node(NULL, NULL, NULL); 
     tm->key = value; 
     tm->left = tmp->right; 
     tm->right = tmp->left; 
     tmp->right = tm; 
     cout << "inserted: " << tm->key << " right child of: " << tmp->key <<endl; 
     tmp = tmp->right; 
    } 
    else if (value < tmp->key){ 
     Node *tm = new Node(NULL, NULL, NULL); 
     tm->key = value; 
     tm->left = NULL; 
     tm->right = NULL; 
     tmp->left = tm; 
     cout << "inserted: " << tm->key << " left child of: " << tmp->key <<endl; 
     tmp = tmp->left; 

    } 
} 

return tmp; 

}

Answer 1

有幾個問題，您插入代碼：

• 你總是插入新節點爲根的孩子（這並不總是產生BST）
• 當你鏈接你的樹時，你或者（如果你作爲正確的孩子）使根的左邊孩子也是新節點的左邊孩子，或者（如果是左邊孩子）失去跟蹤原始左邊子樹的根。
• 如果根是NULL

下面的代碼應該爲你

//The following code assumes the following definition of Node 
struct Node { 
    Node(int val, Node* l, Node* r):key(val),left(l),right(r){} 
    int key; 
    Node* left; 
    Node* right; 
} 

// Returns the root of the tree after inserting val into tree (no duplicates) 
Node * insert (Node * root, int val){ 
    if (root == NULL) return new Node(val, NULL, NULL); 
    if (root->key == val) return root; 
    if (root->key > val) return insert(root->left, val); 
    return insert(root->right, val); 
} 

上述代碼定義插入遞歸工作會發生什麼。基本情況：樹是空的。插入新的值作爲根。如果根是密鑰，那麼你就完成了（沒有重複的密鑰）。否則，將該值插入左側或右側子樹（如果值小於root->鍵則爲左側，否則爲右側）。

或者您可以使用while循環迭代地定義插入。

Node * insert (Node * root, int val){ 
    // is this an empty tree? 
    if (root == NULL) return new Node(val, NULL, NULL); 

    Node* tmp = root; 
    while (tmp != null){ 
    if (tmp->key == val) break; 
    if (tmp->key > val){ 
     if (tmp->left == NULL){ 
     tmp->left = new Node(val, NULL, NULL); 
     break; 
     } else { 
     tmp = tmp->left; 
     } 
    } else { 
     if (tmp->right == NULL){ 
     tmp->right = new Node(val, NULL, NULL); 
     break; 
     } else { 
     tmp = tmp->right; 
     } 
    } 
    } 
    return root; 
} 

無論哪種情況，您都可以使用同樣的方式插入。

Node * tree1 = NULL; 
tree1 = insert(tree1, 3); 
tree1 = insert(tree1, 1); 
tree1 = insert(tree1, 2); 
tree1 = insert(tree1, 4); 

之後tree1將成爲下面的樹。

3 
/\ 
1 4 
\ 
    2