Recursivité dans un arbre binaire simplement chaînée

Bonjour,

J'ai un code ci-dessous qui permet de trouver le père d'un noeud dans un arbre binaire (simplement chaîné).

[CODE]
FONCTION   AB1_Pere(Racine,NoeudRef);
PARAMETRES Racine   : POINTEUR DE TNoeudAB1; [I]
           NoeudRef : POINTEUR DE TNoeudAB1; [I/O]
RETOURNER  POINTEUR DE TNoeudAB1;
VARIABLE   NoeudPere : POINTEUR DE TNoeudAB1;
DEBUT
  SI Racine == NULL ALORS
    RETOURNER NULL;
  SINON SI (Racine->FG == NoeudRef) OU (Racine->FD == NoeudRef) ALORS
    RETOURNER Racine;
  SINON
    NoeudPere = AB1_Pere(Racine->FG,NoeudRef);
    SI NoeudPere == NULL ALORS
      NoeudPere = AB1_Pere(Racine->FD,NoeudRef);
    FIN SI
    RETOURNER NoeudPere;
  FIN SI
FIN[/CODE]

Je vais décirre ligne par ligne afin d'être le plus clair possible dans mes questions sur cette fonction :

[CODE]FONCTION   AB1_Pere(Racine,NoeudRef);[/CODE]

Une autre fonction appelle AB1_Pere et lui transmet Racine et NoeudRef.

Racine est la racine de l'abre (son adresse en tous cas) et NoeudRef est le noeud recherché (on recherche également l'adresse).

Les deux paramètres reçus sont de type POINTEUR DE TNoeudAB1; [I] pour la racine et NoeudRef : POINTEUR DE TNoeudAB1; [I/O] pour NoeudRef.

Voici la composition de la structure TNoeudAB1 :


[CODE]TYPE TNoeudAB1 = STRUCTURE
                   Donnee : DATA;
                   FG,FD  : POINTEUR DE TNoeudAB1;
                 FIN STRUCTURE[/CODE]

[CODE]SI Racine == NULL ALORS
    RETOURNER NULL;
  SINON SI (Racine->FG == NoeudRef) OU (Racine->FD == NoeudRef) ALORS
    RETOURNER Racine;[/CODE]

Vous l'aurez mieux compris que moi, si la racine est NULL, on renvoie NULL, SINON SI le fils gauche de la racine est égal au noeud recherché ou si l'adresse du fils droit de la racine correspond au noeud recherché, on renvoie alors la racine.

Ce qui nous intéresse est ci-dessous :

[CODE] SINON
    NoeudPere = AB1_Pere(Racine->FG,NoeudRef);[/CODE]

On affecte à la variable NoeudPere le résultat obtenu par la fonction AB1_Pere en lui passant comme paramtère Racine->FG et NoeudRef.

Et s'est ici que je ne comprends pas bien, je pense qu'on part de Racine->FilsGauche car s'est le départ mais après :

- comment on voit que l'on passe d'un noeud à l'autre (voir un exemple de récursivité qui montre bien une décrémentation tout en bas de cette page) ?
 
[CODE]  SI NoeudPere == NULL ALORS[/CODE]

Si NoeudPere est NULL, s'est qu'il n'y a rien
      
[CODE]NoeudPere = AB1_Pere(Racine->FD,NoeudRef);[/CODE]

On fait alors la recherche dans la branche droite
[CODE]
    FIN SI

    RETOURNER NoeudPere;
  FIN SI
FIN[/CODE]

