c++ - C++ 中的二叉搜索树

Question

我有以下代码要插入到 bst 中，但是它无法插入除根节点之外的所有节点。知道我做错了什么吗？

class Node
{
public:
    int data;
    Node* right;
    Node* left;
    Node(int data)
    {
        this->data = data;
    }
    Node() {}
};

class BST
{
public:
    Node* head;
    void insert(int data)
    {
        if (head == nullptr)
        {
            head = new Node(data);
            head->data = data;
        }
        else
        {
            // head = new Node(data);
            insertNode(data, head);
        }
    }

    void insertNode(int data, Node* head)
    {
        if (head == nullptr)
        {
            head = new Node(data);
            return;
        }
        if (head)
        {
            Node* temp = head;
            if (temp->data > data)
            {
                insertNode(data, temp->left);
            }
            else if (temp->data <= data)
                insertNode(data, temp->right);
        }
    }
};

Answer 1

insertNode 中的参数head 隐藏了名为head 的成员变量。

但是，虽然这是一个非常糟糕的做法，但另一个答案才是您出错的真正原因，因此请改为选择他的答案(当然，一旦您开始使用它)。

我建议将 insertNode 的签名更改为

void insertNode(int data, Node*& node)

此外，您不需要在插入中检查 head == nullptr。您在 insertNode

中进行了重复检查

所以插入看起来像这样:

void insert(data) {
    insertNode(data, head);
}

最后，您没有在构造函数中初始化 head。 head 有可能被初始化为 nullptr 以外的东西，特别是如果你在 Release模式下编译它。添加这样的构造函数:

BST() : head(nullptr) {
    // Other init stuff here if necessary
}

您还需要使 Node* head 成为私有(private)数据成员而不是公共(public)数据成员。