我正在处理AVL树。看来我的删除有时只能正常工作。我建了一棵像这样的树
f
/ \
e j
/ / \
a h s
通过按顺序
f e h s j a
插入。我知道它在插入和平衡方面工作正常。当我删除
a
或j
或h
或s
或e
时,一切正常。如果我删除f
,那么它将用f
替换h
,这是正确的,但是我丢失了j
和s
。这是第一个被调用的函数。
void remove(const ItemType& item)
{
if(root == NULL)
return;
else
{
remove(root, item);
}
};
第一个函数调用此函数以递归方式找到正确的节点。
void remove(Node<ItemType>* & node, const ItemType& item)
{
if(item > node->item)
{
if (node->rightChild == NULL)
{
return; // there is nothing here to remove
}
else
{
// recurse to next node
remove(node->rightChild, item);
}
}
else if (item < node->item)
{
if (node->leftChild == NULL)
{
return; // there is nothing here to remove
}
else
{
// recurse to next node
remove(node->leftChild, item);
}
}
else if (node->item == item)
{
remove(node);
}
if (node != NULL)
node->updateHeight();
};
这是最后一个要调用的函数。在此完成删除和交换。
void remove(Node<ItemType>* & node)
{
if (node->rightChild == NULL && node->leftChild == NULL)
{
delete node;
node = NULL;
}
else if (node->rightChild == NULL)
{
Node<ItemType>* temp = node;
node = node->leftChild;
delete temp;
}
else
{
Node<ItemType>* & temp = node->rightChild;
while (temp->leftChild != NULL)
temp = temp->leftChild;
node->item = temp->item;
delete temp;
temp = NULL;
}
if(node != NULL)
node->initializeHeight();
};
我想知道这是否与线条有关
Node<ItemType>* & temp = node->rightChild;
while (temp->leftChild != NULL)
temp = temp->leftChild;
node->item = temp->item;
delete temp;
temp = NULL;
并且临时指针正在执行我不熟悉的行为,或者如果我的整个实现是错误的。我知道丢失的节点在某个地方,因为我的内存泄漏显示出丢失的两个节点从未删除。
最佳答案
是。 Node<ItemType>* & temp = node->rightChild;
说temp
是node->rightChild
的别名。因此,while
循环修改node->rightChild
,您将失去原来的正确子项的句柄。
拿一个普通的指针,沿着正确的子树向下走,直到到达最小成员的父节点为止。然后获取最小成员的值,将其复制到node->item
,并删除父级的左 child 。
关于c++ - 简单的AVL树删除有时仅适用,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/15773705/