我正在编写一个函数,该函数将从具有与之关联的给定键的二叉搜索树中删除一个条目。到目前为止,我的代码有这个:
template <typename Item, typename Key = Item>
bool BSTree<Item,Key>::remove(const Key& key) {
bool removed = false;
Node* ptr = root;
if(ptr == NULL)
return removed;
while(key != ptr) {
if(ptr == NULL)
return removed;
else if(key > ptr)
ptr = ptr->right();
else
ptr = ptr->left();
}
removed = true;
Item max = max(ptr);
ptr->data() = max;
Node* prev = ptr;
while (ptr != NULL) {
prev = ptr;
ptr = ptr->right();
}
delete ptr;
if (prev->left() != NULL)
prev = copy(prev->left());
delete prev;
return removed;
}
Copy 是我已经编写的另一个函数,它将使用递归方法将所有值从某个节点传输到树的末尾。我相信此功能应该有效,但我不完全确定并希望得到一些反馈。
函数的最后三行也有问题。在它们每个中,“if”、“delete”和“return”都带有下划线,并给我错误“Error: expected a declaration”。我不知道这是怎么回事,非常感谢反馈!
最佳答案
恕我直言,我看到了几件事。
对于 BST 移除,你需要一个更好的移植方法,而不是你的“复制”,至少你应该找到与要移除的节点相比的下一个最小节点。
ptr->data() = max;我猜您的“data()”方法返回对 Item 中成员的引用。没有错,就是感觉怪怪的。
你有两个“删除”语句,但你不是应该只删除一个项目吗?
在本节中:
while (ptr != NULL) { prev = ptr; ptr = ptr->right(); } delete ptr;
while 退出后,ptr 的值为NULL,所以你在删除一个NULL,不酷。
关于c++ - 从二叉搜索树中删除一个值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13715241/