0

削除機能に問題があります。何が問題なのかわかりません。これを修正するのを手伝ってください。どうもありがとうございます。

node* tree_minimum(node *x){

    while(x->left!=NULL){
        x=x->left;
    }
    return x;
}

node* tree_successor(node *x){

    if(x->right!=NULL)
        return tree_minimum(x->right);

    node *y;
    y=new node;
    y=x->parent;

    while(y!=NULL&&x==y->right){
        x=y;
        y=y->parent;
    }
    return y;
}

node* tree_search(node* x,int k){

    if(x==NULL||k==x->key)
        return x;

    if(k<x->key)
        return tree_search(x->left,k);
    else
        return tree_search(x->right,k);
}

node* tree_delete(int b){

    node *y;
    y=new node;
    node *x;
    x=new node;
    node *z;
    z=new node;

    z=tree_search(root,b);

    if(isempty()){
        cout<<"TREE is empty.";
        return NULL;
    }

    if(z->left==NULL||z->right==NULL)
        y=z;
    else
        y=tree_successor(z);

    if(y->left!=NULL)
        x=y->left;
    else
        x=y->right;

    if(x!=NULL)
        x->parent=y->parent;
    if(y->parent==NULL)
        root=x;
    else{

    if(y=y->parent->left)
        y->parent->left=x;
    else
        y->parent->right=x;
    }
    if(y!=z)
        y->key=z->key;

    return y;
}
4

1 に答える 1

3

残念ながら、ここで多くの問題が発生しています。メモリ割り当てを誤解していると思います：

node *y;
y=new node;
y=x->parent;  // Holy Mackerel!

2 行目にメモリを割り当て、新しく割り当てられたメモリにアドレスを返します。次の行で、y が指していたアドレスが変更されます (!!) - 割り当てられたメモリ ロケーションが失われ、メモリ リークが発生します。これらはコード全体に散らばっており、main()呼び出しを示すコードがないか、コードがないため、続行する必要はあまりありません。

ポインタをコピーするだけの場合は、動的割り当て (つまり、new演算子) を実行する必要はありません。

int *x = new int;
int y = 2;
*x = 1;  // Assigns the memory (int) pointed to by x to 1
x = &y;  // Reassigns x to point to y - but without delete the allocated memory's last reference is lost

先に進む前に、本を手に入れることを強くお勧めします。

編集:次のような条件にも注意してください:

if (y=y->parent->left)

あなたがおそらく意味したとき：

if (y == y->parent->left)

BSTロジックは凝縮する必要があります -次のような SOに関するいくつかの投稿をチェックしてください:

二分探索木の実装

于 2013-03-13T13:22:23.070 に答える