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

bugfix> c++ > 投稿 2020-08-22 19:10

バイナリ検索ツリーにノードを挿入する機能があります。ノードを挿入しようとするとクラッシュします。 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 へそれは本当でした。

bugfix

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

c++

tree

binary

関連記事