FORUM MP | Algorithmes : récursivité avec les arbres binaires

COMMUNAUTE MP

Identifiez vous ...

DOMAINE MP

Bavardages

Langages Généraux

Langages Web

Langages DotNet

Autres langages

Dev. Jeux Video

Sécurité

Sys. Exploitation

Graphismes

Logiciels

Réseaux

Bases de données

Méthodologies

Emplois High-tech

Aide juridique

Articles juridiques

FORUM

CHAT MP IRC

Votre pseudo ...

Serv: irc.irc-land.org

Chan: #MoteurProg

PARTICIPER

Plus de 3500 emplois.

Visiteur MP

récursivité avec les arbres binaires
	Forum : ALGORITHMES Sous Catégorie : Aucune Type du sujet : Sujet Normale FAQ : FAQ ALGORITHMES
		SUIVI PAR MAIL INACTIF
		SUJET NON RESOLU
		SUJET ACTIF
		N'APPARTIENT PAS A LA FAQ

FORUM ALGORITHMES
	Page précedente	Page suivante

beegees
Nouveau membre

Inscrit : 24/05/2004
Messages : 6

#150716 Posté le 16/03/08 à 19:25

Bonjour tout le monde,

J'ai une fonction qui permet de rechercher le Père d'un noeud en partant de la racine :

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]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.

[COLOR]Et s'est ici que je ne comprends pas bien[/COLOR] 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] 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

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

HAUT DE PAGE

Publicité

Inscrit : X
Messages : X

#Aucun

HAUT DE PAGE

hibou57
Superviseur :
- Langages Web
Modérateur :
- XML/XSL
- ADA

Inscrit : 13/02/2005
Messages : 350

#150723 Posté le 17/03/08 à 01:16

Bonjour BeeGees,

Tout d'abord je tiens à te féliciter pour le soin que tu as apporté à la formulation de ta question. On sent bien que tu t'es donné la peine de te faire comprendre.

Pour répondre à la question "je ne vois pas quand on change de noeud" :

Ca se passe ici

NoeudPere = AB1_Pere(Racine->FG,NoeudRef); SI NoeudPere == NULL ALORS NoeudPere = AB1_Pere(Racine->FD,NoeudRef);

Racine->FG ou Racine->FD va remplacer Racine, tout simplement.

Mais je ne sais pas si j'ai bien répondu à ta question.

Si tu as une fonction récursive F(X) et que tu l'appel en faisant F(A), alors A va prendre la place de X.

De la même manière, c'est en passant le paramètre ->FG ou ->FD que tu change de Racine.

Dis moi si la réponse ne te convient pas, et j'essaierai de t'expliquer autrement encore.

Note : pour bien comprendre un algorithme, l'astuce au départ est de faire un shéma sur lequel tu va faire travailler ton algorithme. Dans cet exemple, dessine un arbre sur papier, choisi deux noeud sur lesquels tu veux appliquer la fonction, et applique le fonctionnement à partir du dessin de ton arbre. Voir le fonctionnement des choses en image, aide souvent à comprendre. Ensuite, on prend l'habitude, et on fait les petits dessins directement dans sa tête...

Voilà Smiley

A bientôt ...
__________________________
Lasidoré : Editeur XML orienté sémantique/Online XML editor (Prototype)
Utiliser le Compilateur Ada Gnat

HAUT DE PAGE

PAGE : [1]

.: Site Web développé par Julien Pichot et l'équipe MPWG avec www.evolvia-web.com :.