Enoncé 5 : Récursivité - Arbres  Corrigé 5

Exercice 1 : Définition de fonctions récursives

Soit la fonction Reste(L) qui fournit la liste linéaire chaînée L sans le premier élément. Utiliser cette fonction pour trouver les fonctions récursives suivantes:

- TROUVE ( L, N) qui détermine si l'élément N existe ou non dans la liste linéaire chaînée L .

- COMMUN ( L1, L2 ) qui détermine si les deux listes linéaires L1 et L2 ont au moins un élément en commun.

- TOUS (L1, L2) qui détermine si tous les éléments de L1 existent dans L2.

Exercice 2 : Puzzle

Soit la procédure Construire ( Objet, Arbre1, Arbre2, Arbre) qui construit un arbre de racine Arbre à partir d'une valeur Objet et de deux sous arbres Arbre1 et Arbre2.

a) Ecrire cette procédure

b) Utiliser cette procédure pour compléter la fonction récursive Insérer ( X, A) ci-dessous qui insère l'élément X dans un arbre de recherche binaire et qui rend la référence de sa racine. Justifier.

                ?

c) Faire une trace en donnant l'état de l'arbre après chacune des opérations suivantes :

Arb = NIL ; Insérer(6, Arb) ; Insérer(1, Arb) ; Insérer(3, Arb); Insérer(8, Arb) ; Insérer(7, Arb).

Exercice 3 : Représentation séquentielle

Soit un arbre de recherche binaire représenté sous la forme séquentielle suivante :

- l'arbre est représenté par un tableau A

- le noeud à la position P du tableau A est le père implicite des noeuds aux positions 2P (fils gauche) et 2P+1 (fils droit).

a) Peut-on garder toutes les opérations du modèle sur les arbres de recherche binaire sous cette représentation ? Doit-on rajouter d'autres ?

b) Implémenter les opérations possibles.

c) Ecrire l'algorithme non récursif d'insertion d'un élément X dans un arbre de recherche binaire ainsi représenté.

* * * * *