Exercices (pc 5) Corrigé

Exercice 1 : En utilisant la formule

π(x, T_{1}, T_{2}, …, T_{n}) = (x, π(T_{1}), π(T_{2}), …, π(T_{n}))

on obtient la version récursive :

procedure parcours(r : noeud);
var n : noeud;
begin
write(r);
n:=Fg[r];
while n <> Vide do begin
 parcours(n);
 n:= Frd[n]
 end;
end;

Si par contre on utilise la formule

π(x, F) = (x, π(F))
π(T, F) = (π(T), π(F))

on obtient une autre version récursive:

procedure Parcours(r: noeud);
var n: noeud;
begin
 writeln(r);
 n:= Fg[r];
 if n <> vide then Prefixe(n);
 r:=Frd[r];
 if r <> vide then Prefixe(r)
end;

Version non récursive :

procedure Parcoursnrec (r: noeud);
 var
  m: noeud;
  P: array[1..N] of noeud;{pile}
  s: integer;{sommet de pile}
 label
  1, 2, 3;

 begin
  P[1] := r;
  s := 1;
1:{explorer les descendants du sommet de pile}
  write(P[s]);
  m := Fg[P[s]];
  if m = Vide then {P[s] est une feuille}
   goto 2
  else
   begin
    s := s + 1;
    P[s] := m;
    goto 1
   end;
2: {l'exploration du sommet est finie}
  if P[s] = r then
   goto 3
  else
   begin
    m := Frd[P[s]];
    s := s - 1;
    if m = Vide then {plus de freres}
     goto 2
    else
     begin
      s := s + 1;
      P[s] := m;
{commencer l'exploration depuis m}
      goto 1
     end
   end;
3:
 end;{Parcoursnrec}

Exercice 2 : Un arbre binaire complet ayant n noeuds internes a n+1 feuilles . En effet chaque noeud interne a deux fils qui sont des feuilles ou des noeuds internes. Tous les noeuds sauf la racine sont obtenus ainsi et donc

2i = i + f − 1

d’où f = i + 1.

On obtient un arbre binaire à n noeuds à partir d’un arbre binaire complet à n feuilles en supprimant les feuilles. On obtient ainsi la première bijection.

La deuxième s’obtient en considérant la représentation fils gauche-frère droit. 3