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