Pourquoi mon code C ++ ne parviennent pas à supprimer tous les nœuds dans mon BST?
-
19-09-2019 - |
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;
}
La solution
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.
Autres conseils
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.
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.
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é.
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.