二叉搜索树的插入功能有问题

约翰·多伊

我正在使用递归函数将一个节点插入到我的二叉搜索树中。如果没有根节点，该程序通过创建一个根节点来工作。Root 是指向节点结构的指针。如果根已经存在，我调用工作函数。

注意： Key 为 int，Item 为字符串。

当调用工人功能，current->key(-858993460)而current->item(Error reading characters of string)不是他们的预期values (1, "Harrold")。

递归继续，直到发生此异常：

"Exception thrown: read access violation. current was 0xCCCCCCCC."

Key k和Item i是他们的期望值。这只是我试图从Node*root访问它们的原因，它们会改变，我不确定为什么会发生这种情况。

任何帮助表示赞赏

void BST::insert(Key k, Item i)
{
    if (root == nullptr) {
        root = &Node(k, i);
    }
    else insertRec(k, i, root);
}

void BST::insertRec(Key k, Item i, Node* current)
{

    if (current->key == k)//if the key of the inserted node is = to an existing key, change the item.
    {
        current->item = i;
    }
    else if (current->key > k)//if the key of the current node is larger than key inserted traverse leftchild recursively calling function
    {
        if (current->leftChild != nullptr)
            insertRec(k, i, current->leftChild);
        else
            current->leftChild = &Node(k, i);
    }
    else if (current->key < k)
    {
        if (current->rightChild != nullptr)
            insertRec(k, i, current->rightChild);
        else
            current->rightChild = &Node(k, i);
    }
}

保罗·麦肯齐

您现在为树创建新节点所做的是实例化一个临时Node对象，然后存储该对象的地址。这就是&Node(k, i)正在做的事情。

问题是临时文件将超出范围，并且您的 BST 现在包含Node指向不存在内容的指针。这更有可能是您的程序因无效地址错误而停止的原因。

所以代替

&Node(k,i),

用

new Node(k, i).

这会动态分配一个 new Node，使指向此Node“棒”的指针不是临时的。

当然，当需要销毁树时，您负责为 BST 释放内存。那是您需要遍历树节点并调用delete每个Node.

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。