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() 获取指针的副本，因此在函数内部所做的更改不会影响树中的实际指针。你想要做的是引用指针：

void insertNode(int data, Node*& head)

Answer 2

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

然而，虽然这是一个非常糟糕的做法，但另一个答案是您错误的真正原因，所以请 select 他的答案代替（当然，一旦你开始工作）。

我建议将 insertNode 的签名更改为

void insertNode(int data, Node*& node)

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

中有重复检查

因此插入可能如下所示：

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

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

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

您还需要将 Node* head 设为私有数据成员而不是 public。

Answer 3

在您的函数“insertNode”中，您使用的是 if(head)，此 if 仅在 head == 1 时有效，并且 head 永远不会等于 1，因为它是一个指针，所以此 "if" 是不工作。！

C++ 中的二叉搜索树

Binary Search Tree in C++

c++

binary-search-tree