0

削除機能を終了しようとしています。

擬似コードは次のとおりです。最後に注意してください。

ただし、疑似コードが間違っているかどうかはわかりません。

これが私がそれをどのように解釈したかです：

Node* minNode = Minimum(toDelete->right);

            int tmp = 0;
            tmp = minNode->val;
            // delete(&tmp);
            free(minNode);
            minNode=NULL;
            toDelete->val=tmp;

ただし、削除すると、印刷時に1兆のゼロが埋められます。

私がやっていることは理にかなっていますか？私が持っている残りのコードは正しいか、とにかくそうだと思います。このシナリオでは台無しになるだけです。

こちらも最低限の機能

Node* BST::Minimum(Node *curr) {

    // if (curr->left != NULL) {
    //      return(Minimum(curr->left));
    //  }
    //  return curr;
    Node* node = curr;
    while (node->left != NULL) {
        node = node->left;
    }
    return node;

}
4

1 に答える 1

1

これはひどい疑似コードで、一見正しくもないように見えます (これがBST示すように、これが二分探索木である場合は、丸で囲んだ部分が間違っています)。二分探索木については、インターネットで入手できるはるかに優れた情報があります。

いずれにせよ、右のサブツリーで最小の要素を見つけようとしています。これは、右のサブツリーの他のすべての要素よりも小さく、左のサブツリーの他のすべての要素よりも大きいためです。

あなたの最小機能は正しいようです。解放した後、minNode への参照を削除する必要があります。したがって(minNode->parent)->left、親ポインターがない場合は = NULL または少し面倒です。現在、それleftはメモリ内の空きスペースを指しているだけで、完全にランダムな動作につながります.

于 2012-12-11T18:10:25.403 に答える