Warum funktioniert mein C ++ Code nicht alle Knoten in meinem BST löschen?

Question

Das soll ein BST zu durchlaufen und jeden Knoten, einschließlich der Root-Knoten löschen. Doch am Ende, bekomme ich die Meldung „root noch einen linken Knoten hat.“ Warum sind nicht alle Knoten gelöscht?

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;
}   

Answer 1

Sie löschen p am Ende (root) und dann zu versuchen, seinen Inhalt in deleteTree() zuzugreifen, wo root nicht mehr auf zugewiesenen Speicher. Das Ergebnis wird sich nicht definiert werden.

Answer 2

Sie löschen root. Und dann wird der Code für den Zugriff Speicher versuchen, wo es war.

Sie sind gut in undefined-Verhalten Land gibt.

Answer 3

Sie sollten nicht dereferenzieren root, nachdem Sie es in deleteNode löschen. Verwenden Sie einen Debugger zu untersuchen, warum root->left nicht null ist.

Answer 4

Sie betrachten root->left, nachdem Sie bereits root gelöscht haben, ist es für den Einsatz in einem neuen zugeordneten Block zu machen.

Answer 5

Ich würde einfach den Baum selbst ändern, wäre es einfacher, damit umzugehen, dann:

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;
};

Durch die objektorientierte, ist jeder Knoten nun verantwortlich für die Speicher es abwickelt. Außerdem macht es mit std::auto_ptr in der Schnittstelle klar, dass es übernimmt den Besitz.

Beachten Sie, dass es für Tief Kopieren zugeschnitten worden ist, anderer Ansatz erfordert boost::shared_ptr oder gleichwertig. Und ja std::auto_ptr Blättern Sie mit dem Kopieren von selbst zu tun, keine Magie gibt.

Dieser Entwurf ist viel sauberer als die Anwendung eines einfachen C-struct mit jedem den Ressourcen manipulieren zu können. Sie haben noch vollen Zugriff auf die zugrunde liegenden Daten über die Accessor ... aber sie kümmern sich nicht undefiniert Verhalten ...

aufzurufen

Natürlich können Sie es immer noch abstürzen:

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

Aber wenn C ++ gegen unbeabsichtigte Probleme schützen kann, es läßt die Tür offen für bösen Code.