c++ - 从二叉搜索树中删除一个值

Question

我正在编写一个函数，该函数将从具有与之关联的给定键的二叉搜索树中删除一个条目。到目前为止，我的代码有这个:

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”。我不知道这是怎么回事，非常感谢反馈!

Answer 1

恕我直言，我看到了几件事。

1. 对于 BST 移除，你需要一个更好的移植方法，而不是你的“复制”，至少你应该找到与要移除的节点相比的下一个最小节点。

2. ptr->data() = max;我猜您的“data()”方法返回对 Item 中成员的引用。没有错，就是感觉怪怪的。

3. 你有两个“删除”语句，但你不是应该只删除一个项目吗？

4. 在本节中:

   while (ptr != NULL) {
   
       prev = ptr;
       ptr = ptr->right();
   }
   delete ptr;
   

   while 退出后，ptr 的值为NULL，所以你在删除一个NULL，不酷。