1

これが私のNodeクラスです。

class Node
{
private:
public:
  T data;
  Node<T>* left;
  Node<T>* right;
  Node(T dat) : data(dat), left(NULL), right(NULL)
  {}
};

Btree クラスで定義された挿入関数は次のとおりです。

public:
  Node<T>* root;
  Btree() : root(NULL){}
  void insert(T data, Node<T>* parent)
  {   
      if( !parent  )
      {   
        parent = new Node<T>(data);
        return;
      }   
      else if(data < parent->data)
      {   
        insert(data, parent->left);
      }   
      else if(data > parent->data)
      {   
        insert(data, parent->right);
      }   
  }

};

これが私の主な機能です：

int main()
{
  Btree<int> tree;

  tree.insert(5, tree.root);

  cout << tree.root->data << endl;

  tree.insert(6, tree.root);

  cout << tree.root->right->data << endl;

}

実行すると、セグフォルトが発生します。

ポインター変数の親が値渡しされているためだと思うので、親が指す新しいノードを作成すると、挿入関数を終了すると失われますか? ここでダブルポインターを使用する必要があるということですか?

これが計画どおりに機能しない原因となっているメモリ内で何が起こっているかについて、誰かが完全な説明をしてくれませんか。ここで私の診断は正しいですか、それとも他に何か問題がありますか?

挿入する 2 番目のパラメーターとして tree.root を渡すと、Node* が渡されます。さて、値で渡されたとしても、呼び出し元のメイン関数から渡したアドレスと同じではないでしょうか。したがって、parent (メインの tree.root から渡したアドレス) = new Node と言うと、ヒープ上に、parent のアドレス、別名 tree.root のアドレスに新しい Node を作成するべきではありませんか? なぜ値渡しがこれを混乱させるのですか?

4

3 に答える 3

2

この場合の値渡しの問題は、関数内の仮引数に行われたすべての割り当てが呼び出し元から見えないことです。したがって、この割り当て

if( !parent  )
{   
    parent = new Node<T>(data); // <<== HERE
    return;
}

tree.root呼び出し元の には影響しません:

tree.insert(5, tree.root);

parent関数内のポインターの値が変更され、すぐに破棄されます。木のroot残骸NULL。

この問題を解決するには、次のようにポインターをポインターに渡します。

void insert(T data, Node<T>** parent) {
    if( !*parent  )
    {
        *parent = new Node<T>(data);
        return;
    }
    else if(data < (*parent)->data)
    {
        insert(data, &((*parent)->left));
    }
    else if(data > (*parent)->data)
    {
        insert(data, &((*parent)->right));
    }
}
于 2012-07-14T23:26:37.150 に答える
2

C++ は値渡しなのでparent、渡されたポインターのコピーです。したがって、それに割り当てても永続的な効果はありません。これを修正する最も簡単な方法は、ポインターへの参照を受け入れるようにメソッドのシグネチャを変更することです。これにより、コンパイラーは元のポインターを自動的に更新し、残りのプログラムを変更する必要がなくなります。

于 2012-07-14T23:27:09.080 に答える
1

dasblinkenlight さんが最もよく答えました。しかし、より簡潔な解決策があります。

ポインターの参照を取得します (ポインターへの参照と呼ばれます)。

void insert(T data, Node<T>*& parent)
  {   
      if( !parent  )
      {   
        parent = new Node<T>(data);
        return;
      }   
      else if(data < parent->data)
      {   
        insert(data, parent->left);
      }   
      else if(data > parent->data)
      {   
        insert(data, parent->right);
      }   
  }

詳細はこちら: http://www.codeproject.com/Articles/4894/Pointer-to-Pointer-and-Reference-to-Pointer

于 2012-07-14T23:39:32.220 に答える