Previous: Les files

Prototype

Next: Parcours d’arbres

Définition

Un arbre est une structure qui est :

• soit vide\footnote{que nous noterons . Concrètement, pourra être 0, -1 ou tout autre valeur significative dans un contexte particulier.},
• soit composée d’un {\em n\oe ud} chaîné à zéro un ou plusieurs sous-arbres ordonnés de gauche à droite.

Un sous-arbre est donc un n\oe ud,\\ la {\em racine} est le n\oe ud qui n'{\bf est} pas un sous-arbre,\\ une {\em feuille} est un n\oe ud qui n{\bf ‘a} pas de sous-arbre.

\label{Expression} \markboth{Arbres}{Arbres}

Étiquettes et expressions

L’arbre étiqueté de la figure ?? représente l’expression arithmétique . Les noms attribués aux n\oe uds sont et les étiquettes apparaissent, comme c’est l’usage, à côté des n\oe uds. Les règles imposées à un arbre pour qu’il représente une expression sont les suivantes :

1. Chaque feuille est étiquetée par un opérande et est constituée de cet opérande uniquement. Ainsi la feuille représente l’expression .
2. Chaque nœud interne est étiqueté par un opérateur. Si est étiqueté par un opérateur binaire , comme ou , si son fils gauche représente l’expression et son fils droit l’expression , alors représente l’expression ()(). Les parenthèses peuvent être retirées si aucune ambiguïté n’est à craindre.

Par exemple, l’opérateur + est associé au nœud et ses fils gauche et droit représentent et respectivement. Ainsi représente () + (), ou simplement . Le nœud représente , puisque est l’étiquette associée à et puisque et sont les expressions représentées par et respectivement.

Parcours d’arbres

Il existe plusieurs moyens de parcourir les nœuds d’un arbre. Les trois parcours les plus importants sont les parcours préfixé, {postfixé et infixé ; ces parcours peuvent être définis récursivement.
Il existe un moyen pratique pour simuler les trois parcours d’arbre : imaginons que l’on parcourt l’arbre depuis sa racine, dans le sens contraire à celui des aiguilles d’une montre, en en restant toujours le plus près possible.

Dans un parcours préfixé, on ne considère que le premier passage par un nœud donné () ; dans un parcours postfixé, on ne prend en compte que le dernier passage par un nœud, lors de la remontée vers son père (). Pour un parcours infixé, on liste une feuille la première fois qu’on la rencontre, mais on ne liste un nœud non terminal qu’à la deuxième rencontre  : .

Previous: Les files

Next: Parcours d’arbres