On retourne le résultat trouvé (l'adresse de la structure Père).

Ce qui "ne me plait pas" s'est que je ne vois pas comment on passe d'un noeud à l'autre.

Dans cet exemple, on voit bien comment la récursivité est utilisée :

public static long factorielle(int n)
{
   if (n<=0) return 1;
   else return n*factorielle(n-1);
}

on peut voir ici que la condition de fin est n est inférieur ou égal à zéro ET n diminue de 1 à chaque fois qu'il appelle sa propre fonction pour ne pas faire une boucle infinie, mais dans mon code ci-dessus, je ne vois pas le changement d'adresse.

Merci d'avance pour votre aide.

beegees

Pour voir la récursivité en action sur le parcours d'un arbre, il suffit de réaliser un exemple avec des traces :

#include <stdio.h>
#include <stdarg.h>

// --- Voir un message avec une indentation liée à la récursivité
// --- Le niveau est incrémenté quand on entre dans AB1_Pere()
// --- Le niveau est décrémenté quand on quitte AB1_Pere()
#define CHAINE(p) (p ? p->pData : "NULL")
void Voir (int iAction,const char* pText,...)
{
   char szText[100];
   va_list pArg;
   va_start(pArg,pText);
   vsprintf(szText,pText,pArg);
   va_end(pArg);

   static int iNiveau = 0;
   if (iAction == -1) --iNiveau;

   printf("%02d ",iNiveau);
   for (int i=0 ; i<3*iNiveau ; ++i) printf(" ");
   printf(szText);
   printf("\n");

   if (iAction == +1) ++iNiveau;
}

struct NOEUD          // description d'un noeud
{
   const char* pData; // chaque NOEUD aura son nom comme data
   NOEUD*      pFG;   // pointe le fils de gauche
   NOEUD*      pFD;   // pointe le fils de droite
};

const NOEUD* AB1_Pere(const NOEUD* pRacine,const NOEUD* pNoeudRef)
{
   const NOEUD* pNoeudPere;

   Voir(+1,"ENTREE AB1_Pere(%s,%s)",CHAINE(pRacine),CHAINE(pNoeudRef));
   if (pRacine == NULL)
   {
      Voir(-1,"SORTIE AB1_Pere() avec racine NULL");
      return NULL;
   }
   if (pRacine->pFG == pNoeudRef)
   {
      Voir(-1,"SORTIE AB1_Pere() avec noeud %s trouve a gauche",CHAINE(pNoeudRef));
      return pRacine;
   }
   if (pRacine->pFD == pNoeudRef)
   {
      Voir(-1,"SORTIE AB1_Pere() avec noeud %s trouve a droite",CHAINE(pNoeudRef));
      return pRacine;
   }
   Voir(0,"Appel du sous-arbre gauche avec %s comme racine",CHAINE(pRacine->pFG));
   pNoeudPere = AB1_Pere(pRacine->pFG,pNoeudRef);
   if (pNoeudPere == NULL)
   {
      Voir(0,"Appel du sous-arbre droit avec %s comme racine",CHAINE(pRacine->pFD));
      pNoeudPere = AB1_Pere(pRacine->pFD,pNoeudRef);
   }
   Voir(-1,"SORTIE AB1_Pere() avec noeud pere %s",CHAINE(pNoeudPere));
   return pNoeudPere;
}

void main()
{
   // On va créer cet arbre :
   //
   //                 +-- FD2 --+-- FD3
   //                 |         |
   //       +-- FD1 --+         +-- FG3
   //       |         |
   //       |         +-- FG2 --+-- FD4
   //       |                   |
   // RAC --+                   +-- FG4
   //       |
   //       |         +-- FD5 --+-- FD6
   //       |         |         |
   //       +-- FG1 --+         +-- FG6
   //                 |
   //                 +-- FG5 --+-- FD7
   //                           |
   //                           +-- FG7

   NOEUD FD3 = {"FD3",NULL,NULL};
   NOEUD FG3 = {"FG3",NULL,NULL};

   NOEUD FD2 = {"FD2",&FG3,&FD3};

   NOEUD FD4 = {"FD4",NULL,NULL};
   NOEUD FG4 = {"FG4",NULL,NULL};

   NOEUD FG2 = {"FG2",&FG4,&FD4};

   NOEUD FD1 = {"FD1",&FG2,&FD2};

   NOEUD FD6 = {"FD6",NULL,NULL};
   NOEUD FG6 = {"FG6",NULL,NULL};

   NOEUD FD5 = {"FD5",&FG6,&FD6};
  
   NOEUD FD7 = {"FD7",NULL,NULL};
   NOEUD FG7 = {"FG7",NULL,NULL};

   NOEUD FG5 = {"FG5",&FG7,&FD7};

   NOEUD FG1 = {"FG1",&FG5,&FD5};

   NOEUD RAC = {"RAC",&FG1,&FD1};

  
   // --- Test 1
   printf("\nChercher le noeud pere de FD6 :\n\n");
   const NOEUD* pPere = AB1_Pere(&RAC,&FD6);
   printf("\nLe noeud pere de FD6 est %s\n\n",CHAINE(pPere));

  
   // --- Test 2
   printf("\nChercher le noeud pere de FG1 :\n\n");
   pPere = AB1_Pere(&RAC,&FG1);
   printf("\nLe noeud pere de FG1 est %s\n\n",CHAINE(pPere));
   

   // --- Test 3
   printf("\nChercher le noeud pere de RAC :\n\n");
   pPere = AB1_Pere(&RAC,&FG1);
   printf("\nLe noeud pere de RAC est %s\n\n",CHAINE(pPere));
}

Ce qui donne :


Chercher le noeud pere de FD6 :

00 ENTREE AB1_Pere(RAC,FD6)
01    Appel du sous-arbre gauche avec FG1 comme racine
01    ENTREE AB1_Pere(FG1,FD6)
02       Appel du sous-arbre gauche avec FG5 comme racine
02       ENTREE AB1_Pere(FG5,FD6)
03          Appel du sous-arbre gauche avec FG7 comme racine
03          ENTREE AB1_Pere(FG7,FD6)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,FD6)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,FD6)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
03          Appel du sous-arbre droit avec FD7 comme racine
03          ENTREE AB1_Pere(FD7,FD6)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,FD6)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,FD6)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
02       SORTIE AB1_Pere() avec noeud pere NULL
02       Appel du sous-arbre droit avec FD5 comme racine
02       ENTREE AB1_Pere(FD5,FD6)
02       SORTIE AB1_Pere() avec noeud FD6 trouve a droite
01    SORTIE AB1_Pere() avec noeud pere FD5
00 SORTIE AB1_Pere() avec noeud pere FD5

