1

二分探索木の関数をまとめていて、壁にぶち当たりました。指定された値を保持しているノードをツリーから削除する必要がある場合に発生する可能性のある各状況に取り組んでいます。ノードに左右の子がない場合、ノードを解放する方法がわかりません。関数はノードを返す必要があります。バックアップして、左右の子をそれぞれ調べ、値が子にある間に値を削除しますか? しかし、値がルートにある場合、それを削除する方法について同様の問題が発生しませんか? 説明として、プログラムは void ポインタを使用し、別の関数 compare() で TYPE val をキャストします。この関数は両方の値を評価し、< の場合は -1、== の場合は 0、> の場合は 1 を返します。

struct Node *_removeNode(struct Node *cur, TYPE val)
{
    if (compare(cur->val, val) == 0) { //if val == cur->val
        if (cur->right != NULL && cur->left != NULL) { //if cur has right and left
            cur = _leftMost(cur->right);
            free(_leftMost(cur->right));
        }
        else if (cur->right == NULL && cur->left != NULL) {  //if cur has left
            cur = cur->left;
            free(cur->left);
        }
        else if (cur->right != NULL && cur->left == NULL){ //if cur has right
            cur = cur->right;
            free(cur->right);
        }
        else if (cur->right == NULL && cur->left == NULL){ //if cur has no child
                //free cur if cur = val

        }
    }
    else if (compare(cur->val, val) == -1) {
        cur->right = _removeNode(cur->right, val);
    }
    else if (compare(cur->val, val) == 1) {
        cur->left = _removeNode(cur->left, val);
    }

    return cur;
}
4

1 に答える 1

2

ノードに子がない場合は、単純に削除できます。他のケースで再帰を機能させるには、_removeNode から NULL を返す必要があります。いずれの場合も、cur は不要になったため、削除 (解放) する必要があります。いずれの場合も、置換サブツリーを返す必要があります。合併症は、右の子の最も左の子孫が引き上げられる最初のケースで発生します。引き上げた後、右のサブツリーから削除する必要があります (右のサブツリーである可能性があることに注意してください)。

以下のすべてを頭のてっぺんから書いたので、いくつかのエラー/少しのデバッグに備えてください。また、_leftMost と _removeLeftMost は少しの作業でマージできます。

問題のブロックは次のようになります。

    Node *replacement;
    if (cur->right != NULL && cur->left != NULL) { //if cur has right and left    
        replacement = _leftMost(cur->right);
        replacement->right = _removeLeftMost(cur->right,replacement);
        replacement->left = cur->left;
    }
    else if (cur->right == NULL && cur->left != NULL) {  //if cur has left
        replacement = cur->left;
    }
    else if (cur->right != NULL && cur->left == NULL){ //if cur has right
        replacement = cur->right;
    }
    else if (cur->right == NULL && cur->left == NULL){ //if cur has no child
        replacement = NULL;
    }
    free(cur);
    cur = replacement;

関数 _removeLeftMost は、置き換えられるノードが見つかるまで左の子ポインターをたどり、そのノードの右の子に置き換えます。何かのようなもの：

Node *_removeLeftMost(node, remove) {
    if (node == remove) {
       return node->right; // Note that remove->left should be null
    }
    else {
       node->left = _removeLeftMost(node->left,remove);
       return node;
    }
}

また、メインコールは次のようなものです

root = _removeNode(root, val);

これで、ノードがルートである場合の懸念が処理されます。

于 2013-02-19T19:19:17.080 に答える