バイナリ検索ツリーに挿入未処理の例外がスローされました

bugfix> c++ > 投稿

バイナリ検索ツリーにノードを挿入する機能があります。ノードを挿入しようとするとクラッシュします。 VSのデバッガーを使用すると、未処理の例外がスローされたことが示されます。書き込みアクセス違反です。 m_fatherはnullptrでした。

挿入する関数は次のとおりです。

NOD *INSERT(NOD k)
{
    NOD *temp = new NOD(k);
    NOD *m_father = NULL;
    NOD *x = root;
    while (x != NULL)
    {
        m_father = x;
        if (m_father->m_key > x->m_key)
        {
            x = x->m_right_child;
        }
        x = x->m_left_child;
    }
    if (root == NULL) 
        root = temp;
    else if (temp->m_right_child->m_key > m_father->m_key)
        {
            m_father->m_right_child = temp;
        }
    m_father->m_left_child = temp;
    temp->m_father = m_father;
    return 0;
}

そして、ここに私がノードを挿入しようとする方法があります：

int temp_nod;
cin >> temp_nod;
binary_tree.INSERT(temp_nod);

c++

tree

binary

回答 2 件

  • else if (temp->m_right_child->m_key > m_father->m_key)

    temp  ここでコピー構築されます（予想される動作ですか？）。新しいノードから作成された場合は、 m_right_child  まだ割り当てられていない可能性があるため、 nullptr を逆参照しようとします 。
    よくわかりませんが、あなたは temp をチェックしたかったです  ここのキー？ BSTで正しい場所を選択するときに、子キーをチェックする理由はあまりありません。

    また、コメントに記載されているように、m_father->を割り当てます left_child常に、条件なし。これは空のリストでも発生するため、再び nullptr を逆参照しようとします 。私はそれがこのように見えるはずだと思う：

    if (root == NULL) 
    root = temp;
else if (temp->m_right_child->m_key > m_father->m_key)
{
    m_father->m_right_child = temp;
    temp->m_father = m_father;
}
else
{
    m_father->m_left_child = temp;
    temp->m_father = m_father;
}

    補足として、関数が有用なものを何も返さない場合は、 void にしてください 。

  • root == NULL の場合   m_father への唯一の割り当て   NOD *m_father = NULL; になります 、ステートメント m_father->m_left_child = temp; の前 。

    編集：（ root == NULL の場合 、次に x  また NULL になります 、したがって、 while  ループは実行されません）

    EDIT2： else if (temp->m_right_child->m_key > m_father->m_key)  =>  m_father->m_left_child = temp;  -前者は root == NULL の場合は評価されません 、 else if であるため   if へ  それは本当でした。

あなたの答え

関連記事