二叉搜索树插入C++

Question

也许已经有很多人问过了，但我就是无法理解这里到底出了什么问题。我不想使用互联网上的代码，所以我只是试图编写我心中的想法。要么是我的打印函数有问题，要么就是下面的代码有问题。请问下面的代码有什么问题吗？

void addNode(int value)
    {
        Node* newNode=new Node;
        newNode->data=value;
        if(root==NULL)
            root=newNode;
        else {
            Node* temp=root,*parent;
            while(temp!=NULL)
            {
                parent=temp;
                if(temp->data == value)
                    return;
                else if(temp->data < value)
                    temp=temp->left;
                else 
                    temp=temp->right;
            }
            temp=newNode;
        }
    }

- Ali

---

你从未分配任何节点的“left”或“right”成员。 - Ken Dyck

我正在使用“temp=temp->left”和“temp=temp->right”。这不算吗？ - Ali

@rolandbishop：不会的；这会将你的本地变量更改为引用不同的节点，但是一旦找到插入点，你就不会修改树。 - Mike Seymour

Answer 1

temp=newNode;

这将指针分配给局部变量，当函数返回时，该变量被丢弃，从而丢失了新节点。相反，您希望将其分配给树内的指针；可能像这样：

if (temp->data < value) {        // If the new node should be to the left
    if (temp->left) {            //   If there is a left subtree
        temp = temp->left;       //      Move into the left subtree
    } else {                     //   Otherwise
        temp->left = newNode;    //      Insert the new node there
        return;                  //      Done.
    }
}

如果value < temp->data，则temp->right同样如此。

还有：

if (temp->data == value) 
    return;

你的代码有内存泄漏问题；在返回前应该删除newNode。

- Mike Seymour

---

我认为他也漏掉了在树的中间插入的情况。 - John Kalberer

谢谢你的回答。我可能有点困惑，所以这可能听起来很蠢，但我没有完全理解为什么要检查temp->left是否为'if(temp->left'。如果是NULL值，while循环不已经提供了吗？我的意思是，为什么你要用if语句来检查它呢？ - Ali

@JohnKalberer：平衡树是一种优化方法；最好先让基础功能正常工作。 - Mike Seymour

@rolandbishop：一旦找到空指针，主循环就会停止；但是您需要重新分配该指针以指向新节点，以将其添加到树中。通过我的更改，您将不需要在外部循环上进行测试；一旦找到插入点，您将返回。 - Mike Seymour

@MikeSeymour 非常感谢您，Mike！我刚刚实现了它并且它可以工作。然而，我仍然有一种奇怪的感觉，插入操作有一个更简单的解决方案。即使它完全合理，我也无法使用if语句。您能否推荐任何源，以展示迭代插入操作的实现？ - Ali