suppression récursive sur un arbre binaire
Je suis en train d'essayer de comprendre comment la méthode récursive de la suppression d'un arbre de recherche binaire fonctionne. Le code que j'ai trouvé dans de nombreux endroits, se présente comme suit:
void destroy_tree(struct node *leaf)
{
if( leaf != 0 )
{
destroy_tree(leaf->left);
destroy_tree(leaf->right);
free( leaf );
}
}
Je ne comprends pas cependant a) comment ça fonctionne si il y a pas de retour dans la routine? b) lors de la free() peut être appelé? Je pense, par exemple, un tel arbre:
10
/ \
6 14
/ \ / \
5 8 11 18
Si ma compréhension est que je traverse 10->6->5, puis-je appeler destroy_tree(5->gauche). Par conséquent, la feuille à l'intérieur si la valeur est NULL, et ce qui est si dépendante n'est pas exécutée, donc 5 n'est pas supprimé. Où dois-je faire d'erreur dans ce raisonnement? Comment enroulement et le déroulement du travail ici? Toute aide bien appréciés 🙂
OriginalL'auteur Simon Righley | 2013-06-18
Vous devez vous connecter pour publier un commentaire.
Il ressemble à ce à ce point:
Rien n'est requis pour le retour... "l'histoire" des étapes est sur la pile d'appel, qui ressemble à quelque chose comme ça à ce point:
Donc après leaf_5 est parti, il remonte haut de la pile et ne
destroy_tree(leaf_6->right, which is leaf_8)
... etc...OriginalL'auteur mark
C'est la façon dont la fonction fonctionne essentiellement:
Ci-dessous est le code pour la mise en œuvre complète de suppression récursive devrait ressembler à:
OriginalL'auteur Zzz