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 :

void Parcours(int r) {
 int n;
 printf("%d",r);
 n= Fg[r];
 while (n != VIDE) {
  Parcours(n);
  n= Frd[n];
  }
}

Si par contre on utilise les formules

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

on obtient une autre version récursive (identique au parcours d’un arbre binaire):

void Parcours(int r) {
 int n;
  printf("%d",r);
  n= Fg[r];
  if (n != VIDE) Prefixe(n);
  n= Frd[r];
  if (n != VIDE)  Prefixe(n);
}

Version non récursive :

void ParcoursNrec (int n) {
  do {
    printf("%d",n);
    if (Fg[n] == VIDE) {
      while (Frd[n] == VIDE && P[n] != VIDE)
        n= P[n];
      if (P[n] != VIDE)
        n=Frd[n];
     } else
      n= Fg[n];
  } while (P[n] != VIDE);
}

Exercice 2 : La version récursive est encore plus simple :

void Parcours(int n) {
  printf("%d",n);
  if (Fg[n] != VIDE) Parcours(Fg[n]);
  if (Fd[n] != VIDE) Parcours(Fd[n]);
}

Voici une solution non récursive :

void ParcoursNrec (int n) {
  int p;
  do {
    printf("%d",n);
    if (Fg[n] == VIDE) {
      p= P[n];
      while (n == Fd[p] && p != VIDE) {
        n= p;
        p= P[p];
      }
      if (p != VIDE)
        n=Fd[p];
     } else

      n= Fg[n];
  } while (P[n] != VIDE);
}

Exercice 3 : 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.