Le noeud pere de FD6 est FD5

Chercher le noeud pere de FG1 :

00 ENTREE AB1_Pere(RAC,FG1)
00 SORTIE AB1_Pere() avec noeud FG1 trouve a gauche

Le noeud pere de FG1 est RAC

Chercher le noeud pere de RAC :

00 ENTREE AB1_Pere(RAC,RAC)
01    Appel du sous-arbre gauche avec FG1 comme racine
01    ENTREE AB1_Pere(FG1,RAC)
02       Appel du sous-arbre gauche avec FG5 comme racine
02       ENTREE AB1_Pere(FG5,RAC)
03          Appel du sous-arbre gauche avec FG7 comme racine
03          ENTREE AB1_Pere(FG7,RAC)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
03          Appel du sous-arbre droit avec FD7 comme racine
03          ENTREE AB1_Pere(FD7,RAC)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
02       SORTIE AB1_Pere() avec noeud pere NULL
02       Appel du sous-arbre droit avec FD5 comme racine
02       ENTREE AB1_Pere(FD5,RAC)
03          Appel du sous-arbre gauche avec FG6 comme racine
03          ENTREE AB1_Pere(FG6,RAC)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
03          Appel du sous-arbre droit avec FD6 comme racine
03          ENTREE AB1_Pere(FD6,RAC)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
02       SORTIE AB1_Pere() avec noeud pere NULL
01    SORTIE AB1_Pere() avec noeud pere NULL
01    Appel du sous-arbre droit avec FD1 comme racine
01    ENTREE AB1_Pere(FD1,RAC)
02       Appel du sous-arbre gauche avec FG2 comme racine
02       ENTREE AB1_Pere(FG2,RAC)
03          Appel du sous-arbre gauche avec FG4 comme racine
03          ENTREE AB1_Pere(FG4,RAC)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
03          Appel du sous-arbre droit avec FD4 comme racine
03          ENTREE AB1_Pere(FD4,RAC)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
02       SORTIE AB1_Pere() avec noeud pere NULL
02       Appel du sous-arbre droit avec FD2 comme racine
02       ENTREE AB1_Pere(FD2,RAC)
03          Appel du sous-arbre gauche avec FG3 comme racine
03          ENTREE AB1_Pere(FG3,RAC)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
03          Appel du sous-arbre droit avec FD3 comme racine
03          ENTREE AB1_Pere(FD3,RAC)
04             Appel du sous-arbre gauche avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
04             Appel du sous-arbre droit avec NULL comme racine
04             ENTREE AB1_Pere(NULL,RAC)
04             SORTIE AB1_Pere() avec racine NULL
03          SORTIE AB1_Pere() avec noeud pere NULL
02       SORTIE AB1_Pere() avec noeud pere NULL
01    SORTIE AB1_Pere() avec noeud pere NULL
00 SORTIE AB1_Pere() avec noeud pere NULL

