二进制搜索树的插入功能有问题 [英] Binary Search Tree having issues with insert function
问题描述
我正在使用递归函数将节点插入到我的二进制搜索树中.该程序通过创建根节点(如果没有)来工作.根是指向节点结构的指针.如果根目录已经存在，我将调用worker函数.
I'm using recursive functions to insert a node into my binary search tree. The program works by creating a root node if there is none. Root is a pointer to a node struct. If the root already exists I call the worker function.
注意:键是int，Item是字符串.
Note: Key is int and Item is a string.
在调用worker函数时，current->key(-858993460)和current->item(Error reading characters of string)不是他们期望的values (1, "Harrold").
When calling the worker function, current->key(-858993460) and current->item(Error reading characters of string) are not their expected values (1, "Harrold").
递归继续进行，直到发生此异常:
Recursion continues until this Exception occurs:
"Exception thrown: read access violation. current was 0xCCCCCCCC."
Key k和Item i是它们的期望值.只是为什么我尝试从Node*根目录访问它们，并且它们会更改，但我不确定为什么会发生这种情况.
Key k and Item i are their expected value. It is only why I'm trying to access them from Node* root that they change and I'm unsure why this is happening.
感谢您的帮助
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)的工作.
What you're doing now in creating new nodes for the tree is that you're instantiating a temporary Node object and then storing the address of that object. This is what &Node(k, i) is doing.
问题在于临时目录将超出范围，并且您的BST现在包含Node指针，该指针指向不存在的对象.更有可能是您的程序因无效的地址错误而停止的原因.
The problem is that the temporary will go out of scope, and your BST now contains Node pointers pointing to something that doesn't exist. That's more likely the reason your program stops with invalid address errors.
所以不是
&Node(k,i)，
使用
new Node(k, i).
这会动态分配一个新的Node，使指向该Node的指针粘住"，而不是临时的.
This dynamically allocates a new Node, making the pointer to this Node "stick" and not be temporary.
然后，当您要销毁树时，您当然要为BST分配内存.那是您需要遍历树节点并在每个Node上调用delete的时候.
Then of course, you're responsible for deallocating the memory for the BST when it's time to destroy the tree. That's when you need to go through the tree nodes and call delete on each Node.
这篇关于二进制搜索树的插入功能有问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
