Pourquoi mon code C ++ ne parviennent pas à supprimer tous les nœuds dans mon BST?

Question

Ceci est censé traverser un BST et supprimer tous les noeuds, y compris le nœud racine. Cependant, à la fin, je reçois le message « racine a toujours un nœud gauche. » Pourquoi ne sont pas tous les nœuds supprimés?

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

Votre supprimons p à la fin (root), puis essayer d'accéder à son contenu dans deleteTree(), où root ne pointe plus à la mémoire allouée. Le résultat va être indéfini.

Answer 2

vous supprimez root. Et puis votre code tente d'accéder à la mémoire où il était.

Vous êtes bien en terre un comportement non défini il.

Answer 3

Vous ne devriez pas déréférencer root après avoir supprimé dans deleteNode. Utilisez un débogueur pour inspecter pourquoi root->left est non nulle.

Answer 4

Vous regardez root->left après que vous avez déjà supprimé la racine, le rendant disponible pour une utilisation dans un nouveau bloc alloué.

Answer 5

Je voudrais simplement changer l'arbre lui-même, il serait plus facile de traiter avec elle alors:

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

En étant orienté objet, chaque nœud est maintenant responsable de la mémoire qu'il gère. De plus, en utilisant std::auto_ptr dans l'interface, il est clair qu'il faut la propriété.

Notez qu'il a été adapté pour-copie en profondeur, toute autre approche nécessitant boost::shared_ptr ou équivalent. Et oui std::auto_ptr vous laisse traiter la copie par vous-même, pas de magie là.

Cette conception est beaucoup plus propre que d'utiliser un C-struct simple avec tout le monde étant en mesure de manipuler les ressources. Vous avez toujours accès aux données sous-jacentes via l'accesseur ... mais ils prennent soin de ne pas invoquer un comportement non défini ...

Bien sûr, vous pouvez toujours tomber en panne vers le bas:

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

Mais si C ++ peut protéger contre les problèmes involontaires, il laisse la porte ouverte au code mal.