Bonjour ! 

J'essaye de comprendre depuis de longues minutes un algorithme récursif sur un arbre binaire.

Je comprends le principe de l'algo de parcours de l'arbre binaire en préfixe avec une pile. Mais pour le parcours récursif, j'ai vraiment du mal je saisis vraiment pas.

Je pense que c'est le principe de la récursivité que je ne comprends car les autres exercices de cours, j'ai du mal à en saisir le sens.

Voici l'algorithme en question : 

Procédure ParcoursPrefixe(Noeud *N)

Début

si N != NULL

   alors

       ecrire(N->valeur); 
       ParcoursPrefixe(N->filsG); 
       ParcoursPrefixe(N->filsD);

    fin

Fin

Merci d'avance si vous m'aidez à comprendre ! 

-
Edité par Palipica 27 octobre 2016 à 17:38:21

C'est pourtant simple, ça dit que :

pour éplucher un tas de patates :

• tu attrapes une patate et tu l'épluches
• et après tu épluches le tas de patates qui reste

sauf si le tas de patates est vide parce que là il n'y a rien à faire.

Donc pour afficher tout ce qu'il y a dans un arbre, tu affiches d'abord la valeur qui est à la racine, puis tu t'occupes de faire afficher tout ce qui est à gauche, et enfin tout ce qui est à droite.

Sauf bien entendu si l'arbre est vide, parce que là il n'y a rien à faire.

-
Edité par michelbillaud 27 octobre 2016 à 18:00:05

Je comprends le principe en lisant l'algorithme mais de là à le faire moi même..

par exemple là je regarde celui pour trouver la hauteur  :

IF (A=NULL)
    hauteur = -1;
ELSE
    hauteur = 1 + (max(hauteur(A.fg), hauteur(A.fd))
return(hauteur)

J'essaye d'imaginer qu'on a un gros bloc à gauche et à droite avec une racine (comme s'il n'ya avait qu'un seul sous arbre gauche et un seul droit), contenant eux-même des sous arbres. ça me permet de visualiser. Mais ce genre de visualisation marche que dans ce cas j'ai l'impression...

Non ça marche très bien, c'est exactement ça.

Exprimer les choses récursivement, sur un arbre binaire, ça veut dire qu'on montre la relation entre le traitement de l'arbre complet, la valeur de la racine, et le traitement des deux sous arbres.

Par exemple si tu sais que le sous arbre de gauche est de hauteur 5, et celui de droite de hauteur 8, tu en conclues que la hauteur totale est 8+1 = 1 + max(hauteur(gauche) + hauteur(droite))

Si tu sais que la somme de tout ce qu'il y a à gauche est 12, et tout ce qu'il y a à droite fait 7, et que la racine contient 3, la somme est  12+7+3 = total(gauche)+total(droite)+valeur(racine).

      3
     /  \
    8    4
   /    / \
  2    2   1
 / \
1  1

C'est en fait bien plus naturel que de dire, bon alors je vais sur le fils gauche, et puis j'empile machin truc.

PS 1 la méthode pour y arriver, c'est de prendre un exemple, d'écrire la relation qu'il y a entre les différents éléments, et de généraliser. C'est tout bête.

PS 2 il faut voir comment tu comptes la hauteur : en nombre d'étages de sommets - dans ce cas un arbre à 2 sommets est de hauteur 2 - ou en longueur de branche, dans ce cas  c'est 1.

      R         
     /
    S

Mais un arbre vide, ça va pas faire -1.

-
Edité par michelbillaud 27 octobre 2016 à 18:56:00

D'accord ! 

Va falloir que je bosse à fond pour mon contrôle ! 

Si jamais j'ai de nouvelles questions, je repost un message ici.

Merci !