procedure Parcours(val x: sommet) debut (1) si Existe_Fils(x) alors (2) y := Premier_Fils(x); Parcours(y); (2') tant que Existe_Frere(y) faire (3) y := Frere(y); Parcours(y); (3') fin tantque sinon (4) fin si (5) fin
fonction Parcours(val x: sommet) var minLocal:entier debut si Existe_Fils(x) alors (2) y := Premier_Fils(x); minLocal:=1+Parcours(y); (2') tant que Existe_Frere(y) faire (3) y := Frere(y); minLocal:=min(1+Parcours(y),minLocal); (3') fin tantque sinon (4) retourner(0) fin si; retourner(minLocal) (5) finAppel : k:=Parcours(x) avec type x:sommet; type k:entier;
type sommet:entier;A tout moment le nombre de sommets d'un arbre peut être renvoyé par la procédure récursive donc qu'elle soit transformée en fonction.
fonction Parcours(val x: sommet;ref taille:tableau[1..N] d'entiers):entier; debut (1)taille[x]:=1; si Existe_Fils(x) alors (2) y := Premier_Fils(x); taille[x]:=taille[x]+Parcours(y); (2') tant que Existe_Frere(y) faire (3) y := Frere(y); taille[x]:=taille[x]+Parcours(y); (3') fin tantque fin si (5) retourner(taille[x]) finAppel : k:=Parcours(x,taille) avec type x:entier; type taille:tableau[1..N]d'entiers;
procedure Mystere (ref A : Arbre); var P1, P2 : Pile de sommet; debut Vider_Pile(P1); Vider_Pile(P2); Empiler(Racine(A),P1); tant que non Pile_Vide?(P1) faire // boucle tant que principale x := Valeur_Pile(P1); afficher(x); Depiler(P1); si Existe_Fils?(x) alors y := Premier_Fils(x); Empiler(y, P2); tant que Existe_Frere?(y) faire // 1ere boucle secondaire y := Frere(y); Empiler(y, P2); fin tant_que; tant que non Pile_Vide(P2) faire // 2eme boucle secondaire Empiler(Valeur_Pile(P2), P1); Depiler(P2); fin tant_que; fin si; fin tant_que; fin;
Sommets | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Premier_Fils | 2 | 4 | 0 | 0 | 7 | 0 | 0 |
Frere | 0 | 3 | 0 | 5 | 6 | 0 | 0 |
étape 1 : 1 étape 2 : 3,2 étape 3 : 3,6,5,4 étape 4 : 3,6,5 étape 5 : 3,6,7 étape 8 : 3,6 étape 9 : 3 étape 10 : sortie de boucle, la pile P1 est vide