c++ - 使用 C++ 插入 BST

Question

我创建了一个将数据插入 BST 的函数，它工作正常。我使用了“通过引用传递”，并且“head”的值应该在每次插入后改变。但是，我发现“head”总是指向我插入的第一个值。这里有人可以解释是什么原因导致“头”指向我插入的第一个数据吗？

void insert(node *&head, int val){
if(head == NULL){
    head = newNode(val);
}
else{
    if(val <head->data)
        insert(head->left,val);
    else
        insert(head->right,val);
}
}

Answer 1

这就是函数应该如何工作，head永远不应该改变，否则你将失去对树根的跟踪。

只要您head指向根，您就可以访问整个树。

值不变的原因是，当你在写insert(head->left,val);

您没有为 分配新值head，您只是将对左孩子的引用传递给下一个函数调用。

Answer 2

void insert(node *&head, int val){
if(head == NULL){
    head = newNode(val); // when you call insert() with pointer to root
                         // which is NULL this will create root node
}

然后当您将数据添加到根节点时（不再为 NULL）

else{ // this will be called and this doesn't create new root node
      // but just create nodes at its left or right side 
    if(val <head->data)
        insert(head->left,val);
    else
        insert(head->right,val);
}
}