Le noeud pere de RAC est NULL

Jean-François

Bonjour jfrancois,

Merci pour ton code qui me semble très intéressant.

Qaund je compile, j'ai ces messages d'erreurs :

rec.cpp
C:\Documents and Settings\David\Mes documents\Recursivite\recursivite\rec.cpp(43) : error C2660: 'Voir' : function does not take 4 parameters
C:\Documents and Settings\David\Mes documents\Recursivite\recursivite\rec.cpp(51) : error C2660: 'Voir' : function does not take 3 parameters
C:\Documents and Settings\David\Mes documents\Recursivite\recursivite\rec.cpp(56) : error C2660: 'Voir' : function does not take 3 parameters
C:\Documents and Settings\David\Mes documents\Recursivite\recursivite\rec.cpp(59) : error C2660: 'Voir' : function does not take 3 parameters
C:\Documents and Settings\David\Mes documents\Recursivite\recursivite\rec.cpp(63) : error C2660: 'Voir' : function does not take 3 parameters
C:\Documents and Settings\David\Mes documents\Recursivite\recursivite\rec.cpp(66) : error C2660: 'Voir' : function does not take 3 parameters
Error executing cl.exe.


Saurais-tu m'aider stp ?

Merci d'avance.

Bonjour,

1) La fonction Voir() a un nombre variable d'arguments pour permettre de passer des variables (...) à formater dans le texte (pFormat) via la macro CHAINE() pour éviter les pointeurs NULL. Quand je compile sous mon Visual C++ 6.0, je n'ai aucun problème, c'est vraiment un source basique.
En cherchant des infos sur cette erreur C2660 il est proposé d'utiliser l'opérateur de résolution de portée "::" (écrire ::Voir(+1,"ENTREE ...") ) car il se peut qu'il y ait, dans votre environnement, une autre fonction Voir() avec un nombre précis d'arguments ! mais c'est peu probable ! Vous utilisez quel compilateur ? Si votre compilateur n'admet pas l'argument "..." il suffit de formater le texte avant l'appel à la fonction Voir().


2) Dans cette même fonction Voir() on peut remplacer :
   for (int i=0 ; i<3*iNiveau ; ++i) printf(" ");
par
   for (int i=0 ; i<iNiveau ; ++i) printf("|  ");
c'est plus joli !


3) J'ai modifié AB1_Pere() pour éviter la longue recherche du 3ème test (recherche de la racine même de l'arbre) et réorganiser un peu le parcours des 2 sous-arbres :

Voici ce que tout cela donne :

#include <stdio.h>
#include <stdarg.h>

// --- Voir un message avec une indentation liée à la récursivité
// --- Le niveau est incrémenté quand on entre dans AB1_Pere()
// --- Le niveau est décrémenté quand on quitte AB1_Pere()
#define CHAINE(p) (p ? p->pData : "NULL")
void Voir(int iAction,const char* pFormat,...)
{
   char szText[100];
   va_list pArg;
   va_start(pArg,pFormat);
   vsprintf(szText,pFormat,pArg);
   va_end(pArg);

   static int iNiveau = 0;
   if (iAction < 0) --iNiveau;

   printf("%02d ",iNiveau);
   for (int i=0 ; i<iNiveau ; ++i) printf("|  ");
   printf(szText);
   printf("\n");

   if (iAction > 0) ++iNiveau;
}

 

