0

基本的に、プログラムはバイナリ ツリーの最初のノードを指す BST クラスで構成され、ノードも独自のクラスです。

BST はこのメンバー関数を呼び出します。

void remove(const T& x)
{
    removeNode(m_root, x);
    return;
}

そして、これは remove ノードの再帰部分であり、完了するまで実行されます。

template <typename T>
void removeNode(TreeNode<T>* &p, const T& x)
{
    if(p == NULL)
        return;

    if(x < p -> m_data)
        removeNode(p -> m_left, x);
    else if(x > p -> m_data)
        removeNode(p -> m_right, x);

    else
    {
        TreeNode<T>* tmp = new TreeNode<T>;

        if(p -> m_left == NULL)
        {
            tmp = p -> m_right;
            delete p;
            p = tmp;
        }
        else if(p -> m_right == NULL)
        {
            tmp = p -> m_left;
            delete p;
            p = tmp;
        }
        else
        {
            tmp = p -> m_right;
            TreeNode<T>* tmp2 = new TreeNode<T>;

            while(tmp -> m_left != NULL)
            {
                tmp2 = tmp;
                tmp = tmp -> m_left;
            }

            p -> m_data = tmp -> m_data;

            if(tmp2 != NULL)
                removeNode(tmp2 -> m_left, tmp -> m_left -> m_data);
            else
                removeNode(p -> m_right, p -> m_right -> m_data);
        }
    }

    return;
}

remove() 関数が戻ったときにセグ フォールトが発生しました。その理由を知りたいですか?

4

1 に答える 1

1

ユーザー @WhozCraig は、あなたのコードで最も重要なエラーを指摘しました。

TreeNode<T>* tmp = new TreeNode<T>;

TreeNode<T>* tmp2 = new TreeNode<T>;

後者の代入は条件を引き起こします

if(tmp2 != NULL)

常に満たされるため、実行できなくなります。

else
    removeNode(p -> m_right, ...)

ブランチ。

編集

キー 2、5、および 7 を持つ 3 ノード ツリーがあるとします。ノードnode2、node5およびnode7をそれぞれ示します。が木の根であるnode5とします。また、キー 5 を削除するとします。
次に、次のようにします。

  • *p == node5;
  • 最初の 3 つifの s が満たされず、制御がelseブランチに渡されます。
  • tmpが割り当てられp->m_rightます&node7。
  • tmp2新しい「空の」オブジェクトが割り当てられます-それを呼び出しましょうnodeEmpty;
  • node7子がないため、ループは反復なしでスキップされますtmp->m_left。NULLwhile
  • 割り当て命令p->m_data = tmp->m_dataによりnode5、キー 7 が取得されます。
  • そうでtmp2 == &nodeEmptyはありませんのでNULL、お電話で
    • removeNode(tmp2 -> m_left, tmp -> m_left -> m_data)

どうやら(?!)の存在しない左サブツリーから何かを削除しようとしているようですが... しかし、この時点では子がなく、. その結果、アクセスするとメモリ アクセス エラーが発生し、 への再帰呼び出しの前にプロセスがクラッシュします。nodeEmpty
tmp == &node7node7tmp->m_left == NULLtmp->m_left->m_dataremoveNode

于 2015-04-27T13:23:29.437 に答える