C++ BST插入

Question

我正在用C++实现一个BST，但是在我实现了insert函数之后，我发现我只能向树中插入一个节点。我尝试了很多方法来解决这个问题，但都没有成功...

这是我对插入函数的实现：

void BSTree::insertHelper(Customer* customer, Node* currentNode, Node* parent)
{
    if (currentNode == NULL)
    {
        Node* newNode = new Node(customer);

        currentNode = newNode;
        newNode->setParent(parent);

        return;
    }

    if (*customer < *currentNode->getCustomer())
        insertHelper(customer, currentNode->getLeft(), currentNode);
    else insertHelper(customer, currentNode->getRight(), currentNode);
}

bool BSTree::insert(string lastName, char initial, int account)
{
    Customer* customer = new Customer(lastName, initial, account);

    if (isEmpty())
    {
        Node* newNode = new Node(customer);

        root = newNode;

        return true;
    }

    Node* currentNode = root;
    insertHelper(customer, currentNode, NULL);

    return true;
}

感谢您的帮助。

Answer 1

你泄漏了内存。看这里 insertHelper:

if (currentNode == NULL)
{
    Node* newNode = new Node(customer);

    currentNode = newNode;
    newNode->setParent(parent);

    return;
}

currentNode 是局部变量。它仅存在于 insertHelper 内。因此，如果您分配给它，那么当您 return 时，它不会反映在函数之外。您传递父级，因此分配给其左侧或右侧成员：

newNode->setLeft(parent);
// or
newNode->setRight(parent);

C++ BST插入

C++ BST insertion

c++

recursion

insertion

binary-search-tree