0

CLRSの疑似コードを参考に二分探索木のdeleteメソッドを実装しました。以下はバグのある実装です。最初にリーフ ノードを削除すると機能しますが、ルート ノードを削除するとコードが失敗します。具体的には - 新しいルート ノードの値は移植メソッドで取得されますが、delete_node メソッドでは古いノード値が再び表示されます。誰かがエラーを指摘してください。前もって感謝します。

class bst {
    public:
        struct node
        { 
            int data;
            struct node* ltson;
            struct node* rtson;
            struct node* parent;
        }*btroot;

        // replaces the subtree rooted at node u with the subtree rooted at node v

        void transplant(bst T, struct node* u, struct node *v) {
            if(u->parent==NULL){
                T.btroot = v;
            }
            else if(u->parent->ltson == u)
                u->parent->ltson = v;
            else 
                u->parent->rtson = v;
            if(v!=NULL)
                v->parent = u->parent;
        }

        void delete_node(bst T,struct node* z) {
            struct node * y;

            if(z->ltson==NULL)
                transplant(T,z,z->rtson);
            else if(z->rtson==NULL)
                transplant(T,z,z->ltson);
            else {
                y = minimum(z->rtson); 

                if(y->parent!=z) {
                    transplant(T,y,y->rtson);
                    y->rtson = z->rtson;
                    y->rtson->parent = y;
                }
                transplant(T,z,y);
                cout<< (T.btroot->data)<<endl; //Old value of root is being printed
                y->ltson = z->ltson;
                y->ltson->parent = y;
            }
        }
};
4

1 に答える 1

0

バイナリ ツリーをトラバースする while ループまたはイテレータが欠落していると思います。これにより、削除する必要があるノードが検索され、現在の位置に関係なく削除されます。

于 2013-07-22T18:06:35.910 に答える