1

私は次のような二分探索木クラスを定義しています：

template <class T>
class BSTNode
{
  public:
    BSTNode(){
      right = left = 0;
    }

    BSTNode(const T& el, BSTNode * l = 0, BSTNode * r = 0)
    {
    val = el; left = l; right = r;
    }   

    T val;
    BSTNode * right;
    BSTNode * left;
};

template <class T>
class BST
{
  public:
    BST(){ root = 0;}           
    void Insert(const T& el);
  private:
    BSTNode<T> * root;
};

Insert()そして私はこのような関数を実装します：

template <class T>
void BST<T>::Insert(const T& el)
{
  bool bEqual = false;
  BSTNode<T> * p = root;

  while(p)
  {
    if(el == p->val)
    {
      bEqual = true;
      return;
    }
    if(el < p->val)
    {
      // go left
      p = p->left;
    }
    if(el > p->val)
    {
      // go right
      p = p->right;
    }
  }

  if(!p)
  {
    std::cout << "creating new node " << el << "\n";
    p = new BSTNode<T>(el);
  }  
}

root新しいオブジェクトのアドレスではなく、ポインタ変数が0のままになるのはなぜですか？

4

2 に答える 2

2

root = ?;あなたはあなたのコードで決してしません。また、p = new BSTNode<T>(el);メモリリークが発生します。

私の推測では、あなたはpポインタへの参照になりたかったので、元のポインタを変更することができます。

 BSTNode<T> *& p = root; // watch out, it won't solve anything

ただし、そのような場合、p再割り当てはできません。割り当てるポインタがnullかどうかを確認しp、新しい値を正しい場所（たとえばp->left = new BSTNode<T>(el);）に挿入し、指定さpれたポインタがnullでない場合にのみ再割り当てすることをお勧めします。

つまり：

template <class T>
void BST<T>::Insert(const T& el)
{
  bool bEqual = false;
  BSTNode<T> * p = root;

  if (p == 0)
  {
     root = new BSTNode<T>(el);
     return;
  }

  while(true)
  {
    if(el == p->val)
    {
      bEqual = true;
      return;
    }
    if(el < p->val)
    {
      if (p->left == 0)
      {
        p->left = new BSTNode<T>(el);
        return;
      }
      p = p->left;
    }
    if(el > p->val)
    {
      if (p->right == 0)
      {
        p->right = new BSTNode<T>(el);
        return;
      }
      p = p->right;
    }
  }
}
于 2012-04-14T16:44:15.537 に答える
1

オブジェクトの構築時のため

声明

  p= root

p を null ポインターとして初期化します。

新しいオブジェクトを作成し、そのアドレスを root ではなく p に渡します...

問題は、 p はルートの単なるコピーであり、このポインターへの参照ではありません..

于 2012-04-14T16:46:17.150 に答える