0

私は次のコードを持っています：

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Node
{
    int value;
    Node *left, *right;
    Node(int value, Node *l = NULL, Node *r = NULL)
    {
        this->value = value;
        left = l;
        right = r;
    }
};
struct BST
{
    Node *root = NULL;
    void insert(int value)
    {
        cout<<"Inserting: "<<value<<endl;
        Node **current = &root;
        while(*current != NULL)
        {
            if(value >= (*current)->value)
            {
                current = &((*current)->right);
            }
            else current = &((*current)->left);
        }
        (*current) = new Node(value);
    }
    void remove(int value)
    {
        Node *toRemove = search(value);
        remove(toRemove);
    }
    void remove(Node *toReplace)
    {
        if(toReplace == NULL) return;
        Node *toBeReplacedWith = NULL;

        if(toReplace->left == NULL && toReplace->right == NULL)
        {
            delete toReplace;
            toReplace = NULL;
            return;
        }
        if((toReplace->left == NULL) ^ (toReplace->right == NULL))
        {
            if(toReplace->left != NULL) toBeReplacedWith = toReplace->left;
            else toBeReplacedWith = toReplace->right;
            copyAndDeleteNode(toReplace, toBeReplacedWith);
            return;
        }
        Node *current = toReplace->left;
        while(current->right != NULL) current = current->right;
        toReplace->value = current->value;
        remove(current);
    }
    Node* search(int value)
    {
        Node *current = root;
        while(current != NULL && current->value != value)
        {
            if(current->value > value) current = current->left;
            else current = current->right;
        }
        if(current == NULL)
        {
            cout<<"The node didn't exist in the BST";
        }
        return current;
    }
    void traverse()
    {
        rec_traverse(root);
    }
private:
    void copyAndDeleteNode(Node *toReplace, Node *toBeReplacedWith)
    {
        toReplace->value = toBeReplacedWith->value;
        toReplace->left = toBeReplacedWith->left;
        toReplace->right = toBeReplacedWith->right;
        delete toBeReplacedWith;
        toBeReplacedWith = NULL;
    }
    void rec_traverse(Node * current)
    {
        if(current == NULL) return;
        rec_traverse(current->left);
        cout<<current->value<<endl;
        rec_traverse(current->right);
    }
};
int main()
{
    BST tree;
    for(int i = 0; i < 10; ++i)
    {
        tree.insert(i);
    }
    Node  *a = tree.search(6);
    cout<<"found val: "<<a->value<<endl;

    tree.remove(5);
    tree.remove(9);
    tree.remove(2);
   // tree.insert(4);
    //tree.insert(15);
    tree.insert(6);
    tree.insert(22222);
    cout<<"Traversing:\n";
    tree.traverse();
    return 0;
}

何らかの理由で、実行時にプログラムがクラッシュしinsert(22222)ますが、以前の呼び出しには問題がなく、その理由がわかりません。問題は 26 行目から 30 行目の間にあるはずです。私は常に Node コンストラクターに NULL 値を入れているので、ループが壊れない理由がわかりません。

4

1 に答える 1

1

すぐに間違っていることの1つはこれです：

remove(Node* toReplace).

ポインターを値で渡しているため、その関数は Node ポインターを更新しません。何らかの方法でポインターを変更するその関数内のすべてのコードは、戻るtoReplaceとすぐに破棄されremoveます。

たとえば、次の行です。

delete toReplace;
toReplace = NULL;

これdeleteは完了しましたが、ポインタを NULL に設定しても何も起こりません。繰り返しますが、これtoReplaceはローカル変数です。

プロトタイプを次のように変更する必要があります。

remove(Node *& toReplace).

ポインターへの参照を渡すと、ポインター値を更新して呼び出し元に反映できるようになりました。

また、'9' のリーフ ノードを削除した後、ツリーの状態を確認していません。これを行った場合、'8' の新しいリーフ ノードの "右" ポインターが正しくないことがはっきりとわかるはずです。これにより、8 より大きいノード (22222) を追加しようとすると、あらゆる種類の問題が発生します。

あなたのremove機能はここで間違っています：

    if(toReplace->left == NULL && toReplace->right == NULL)
    {
        delete toReplace;
        toReplace = NULL;
        return;
    }

これで、ノードが削除されました (「9」ノードであると仮定します)。では、'9' を指していたノードはどうなるでしょうか? NULL を指すように右 (または左) ポインターを調整していません。そこから問題が始まります。

これらはすべて、ツリーを見て各操作の後でも正しいかどうかを確認するだけで検出できたはずです。デバッガーを使用したり、各段階でツリーの状態を出力したりすることもできます。

最後に、ツリー構造体にはデストラクタがありません。メモリを割り当てますが、割り当てが解除される場所はありません。

編集：

この行は何をすることになっていますか？より具体的には、それは何をする^ことになっていますか？

if((toReplace->left == NULL) ^ (toReplace->right == NULL))
于 2014-07-09T16:26:07.503 に答える