Résumé du chapitre 13

  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

• soit l'arbre vide ,
• soit un triplet constitué d'un élément , et de deux arbres binaires et .

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).