RÉCURSIVITÉ + ARBRE BINAIRE [VISUAL C++, APPLICATION CONSOLE]

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