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

问题描述：

我正在使用递归函数将节点插入到二叉搜索树中。该程序通过创建根节点（如果没有根节点）来工作。 Root是一个指向节点struct的指针。如果root已经存在，我会调用worker函数。具有插入功能问题的二叉搜索树

注：键是int，Item是一个字符串。

当调用worker函数时，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*访问他们，他们改变了根，我不确定为什么会发生这种情况。

任何帮助表示赞赏

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); 
    } 
}

'current-> leftChild =＆Node（k，i）;' - 解释这个奇怪的线条是干什么的。将指针存储到临时目录（注定失败）的原因是什么？其次，请发布[mcve] – PaulMcKenzie

节点是一个结构体。它包含Int键，String项，Node * leftChild和Node * rightChild。 struct BST ::节点我在这里要做的是; 1 - 创建一个新节点。 2-将其创建为当前节点的右侧或左侧子节点，以便它具有父节点。 – JohnDoe

你试图做的是创建一个新的节点？你的书和许多例子展示了如何创建新对象？你正在做的是创建一个临时的。在C++中听说过'new'，或者更好的是'std :: unique_ptr '和'make_unique'？如果不是，那么在调用'insert'之前，您的整个现有BST不会正确构建。 – PaulMcKenzie

答

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

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

所以不是

&Node(k,i)，

使用

new Node(k, i)。

这动态分配一个新的Node，使指向此Node“指针”，而不是暂时的。

当然，当你需要销毁树时，你有责任为BST释放内存。那时你需要通过树节点并在每个Node上调用delete。

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

相关推荐