Comment supprimer un arbre de recherche binaire de la mémoire?

Question

J'ai un BST qui est une liste liée en C++. Comment est-ce que je supprimerais le tout de la mémoire? Serait-ce fait à partir d'une fonction de classe?

Answer 1

Effectuez une traversée post-commande de l'arborescence (c'est-à-dire en visitant les enfants avant les parents) et supprimez chaque nœud lorsque vous le visitez.

Que cela ait ou non quelque chose à voir avec les classes dépend entièrement de votre implémentation.

Answer 2

Avec peu d'informations fournies ....

Si vous avez attribué les noeuds avec de nouveaux ou malloc (ou fonctions connexes) que vous devez traverser sur tous les nœuds et libres ou les supprimer.

Une alternative est de mettre shared_ptr's (and weak_ptr's to kill cyclics) dans vos allocations - à condition que vous le faites correctement, vous ne devez libérer les nœuds manuellement

Si vous avez utilisé une implémentation de la qualité que vous avez pris sur Internet que prévu la les classes ne fuient pas, vous n'avez pas à vous soucier de quoi que ce soit.

Answer 3

Il suffit de supprimer les enfants:

struct TreeNode { 
    TreeNode *l, *r, *parent; 
    Data d; 

    TreeNode(TreeNode *p) { l = nullptr; r = nullptr; parent = p; } 
    TreeNode(TreeNode const &) = delete; 
    ~TreeNode() { 
     delete l; // delete does nothing if ptr is 0 
     delete r; // or recurses if there's an object 
    } 
}; 

ou si vous utilisez unique_ptr ou un tel, qui est même pas nécessaire:

struct TreeNode { 
    unique_ptr<TreeNode> l, r; 
    TreeNode *parent; 
    Data d; 

    TreeNode(TreeNode *p) { l = nullptr; r = nullptr; parent = p; } 
    TreeNode(TreeNode const &) = delete; 
    ~TreeNode() = default; 
}; 

Answer 4

Utilisez des pointeurs intelligents et oublier.

Answer 5

Si vous avez accès à la liste liée elle-même, il est un morceau de gâteau:

// Making liberal assumptions about the kind of naming/coding conventions that might have been used... 
ListNode *currentNode = rootNode; 

while(currentNode != NULL) 
{ 
    ListNode *nextNode = currentNode->Next; 
    delete currentNode; 
    currentNode = nextNode; 
} 

rootNode = NULL; 

Si cela est un implemention personnalisé d'un BST, cela pourrait bien être la façon dont il fonctionne en interne, si elle a lié à une structure de données particulière.

Si vous n'avez pas accès à l'interne, la réponse de Potatoswatter devrait être sur place. En supposant que la BST est configurée comme ils le suggèrent, la simple suppression du nœud racine devrait supprimer automatiquement toute la mémoire allouée car chaque parent de l'arbre supprimera ses enfants.

Si vous demandez comment aller sur itérer à travers un arbre binaire manuellement, vous feriez l'étape récursive suivante:

void DeleteChildren(BSTNode *node) 
{ 
    // Recurse left down the tree... 
    if(node->HasLeftChild()) DeleteChildren(node->GetLeftChild()); 
    // Recurse right down the tree... 
    if(node->HasRightChild()) DeleteChildren(node->GetRightChild()); 

    // Clean up the data at this node. 
    node->ClearData(); // assume deletes internal data 

    // Free memory used by the node itself. 
    delete node; 
} 

// Call this from external code. 
DeleteChildren(rootNode); 

J'espère que je ne l'ai pas manqué le point ici et que quelque chose de ce aide.