Les files

Prototype


Version de

Définition

Un arbre est une structure qui est :
  • soit vide\footnote{que nous noterons \Lambda. Concrètement, \Lambda 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.

Rendered by QuickLaTeX.com

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

Étiquettes et expressions

L’arbre étiqueté de la figure ?? représente l’expression arithmétique (a+b)*(a+c). Les noms attribués aux n\oe uds sont n_{1}, n_{2}, \ldots, n_{7} 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 n_{4} représente l’expression a.
  2. Chaque nœud interne n est étiqueté par un opérateur. Si n est étiqueté par un opérateur binaire \theta, comme + ou *, si son fils gauche représente l’expression E_{1} et son fils droit l’expression E_{2}, alors n représente l’expression (E_{1})\theta(E_{2}). Les parenthèses peuvent être retirées si aucune ambiguïté n’est à craindre.
Par exemple, l’opérateur + est associé au nœud n_{2} et ses fils gauche et droit représentent a et b respectivement. Ainsi n_{2} représente (a) + (b), ou simplement a + b. Le nœud n_{1} représente (a + b)*(a + c), puisque * est l’étiquette associée à n_{1} et puisque a + b et a + c sont les expressions représentées par n_{2} et n_{3} 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.

Rendered by QuickLaTeX.com

Dans un parcours préfixé, on ne considère que le premier passage par un nœud donné (*+ab+ac) ; 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 (ab+ac+*). 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  : (a+b) * (a+c).
Les files