1

これは、BST をトラバースし、ルート ノードを含むすべてのノードを削除することになっています。しかし、最後に「ルートにはまだノードが残っています」というメッセージが表示されます。すべてのノードが削除されないのはなぜですか?

void deleteTree()
{   
    deleteNode(root);
    if(root->right)
        cout << "root still has a right node" << endl;
    if(root->left)
        cout << "root still has a left node" << endl;
    root = 0;

}   

void deleteNode(node *p) 
{   
    if(p->left) 
    {   
        deleteNode(p->left);
        p->left = 0;
    }   
    if(p->right) 
    {   
        deleteNode(p->right);
        p->right = 0;
    }   

    cout << "Deleting node containing " << p->data << endl;
    delete p;
}
4

5 に答える 5

6

p最後 ( ) で削除してから、割り当てられたメモリを指していない のroot内容にアクセスしようとしています。結果は未定義になります。deleteTree()root

于 2010-02-11T03:00:30.537 に答える
2

を削除していますroot。そして、コードはメモリがあった場所にアクセスしようとしています。

あなたはそこで未定義の動作の土地にうまく入っています。

于 2010-02-11T03:01:11.623 に答える
2

rootで削除した後は逆参照しないでくださいdeleteNode。デバッガーを使用して、root->leftが null でない理由を調べます。

于 2010-02-11T03:01:19.610 に答える
2

root->leftすでにルートを削除して、新しく割り当てられたブロックで使用できるようにした後を見ています。

于 2010-02-11T03:02:17.503 に答える
-1

ツリー自体を変更するだけです。その方が簡単に処理できます。

struct Node
{
  Node(data_type data): mLeft(), mRight(), mData(data) {}
  Node(const Node& rhs): mLeft(), mRight(), mData(rhs.mData)
  {
    if (rhs.mLeft.get()) mLeft.reset(new Node(*rhs.mLeft));
    if (rhs.right.get()) mRight.reset(new Node(*rhs.mRight));
  }
  Node& operator=(Node rhs)
  {
    this->swap(rhs);
    return *this;
  }
  ~Node() { }

  void swap(Node& rhs)
  {
    using std::swap;
    swap(mLeft, rhs.mLeft);
    swap(mRight, rhs.mRight);
    swap(mData, rhs.mData);
  }

  Node* left() const { return mLeft.get(); }
  void left(std::auto_ptr<Node> node) { mLeft= node; }

  Node* right() const { return mRight.get(); }
  void right(std::auto_ptr<Node> node) { mRight = node; }

  data_type& data() { return mData; }
  const data_type& data() const { return mData; }

private:
  std::auto_ptr<Node> mLeft;
  std::auto_ptr<Node> mRight;
  data_type mData;
};

オブジェクト指向であることにより、各ノードは処理するメモリを担当するようになりました。また、std::auto_ptrインターフェイスで使用すると、所有権を取得することが明確になります。

ディープコピー、その他の必要なアプローチ、boost::shared_ptrまたは同等のものに合わせて調整されていることに注意してください。はいstd::auto_ptr、あなたは自分でコピーする必要があります。そこには魔法はありません。

C-structこの設計は、誰もがリソースを操作できるプレーンを使用するよりもはるかにクリーンです。アクセサーを介して基になるデータに完全にアクセスできます...ただし、未定義の動作を呼び出さないように注意してください...

もちろん、クラッシュさせることもできます:

Node& node = ...
delete node.left(); // haha

しかし、C++ が意図しない問題から保護する可能性がある場合、悪意のあるコードへの扉が開かれたままになります。

于 2010-02-11T13:22:01.547 に答える