// --- Description d'un noeud de l'arbre
struct NOEUD
{
   const char* pData; // chaque NOEUD aura son nom comme data
   NOEUD*      pFG;   // pointe le fils de gauche
   NOEUD*      pFD;   // pointe le fils de droite
};

 

// --- Recherche du noeud père d'un noeud fils dans un arbre
const NOEUD* AB1_Pere
(
    const NOEUD* pRacine // E:pointe la racine d'un arbre
   ,const NOEUD* pFils   // E:pointe le noeud fils à rechercher
)                        // S:pointe le noeud père trouvé ou NULL
{
   Voir(+1,"ENTREE AB1_Pere(%s,%s)",CHAINE(pRacine),CHAINE(pFils));

   // --- Quitter si pointeur NULL
   if (pRacine == NULL)
   {
      Voir(-1,"SORTIE AB1_Pere(%s,%s) avec racine = NULL"
          ,CHAINE(pRacine),CHAINE(pFils));
      return NULL;
   }
   if (pFils == NULL)
   {
      Voir(-1,"SORTIE AB1_Pere(%s,%s) avec fils = NULL"
          ,CHAINE(pRacine),CHAINE(pFils));
      return NULL;
   }

   // --- Quitter si le fils n'a pas de père !
   if (pRacine == pFils)
   {
      Voir(-1,"SORTIE AB1_Pere(%s,%s) avec pere = fils"
          ,CHAINE(pRacine),CHAINE(pFils));
      return pRacine;
      // OU return NULL; si on considère que le fils n'a pas de père
      // plutôt que d'être son propre père
   }

  
   // --- Quitter si la racine est le père
   if (pRacine->pFG == pFils)
   {
      Voir(-1,"SORTIE AB1_Pere(%s,%s) avec le fils %s trouve a gauche"
          ,CHAINE(pRacine),CHAINE(pFils),CHAINE(pFils));
      return pRacine;
   }
   if (pRacine->pFD == pFils)
   {
      Voir(-1,"SORTIE AB1_Pere(%s,%s) avec le fils %s trouve a droite"
          ,CHAINE(pRacine),CHAINE(pFils),CHAINE(pFils));
      return pRacine;
   }
  
  
   // --- Chercher le fils dans le sous-arbre de gauche sous la racine
   Voir(0,"Appel du sous-arbre gauche avec racine = %s",CHAINE(pRacine->pFG));
   const NOEUD* pPere = AB1_Pere(pRacine->pFG,pFils);
   if (pPere)
   {
      Voir(-1,"SORTIE AB1_Pere(%s,%s) avec pere = %s"
          ,CHAINE(pRacine),CHAINE(pFils),CHAINE(pPere));
      return pPere;
   }
  
  
   // --- Chercher le fils dans le sous-arbre de droite sous la racine
   Voir(0,"Appel du sous-arbre droit avec racine = %s",CHAINE(pRacine->pFD));
   pPere = AB1_Pere(pRacine->pFD,pFils);
   if (pPere)
   {
      Voir(-1,"SORTIE AB1_Pere(%s,%s) avec pere = %s"
          ,CHAINE(pRacine),CHAINE(pFils),CHAINE(pPere));
      return pPere;
   }
  
  
   // --- Le fils n'a pas été trouvé
   Voir(-1,"SORTIE AB1_Pere(%s,%s) avec le fils %s non trouve"
       ,CHAINE(pRacine),CHAINE(pFils),CHAINE(pFils));
   return NULL;
}

 

