Récursivité + arbre binaire [visual c++, application console]

Soyez le premier à donner votre avis sur cette source.

Snippet vu 25 441 fois - Téléchargée 37 fois

Contenu du snippet

Ce petit bout de code fait un Arbre binaire, l'affiche et le détruit. Aucun memory leak, il est bien monté et pourtant très simple.

Cet arbre binaire contient en fait 25 nombre différents créer avec la fonction rand(), l'arbre est trié directement sur l'ajout puis on l'affiche et on a des stats sur le nombre de fois que chacun des nombres est sorti.

à propos de la récursivité:
1- la récursivité est rarement le code le plus efficace qui existe et doit être soigneusement orchetré. Effectivement c'est assez facile de se tromper de faire des méchants bugs.
2- la récursivité bourre la "stack du système", si vous gérer des arbres trop grand, (ce qui est immense mais passons) vous pouvez défoncer la stack, (un reboot d'ordi en perspective)
3- la récursivité est souvent la méthode la plus facile de se sortir de certains problèmes exotiques.

NOTEZ: C'est aussi un exemple d'allocation de mémoire pour les structures de données.

Source / Exemple :


#include "stdafx.h"
#include <conio.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
/**************************************************************************
//J'ai lu quelque part que pour comprendre la récursivité on doit d'abord
//comprendre la récursivité.  Je l'ai trouvé bien drôle mais la récursivité
//est relativement simple.  
//
//Pour vous l'enseigner j'ai ici programmé un arbre binaire dont l'accès
//est récursif, have fun.

                                                                                                                                                    • /
//la structure de notre arbre struct Noeud_Arbre { int Val; int Nb_Fois; Noeud_Arbre* pParent; Noeud_Arbre* pFils; //tien voilà pas de sexisme, un noeud fils pis un noeud Noeud_Arbre* pFille; //fille, normalement c'est un fils droit un fils gauche }; //bon pas vraiement utile mais on va faire ça propre struct Noeud_Racine { Noeud_Arbre* pRacine; //on pourrait ici stoquer des stats genre //int Nb_Element_total_que_contient_notre_arbre; //int Nb_Etage_Max; //int Couleur_des_yeux_du_chien_de_l_oncle_du_frere_du_cousin_germain_de_l_autre; }; bool Ajouter(int Data, Noeud_Arbre* Noeud_Courant); void Afficher_En_Ordre(Noeud_Arbre* Noeud_Courant); void Afficher_En_Arbre(Noeud_Arbre* Noeud_Courant, int Nb_Etage, char strAfficher[25], bool Fille); void Detruire_Arbre(Noeud_Arbre* Noeud_Courant); int main(int argc, char* argv[]) { int compteur = 300; char strPath[25]; strPath[0] = '\0'; Noeud_Racine Arbre; srand((int)time(NULL)); Arbre.pRacine = new Noeud_Arbre; //bon on initialise l'arbre //normalement notre fonction ajouter doit supporter ce cas limite //mais comme je suis lâche vous ne m'en voudrez pas j'en suis sur Arbre.pRacine->pFille = NULL; Arbre.pRacine->pFils = NULL; Arbre.pRacine->pParent = NULL; //on met un nombre au hasard, j'utilise le %25 pour qu'il //y ait 25 éléments différents dans l'arbre et ainsi l'affichage //prend un écran pas plus pas moins Arbre.pRacine->Val = rand()%25; Arbre.pRacine->Nb_Fois = 1; //ensuite on loop pour ajouter du stock while(compteur--) { Ajouter(rand()%25,Arbre.pRacine); } //on affiche trié Afficher_En_Ordre(Arbre.pRacine); _getch(); //on affiche la structure de l'arbre Afficher_En_Arbre(Arbre.pRacine,0,strPath,false); _getch(); //on le détruit Detruire_Arbre(Arbre.pRacine); return 0; } /************************************************************************* //bool Ajouter(int Data, Noeud_Arbre* Noeud_Courant) // //la fonction ajouter trie automatiquement les données.. c'est une des utilisation //des arbres binaires // //elle utilise la récursivité pour retrouvé la feuille ou l'élément égal //imaginez que vous marcher dans un couloir avec un nombre d'écrit sur //votre gilet. Vous arrivez à un Y. À cet endroit il a un nombre d'écrit //et une pancarte dit, si le nombre inscrit sur votre gilet est plus petit //que celui sur le paneau prenez à gauche, s'il est plus grand que celui //sur la paneau prenez à droite, s'il est égal, asseyez vous ici.Imaginons //que notre nombre est plus petit, alors on va à gauche (voici la //récursivité, on traite le même cas que précédement de la même façon et //c'est le cas qui avance) vous marchez dans un couloir avec un nombre //d'écrit sur votre gilet... etc. Jusqu'à ce que vous trouver l'endroit où //vous arrêter qui peut être soit une intersection où il n'y a pas de //paneau ou dans notre cas, c'est un intersection où le paneau a le même //nombre que sur notre gilet
                                                                                                                                                  • /
bool Ajouter(int Data, Noeud_Arbre* Noeud_Courant) { if(Noeud_Courant == NULL) { //on a rien à faire ici... return false; } //on va être gallant on va traiter le noeud fille en premier else if(Data < Noeud_Courant->Val) { //si le noeud fille existe pas on doit en créer un nouveau if(Noeud_Courant->pFille == NULL) { Noeud_Courant->pFille = new Noeud_Arbre; Noeud_Courant->pFille->pFille = NULL; Noeud_Courant->pFille->pFils = NULL; Noeud_Courant->pFille->pParent = Noeud_Courant; //on assigne la valeur reçu Noeud_Courant->pFille->Val = Data; //on signifie que c'est la première fois que ce nombre survient Noeud_Courant->pFille->Nb_Fois = 1; return true; } else { //voici la récursivité on s'appelle soi-même mais avec un nouvel élément, //dans ce cas ci on progresse vers la feuille de l'arbre donc on encoie //notre fille return Ajouter(Data,Noeud_Courant->pFille); } } else if(Data > Noeud_Courant->Val) { //si le noeud fils existe pas on doit en créer un nouveau if(Noeud_Courant->pFils == NULL) { Noeud_Courant->pFils = new Noeud_Arbre; Noeud_Courant->pFils->pFille = NULL; Noeud_Courant->pFils->pFils = NULL; Noeud_Courant->pFils->pParent = Noeud_Courant; //on assigne la valeur reçu Noeud_Courant->pFils->Val = Data; //on signifie que c'est la première fois que ce nombre survient Noeud_Courant->pFils->Nb_Fois = 1; return true; } else { //voici la récursivité on s'appelle soi-même mais avec un nouvel élément, //dans ce cas ci on progresse vers la feuille de l'arbre donc on encoie //notre fils return Ajouter(Data,Noeud_Courant->pFils); } } else //if(Data == Noeud_Courant->Val { Noeud_Courant->Nb_Fois++; return true; } } /************************************************************************* //void Afficher_En_Ordre(Noeud_Arbre* Noeud_Courant) // //Ici c'est de la récursivité à son meilleur. Pour afficher tout l'arbre //si on a un arbre valide // Afficher la gauche // Afficher vous // Afficher la droite //La gauche et la droite sont eux même des arbres, alors on utilise la //même fonction
                                                                                                                                                  • /
void Afficher_En_Ordre(Noeud_Arbre* Noeud_Courant) { if(Noeud_Courant != NULL) { Afficher_En_Ordre(Noeud_Courant->pFille); printf("\nLa valeur de ce noeud est %d et il a ete genere %d fois", Noeud_Courant->Val ,Noeud_Courant->Nb_Fois); Afficher_En_Ordre(Noeud_Courant->pFils); } } /************************************************************************* //void Afficher_En_Arbre(Noeud_Arbre* Noeud_Courant,int Nb_Etage) // //vous devriez commencer à comprendre... //dans afficher en arbre on s'affiche avec l'héritage des parents, on calcul //ce que les enfant vont avoir à afficher pour respecter leurs rang puis //on leurs dit de s'afficher //
                                                                                                                                                  • /
void Afficher_En_Arbre(Noeud_Arbre* Noeud_Courant,int Nb_Etage,char strAfficher[25],bool Fille) { char strChild[25]; //on se débarasse tout de suite du cas limite par un beau return if(Noeud_Courant == NULL) //comme les prof nous appris a pas faire { return; } if(Fille) { sprintf(strChild,"%s %c",strAfficher,179); printf("\n%s %c-Val = %d(%d fois)", strAfficher,195,Noeud_Courant->Val,Noeud_Courant->Nb_Fois); } else { sprintf(strChild,"%s %c",strAfficher,' '); printf("\n%s %c-Val = %d(%d fois)", strAfficher,192,Noeud_Courant->Val,Noeud_Courant->Nb_Fois); } Afficher_En_Arbre(Noeud_Courant->pFille,Nb_Etage+1,strChild,Noeud_Courant->pFils != NULL); Afficher_En_Arbre(Noeud_Courant->pFils,Nb_Etage+1,strChild,false); } /************************************************************************* //void Detruire_Arbre(Noeud_Arbre* Noeud_Courant) // //plus simple et plus belle fonction de récursivité... // // // //
                                                                                                                                                  • /
void Detruire_Arbre(Noeud_Arbre* Noeud_Courant) { if(Noeud_Courant != NULL) { Detruire_Arbre(Noeud_Courant->pFille); Detruire_Arbre(Noeud_Courant->pFils); delete Noeud_Courant; } }

A voir également

Ajouter un commentaire

Commentaires

nickydaquick
Messages postés
417
Date d'inscription
vendredi 31 janvier 2003
Statut
Membre
Dernière intervention
19 décembre 2013
1 -
Franchement , ton arbre binaire pourrait peut-etre marcher , mais ton arbre binaire n'est pas balance , il n'y a pas de fonction de recherche d'objets ( donc pas de fonction de suppression de ces objets ) , et tes noeuds sont tres gros : il s'agit pas d'un arbre mais d'une liste doublement chainee de listes doublement chainee . en tout cas .... niveau expert , je pense pas . jte mets 5/10
aittayeb
Messages postés
1
Date d'inscription
mercredi 26 janvier 2005
Statut
Membre
Dernière intervention
26 janvier 2005
-
peut-on modifier ce programme pour l'utlliser pour la recherche d'un triangle proche d'un point dans un maillage avec un arbre quaternaire?

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.