Discussion :

[allomona]

bonsoir
mon problème réside dans le parcours récursif d'un arbre binaire de recherche.
Il existe 3 types de parcours infixe(g r d), préfixe(r g d) et le postfixe(g d r).
Par exemple le parcours préfixe de l'arbre du fichier joint donne 0 1 2 3 4 5 6 ça c'est clair mais mon problème réside dans la compréhension du tournage à la main de la procédure récursive:

Code :

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

1
2
3
4
5
6
7
8
procedure parcours_prefixe(b:arbre)
  debut
    si (b!= nil) alors 
      ecrire(b^.valeur) 
      parcours_prefixe(b^.gauche)
      parcours_prefixe(b^.droite)
    fin si
  fin

1)on donne la racine comme paramètre racine!=nil ---->ecrire 0
parcours_prefixe(b^.gauche)
2)b^.gauche!=nil------->ecrire1
parcours_prefixe(b^.gauche)
3)b^.gauche!=nil------->ecrire2
parcours_prefixe(b^.gauche)
4)là je me plante ce noeud!=nil (il s'agit d'un arbre sans feuille avec 2 comme valaur) mais à ce stade b^.gauche == nil
don on peut pas exécuter les instructions du bloc SI et par la suite on peut pas passer a parcours_prefixe(b^.droite)

cette procedure je la trouve partout, certes elle est correcte et si quelqu'un m'aide à la comprendre pour que je puisse continuer à resoudre mes exercices je le serai reconnaissante

j'espère que je me suis bien exprimée et désolée s'il sagit d'une question bête.

[prgasp77]

Bonjour,

Lorsque tu parcours le nœud étiqueté « 2 », tu appelles la fonction parcours_prefixe en lui fournissant nil (b^.gauche).

Lorsque tu appelles parcours_prefixe avec nil, elle ne fait rien (tout est entre le si et le finsi).

Tu finis donc le parcours de « 2 » et tu remontes dans ta pile d'appels récursifs : parcours_prefixe appliqué à « 2 » retourne et on se retrouve dans la suite du parcours de « 1 » qui appelle maitnenant parcours_prefixe pour « 3 ».

Etc.

[allomona]

merci pour votre reponse

[allomona]

parcours_prefixe appliqué à « 2 » retourne

désolée j'ai pas compris qu'est ce que vous voulez dire par retourne

on se retrouve dans la suite du parcours de « 1 »

on est dans le noeud etiqueté 2 comment on s'est retrouvé dans celui etiqueté 1

[prgasp77]

Imagine le cas suivant :

Code :

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

1
2
3
4
5
6
algorithme a
début
   faire des trucs (a)
   f() (b)
   faire d'autres trucs (c)
fin.

Code :

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

1
2
3
4
fonction f
début
   faire des choses (d)
fin.

Lorsque a est exécuté, il fait des trucs, puis f est appelée. f fait des choses et se termine (on dit qu'elle retourne). a reprend son cours normal et fait d'autres trucs. L'exécution se fait donc dans cet ordre a -> b -> d -> b' -> c.


Dans ton cas, on était dans l'exécution de :

Code :

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

1
2
3
4
5
parcours_prefixe(1)
début
   parcours_prefixe(2)
   parcours_prefixe(3)
fin.

Le parcours de « 2 » s'est terminé ; on se retrouve donc à nouveau dans le parcours de « 1 » qui appelle maintenant le parcours de « 3 ». Celui-ci retourne aussi (puisque « 3 » est terminal). Finalement, on arrive à la fin du parcours de « 1 », qui retourne. Etc.

[allomona]

un trés grand merci c'est bien clair maintenant