Résumé du chapitre 13

  Les arbres


Nous avons eu l'occasion de présenter dans ce chapitre une nouvelle structure de données : les arbres.

Nous nous sommes plus particulièrement attachés à l'étude des arbres binaires étiquetés.

Un arbre binaire étiqueté par les éléments d'un ensemble non vide E est

Le parcours des différents n uds d'un arbre peut se faire de différentes manières. Nous avons érudié les parcours préfixe, infixe et postfixe.

À la différence des listes, les arbres ne constituent pas une structure prédéfinie en SCHEME. Nous sommes donc libres dans le choix de leur représentation. Le principe de l'abstraction des données nous permet cependant de les manipuler indépendamment du choix effectué.

Comme application des arbres, nous avons étudié les arbres binaires ordonnés :

un arbre est dit ordonné s'il est vide ou bien si

  1. les clefs des étiquettes des n uds de son sous-arbre gauche sont inférieures ou égales à la clef de l'étiquette de la racine,
  2. et, les clefs des étiquettes des n uds de son sous-arbre droit sont supérieures ou égales à la clef de l'étiquette de la racine,
  3. et ses sous-arbres (s'il en a) sont ordonnés.

Leur ensemble sera noté ABO(E).


next up previous
Next: Résumé du chapitre 14 Up: No Title Previous: Résumé du chapitre 12

Eric.Wegrzynowski
Thu Mar 20 13:58:10 MET 1997