1

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

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”都带有下划线，并给出错误“错误：预期声明”。我不知道这是怎么回事，非常感谢您的反馈！

4

1 回答 1

0

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

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

  2. ptr->数据（）=最大值；我猜您的“data()”方法返回对 Item 中成员的引用。没有错，就是感觉怪怪的。

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

  4. 在这个部分：

    while (ptr != NULL) {

    prev = ptr;
    ptr = ptr->right();
}
delete ptr;

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

于 2012-12-05T02:43:00.990 回答