segfault après le retour 0;

Question

J'ai écrit un programme pour tester mon arbre binaire et quand je l'exécute, le programme semble planter (btree.exe a cessé de fonctionner, Windows recherche une solution ...). Lorsque je l'ai exécuté dans mon débogueur et que j'ai placé le point d'arrêt sur la fonction que je soupçonne le provoquer, destroy_tree(), il semblait fonctionner comme prévu et est revenu à la fonction principale. Main, à son tour, est revenu du programme, mais le curseur est revenu à destroy_tree() et a bouclé recusively en lui-même.

L'exemple de code minimal est ci-dessous afin qu'il puisse être exécuté instantanément. Mon compilateur est MinGW et mon débogueur est gdb (j'utilise Code :: Blocks).

#include <iostream> 

using namespace std; 

struct node 
{ 
    int key_value; 
    node *left; 
    node *right; 
}; 

class Btree 
{ 
public: 
    Btree(); 
    ~Btree(); 
    void insert(int key); 
    void destroy_tree(); 

private: 
    node *root; 

    void destroy_tree(node *leaf); 
    void insert(int key, node *leaf); 
}; 

Btree::Btree() 
{ 
    root = NULL; 
} 

Btree::~Btree() 
{ 
    destroy_tree(); 
} 

void Btree::destroy_tree() 
{ 
    destroy_tree(root); 

    cout<<"tree destroyed\n"<<endl; 
} 

void Btree::destroy_tree(node *leaf) 
{ 
    if(leaf!=NULL) 
    { 
    destroy_tree(leaf->left); 
    destroy_tree(leaf->right); 
    delete leaf; 
    } 
} 

void Btree::insert(int key, node *leaf) 
{ 
    if(key < leaf->key_value) 
    { 
     if(leaf->left!=NULL) 
      insert(key, leaf->left); 
     else 
     { 
      leaf->left = new node; 

      leaf->left->key_value = key; 
      leaf->left->left = NULL; 
      leaf->left->right = NULL; 
     } 
    } 
    else if (key >= leaf->key_value) 
    { 
     if(leaf->right!=NULL) 
      insert(key, leaf->right); 
     else 
     { 
      leaf->right = new node; 

      leaf->right->key_value = key; 
      leaf->right->left = NULL; 
      leaf->right->right = NULL; 
     } 
    } 
} 

void Btree::insert(int key) 
{ 
    if(root!=NULL) 
    { 
     insert(key, root); 
    } 
    else 
    { 
     root = new node; 

     root->key_value = key; 
     root->left = NULL; 
     root->right = NULL; 
    } 
} 

int main() 
{ 
    Btree tree; 
    int i; 

    tree.insert(1); 

    tree.destroy_tree(); 

    return 0; 
} 

En aparté, je prévois de passer du Code :: Blocks Débogueur intégré à DDD pour le débogage de ces problèmes. J'ai entendu DDD peut afficher visuellement des pointeurs sur des objets au lieu d'afficher simplement l'adresse du pointeur. Pensez-vous que le fait de faire le changement aidera à résoudre ces types de problèmes (structure de données et problèmes d'algorithme)?

Answer 1

Votre destroy_tree() est appelé deux fois, vous l'appelez une fois et ensuite il est appelé après que l'exécution quitte Main() du destructeur.

Vous pensez peut-être que cela devrait fonctionner malgré tout, car vous vérifiez si leaf! = NULL, mais delete ne définit pas le pointeur sur NULL. Donc votre racine n'est pas NULL quand destroy_tree() est appelé pour la deuxième fois,

Answer 2

Non directement lié (ou peut-être c'est) à votre problème, mais c'est une bonne habitude de donner un constructeur à structs. Par exemple:

struct node 
{ 
    int key_value; 
    node *left; 
    node *right; 

    node(int val) : key_val(val), left(NULL), right(NULL) {} 
}; 

Si vous faites cela, votre code devient plus simple, parce que vous n'avez pas besoin vous inquiétez pas sur la définition des pointeurs lorsque vous créez un nœud, et il est impossible d'oublier de les initialiser. En ce qui concerne DDD, c'est un bon débogueur, mais franchement, le secret du débogage est d'écrire du code correct en premier lieu, donc vous n'avez pas à le faire. C++ vous donne beaucoup d'aide dans ce sens (comme l'utilisation de constructeurs), mais vous devez comprendre et utiliser les installations qu'il fournit.

Answer 3

Btree :: destroy_tree ne définit pas 'root' sur 0 après avoir nuambulé l'arborescence. Par conséquent, la classe destructor destroy_tree() à nouveau et vous essayez de détruire les objets déjà détruits.

Ce comportement sera indéfini alors :).

Answer 4

Une fois que vous détruisez la racine.
Assurez-vous qu'il est NULL il ne cherche pas à le faire à nouveau (de la destructor)

void Btree::destroy_tree(node *leaf) 
{ 
    if(leaf!=NULL) 
    { 
    destroy_tree(leaf->left); 
    destroy_tree(leaf->right); 
    delete leaf; 

    leaf = NULL; // add this line 
    } 
}