void main()
{
   // On va créer cet arbre :
   //
   //                 +-- FD2 --+-- FD3
   //                 |         |
   //       +-- FD1 --+         +-- FG3
   //       |         |
   //       |         +-- FG2 --+-- FD4
   //       |                   |
   // RAC --+                   +-- FG4
   //       |
   //       |         +-- FD5 --+-- FD6
   //       |         |         |
   //       +-- FG1 --+         +-- FG6
   //                 |
   //                 +-- FG5 --+-- FD7
   //                           |
   //                           +-- FG7

   NOEUD FD3 = {"FD3",NULL,NULL};
   NOEUD FG3 = {"FG3",NULL,NULL};

   NOEUD FD2 = {"FD2",&FG3,&FD3};

   NOEUD FD4 = {"FD4",NULL,NULL};
   NOEUD FG4 = {"FG4",NULL,NULL};

   NOEUD FG2 = {"FG2",&FG4,&FD4};

   NOEUD FD1 = {"FD1",&FG2,&FD2};

   NOEUD FD6 = {"FD6",NULL,NULL};
   NOEUD FG6 = {"FG6",NULL,NULL};

   NOEUD FD5 = {"FD5",&FG6,&FD6};
  
   NOEUD FD7 = {"FD7",NULL,NULL};
   NOEUD FG7 = {"FG7",NULL,NULL};

   NOEUD FG5 = {"FG5",&FG7,&FD7};

   NOEUD FG1 = {"FG1",&FG5,&FD5};

   NOEUD RAC = {"RAC",&FG1,&FD1};

  
   // --- Test 1
   printf("\n*** TEST 1 ***\nChercher le pere de FD6 :\n\n");
   const NOEUD* pPere = AB1_Pere(&RAC,&FD6);
   printf("\nLe pere de FD6 est %s\n\n",CHAINE(pPere));

  
   // --- Test 2
   printf("\n*** TEST 2 ***\nChercher le pere de FG1 :\n\n");
   pPere = AB1_Pere(&RAC,&FG1);
   printf("\nLe pere de FG1 est %s\n\n",CHAINE(pPere));

  
   // --- Test 3
   printf("\n*** TEST 3 ***\nChercher le pere de RAC :\n\n");
   pPere = AB1_Pere(&RAC,&RAC);
   printf("\nLe pere de RAC est %s\n\n",CHAINE(pPere));
}

Qui donne à l'exécution :

*** TEST 1 ***
Chercher le pere de FD6 :

00 ENTREE AB1_Pere(RAC,FD6)
01 |  Appel du sous-arbre gauche avec racine = FG1
01 |  ENTREE AB1_Pere(FG1,FD6)
02 |  |  Appel du sous-arbre gauche avec racine = FG5
02 |  |  ENTREE AB1_Pere(FG5,FD6)
03 |  |  |  Appel du sous-arbre gauche avec racine = FG7
03 |  |  |  ENTREE AB1_Pere(FG7,FD6)
04 |  |  |  |  Appel du sous-arbre gauche avec racine = NULL
04 |  |  |  |  ENTREE AB1_Pere(NULL,FD6)
04 |  |  |  |  SORTIE AB1_Pere(NULL,FD6) avec racine = NULL
04 |  |  |  |  Appel du sous-arbre droit avec racine = NULL
04 |  |  |  |  ENTREE AB1_Pere(NULL,FD6)
04 |  |  |  |  SORTIE AB1_Pere(NULL,FD6) avec racine = NULL
03 |  |  |  SORTIE AB1_Pere(FG7,FD6) avec le fils FD6 non trouve
03 |  |  |  Appel du sous-arbre droit avec racine = FD7
03 |  |  |  ENTREE AB1_Pere(FD7,FD6)
04 |  |  |  |  Appel du sous-arbre gauche avec racine = NULL
04 |  |  |  |  ENTREE AB1_Pere(NULL,FD6)
04 |  |  |  |  SORTIE AB1_Pere(NULL,FD6) avec racine = NULL
04 |  |  |  |  Appel du sous-arbre droit avec racine = NULL
04 |  |  |  |  ENTREE AB1_Pere(NULL,FD6)
04 |  |  |  |  SORTIE AB1_Pere(NULL,FD6) avec racine = NULL
03 |  |  |  SORTIE AB1_Pere(FD7,FD6) avec le fils FD6 non trouve
02 |  |  SORTIE AB1_Pere(FG5,FD6) avec le fils FD6 non trouve
02 |  |  Appel du sous-arbre droit avec racine = FD5
02 |  |  ENTREE AB1_Pere(FD5,FD6)
02 |  |  SORTIE AB1_Pere(FD5,FD6) avec le fils FD6 trouve a droite
01 |  SORTIE AB1_Pere(FG1,FD6) avec pere = FD5
00 SORTIE AB1_Pere(RAC,FD6) avec pere = FD5

