Enoncé 21 : Listes linéaires chaînées - Arbres - Hachage externe - Arbres B  Corrigé 21

Exercice 1 : Suppression dans une liste bilatérale

Soit dans une liste linéaire chaînée bidirectionnelle P le pointeur d'un élément. Ecrire l'algorithme qui supprime cet élément.

Exercice 2 : Parcours Inordre avec pile

Donner l'algorithme de parcours inordre (T1 N T2) itératif dans un arbre de recherche binaire avec utilisation d'une pile.

Montrer sur un exemple comment représenter une expression arithmétique par un arbre binaire. Donner l'algorithme récursif d'évaluation.

Donner le schéma relatif à un fichier organisé en h-code avec la méthode dite d'essai linéaire.

- Décrire la structure.

- Ecrire le module de recherche.

- Utiliser le module de recherche pour écrire l'algorithme d'insertion.

Donner la définition d'un arbre B d'ordre m. Montrer la construction de l'arbre à partir d'un exemple.