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 回答