Discussion :

[beegees]

Bonjour tout le monde,

Je cherche à créer une fonction nommée AB1_Pere afin de trouver le père d'un certain noeud.

J'envoie à cette fonction AB1_Pere l'adrese de la structure de la racine de l'arbre binaire et l'adresse du noeud recherché (noeud de référence).

La structure est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
TYPE TNoeudAB1 = STRUCTURE
                   Donnee : DATA;
                   FG,FD  : POINTEUR DE TNoeudAB1;
FIN STRUCTURE

FG veut dire Fils Gauche
FD veut dire Fils Droit
DATA : peut être n'importe quel type (int...)

voici le prototype de ma fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
FONCTION   AB1_Pere(Racine,NoeudRef);
PARAMETRES Racine   : POINTEUR DE TNoeudAB1; [I]
           NoeudRef : POINTEUR DE TNoeudAB1; [I/O]
RETOURNER  POINTEUR DE TNoeudAB1;
DEBUT
 
FIN

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

FONCTION   AB1_Pere(Racine,NoeudRef);

Racine s'est le point de départ.
NoeudRef s'est le noeud qui est recherché.

Je dois retourner l'adresse du noeud qui contient un fils (gauche ou droit) dont l'adresse correspond à celui du noeud référence (NoeudRef).

Tout ça avec la récursivité.

Merci d'avance pour votre aide.

beegees

[Veovis]

Tu as plusieurs solutions en voici une, la plus simple :

FONCTION AB1_Pere(Racine,NoeudRef,NoeudPrecedent);

Quand tu te trouves sur un NoeudX :

AB1_Pere(NoeudX->FD, NoeudRef, Noeud)
AB1_Pere(NoeudX->FG, NoeudRef, Noeud)

Si ton NoeudRef == NoeudX alors NoeudPrecedent est l'ancêtre.

J'espére avoir été clair dans mes explications...

[beegees]

Bonjour,

Merci pour ta réponse.

J'ai trouvé la réponse à mon problème :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

FONCTION   AB1_Pere(Racine,NoeudRef);

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
TYPE TNoeudAB1 = STRUCTURE
                   Donnee : DATA;
                   FG,FD  : POINTEUR DE TNoeudAB1;
                 FIN STRUCTURE

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
SI Racine == NULL ALORS
    RETOURNER NULL;
  SINON SI (Racine->FG == NoeudRef) OU (Racine->FD == NoeudRef) ALORS
    RETOURNER Racine;

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 SINON
    NoeudPere = AB1_Pere(Racine->FG,NoeudRef);

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 ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  SI NoeudPere == NULL ALORS

Si NoeudPere est NULL, s'est qu'il n'y a rien

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

NoeudPere = AB1_Pere(Racine->FD,NoeudRef);

On fait alors la recherche dans la branche droite

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
    FIN SI
 
    RETOURNER NoeudPere; 
  FIN SI
FIN

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

[PadawanDuDelphi]

Salut,

si tu veux de l'aide sur le parcours d'arbres, tu as
http://rperrot.developpez.com/articl...ctures/arbres/

Sinon ne peux-tu pas définir une variable AdresseNoeudPere quand tu ajoutes un nouveau noeud ?

A+.