Structures de données et de fichiers
|
Enoncé 22 : Arbres - Récursivité - Piles - Files d'attente - Arbre de recherche m-aire - Arbres B Corrigé 22
Exercice 1 : Parcours d'un arbre de recherche binaire - Transformation récursif --> itératif
Soit un arbre de recherche binaire.
- Donner l'algorithme non récursif de recherche d'un élément.
- Donner l'algorithme de parcours "inordre" avec utilisation d'une pile.
- Donner l'algorithme récursif de parcours postordre.
- Donner la traduction automatique de ce dernier en un algorithme itératif ( algorithme informel)
Exercice 2 : Implémentation d'une pile
Implémenter le modèle de pile avec les listes linéaires chaînées.
Exercice 3 : Implémentation d'une pile de files d'attente
Donner deux implémentations différentes pour une pile de files d'attente (schémas et structures de données)
Exercice 4 : Code de HUFFMAN
Donner le code de Huffman pour les caractères suivants avec leurs probabilités d'apparition :
a = .12 b =.18 c = .32
d = .2 e = .08 f = .1
Exercice 5 : Construction d'un arbre de recherche m-aire
Construire l'arbre de recherche m-aire d'ordre 3 pour la séquence : 12, 15, 18, 3, 2, 12, 16, 14, 35, 46, 52
Exercice 6 : Construction d'un arbre B
Construire l'arbre B d'ordre 3 avec la même séquence de l'exercice 5.
* * * * *
