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;
}
}
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.