Le pere de FD6 est FD5

*** TEST 2 ***
Chercher le pere de FG1 :

00 ENTREE AB1_Pere(RAC,FG1)
00 SORTIE AB1_Pere(RAC,FG1) avec le fils FG1 trouve a gauche

Le pere de FG1 est RAC

*** TEST 3 ***
Chercher le pere de RAC :

00 ENTREE AB1_Pere(RAC,RAC)
00 SORTIE AB1_Pere(RAC,RAC) avec pere = fils

Le pere de RAC est RAC
ou
Le pere de RAC est NULL si on choisit le return NULL; dans AB1_Pere()

Jean-François

Bonjour Jean-François,

ça fonctionne maintenant, merci.

À moi d'essayer de comrpendre mainteannt.

encore un grand merci.

Ca marche après quelle modif ?

Voici une autre petite modif qui permet de réaliser plus facilement autant de tests qu'on veut !

// --- Réaliser un test de recherche de père
void Tester
(
    const NOEUD* pRacine // E:pointe la racine d'un arbre
   ,const NOEUD* pFils   // E:pointe le fils dont on cherche le père
)
{
   printf("\n\n*** TEST ***\n");
   printf("Chercher le pere de %s dans l'arbre de racine %s :\n\n"
         ,CHAINE(pFils),CHAINE(pRacine));
   const NOEUD* pPere = AB1_Pere(pRacine,pFils);
   if (pPere)
      printf("\nLe pere de %s est %s dans l'arbre de racine %s\n\n"
            ,CHAINE(pFils),CHAINE(pPere),CHAINE(pRacine));
   else
      printf("\n%s n'a pas de pere dans l'arbre de racine %s\n\n"
            ,CHAINE(pFils),CHAINE(pRacine));
}

 

// --- Fonction principale
void main()
{
   // On va créer cet arbre :
   //
   //                 +-- FD2 --+-- FD3
   //                 |         |
   //       +-- FD1 --+         +-- FG3
   //       |         |
   //       |         +-- FG2 --+-- FD4
   //       |                   |
   // RAC --+                   +-- FG4
   //       |
   //       |         +-- FD5 --+-- FD6
   //       |         |         |
   //       +-- FG1 --+         +-- FG6
   //                 |
   //                 +-- FG5 --+-- FD7
   //                           |
   //                           +-- FG7

   NOEUD FD3          = {"FD3",NULL,NULL};
   NOEUD FG3          = {"FG3",NULL,NULL};
      NOEUD FD2       = {"FD2",&FG3,&FD3};
   NOEUD FD4          = {"FD4",NULL,NULL};
   NOEUD FG4          = {"FG4",NULL,NULL};
      NOEUD FG2       = {"FG2",&FG4,&FD4};
         NOEUD FD1    = {"FD1",&FG2,&FD2};
   NOEUD FD6          = {"FD6",NULL,NULL};
   NOEUD FG6          = {"FG6",NULL,NULL};
      NOEUD FD5       = {"FD5",&FG6,&FD6};
   NOEUD FD7          = {"FD7",NULL,NULL};
   NOEUD FG7          = {"FG7",NULL,NULL};
      NOEUD FG5       = {"FG5",&FG7,&FD7};
         NOEUD FG1    = {"FG1",&FG5,&FD5};
            NOEUD RAC = {"RAC",&FG1,&FD1};

  
   // --- Tests
   Tester(&RAC,&FD6);
   Tester(&RAC,&FG1);
   Tester(&RAC,&RAC);
   Tester(&FG1,&FD7);
   Tester(&FG1,&FD3);
   // ...
}

Jean-François