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;
}

コピーは、再帰的アプローチを使用して、特定のノードからツリーの最後にすべての値を転送するだけの、私がすでに作成した別の関数です。この機能は機能するはずだと思いますが、完全にはわかりません。フィードバックを期待していました。

関数の最後の3行にも問題があります。それぞれに、「if」、「delete」、「return」に下線が引かれ、「エラー:宣言が必要です」というエラーが表示されます。私はこれで何が起こっているのか分かりません、そして本当にフィードバックをいただければ幸いです!

4

1 に答える 1

0

私見、いくつかのことがわかります。

  1. BSTを削除するには、「コピー」以外のより良い移植方法が必要です。少なくとも、削除するノードと比較して次に小さいノードを見つける必要があります。

  2. ptr->data() = max; 「data()」メソッドが Item のメンバーへの参照を返すと思います。間違いではありません、ただ奇妙に感じます。

  3. 「delete」ステートメントが 2 つありますが、アイテムを 1 つだけ削除することになっていませんか?

  4. このセクションで:

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

    while が終了すると、ptr の値は NULL になるため、クールではなく NULL を削除します。

于 2012-12-05T02:43:00.990 に答える