Prototype |
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.
Étiquettes et expressions
L’arbre étiqueté de la figure ?? représente l’expression arithmétique![Rendered by QuickLaTeX.com (a+b)*(a+c)](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-914dd672e1e553e3b08d9ab609516096_l3.png)
![Rendered by QuickLaTeX.com n_{1}, n_{2}, \ldots, n_{7}](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-bb6fe2708f86644132b6289e8e6c7ff9_l3.png)
- 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
.
- 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.
![Rendered by QuickLaTeX.com n_{2}](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-22fd85fb8e86a16486c6b9a7dd3c65b0_l3.png)
![Rendered by QuickLaTeX.com a](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-5b3c447a32dd725fb1aaa99f7caea38e_l3.png)
![Rendered by QuickLaTeX.com b](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-2a6a1c8277992e81a80626f8fc9c76f5_l3.png)
![Rendered by QuickLaTeX.com n_{2}](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-22fd85fb8e86a16486c6b9a7dd3c65b0_l3.png)
![Rendered by QuickLaTeX.com a](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-5b3c447a32dd725fb1aaa99f7caea38e_l3.png)
![Rendered by QuickLaTeX.com b](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-2a6a1c8277992e81a80626f8fc9c76f5_l3.png)
![Rendered by QuickLaTeX.com a + b](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-0c8b91ab3021f0943aa8441b24ba5840_l3.png)
![Rendered by QuickLaTeX.com n_{1}](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-7257faf994f21da101fbf3605983adc9_l3.png)
![Rendered by QuickLaTeX.com (a + b)*(a + c)](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-3dd0931832b10c99815e844ae940e000_l3.png)
![Rendered by QuickLaTeX.com *](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-2a71e3dc843980b6ba5d9b9386f1964e_l3.png)
![Rendered by QuickLaTeX.com n_{1}](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-7257faf994f21da101fbf3605983adc9_l3.png)
![Rendered by QuickLaTeX.com a + b](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-0c8b91ab3021f0943aa8441b24ba5840_l3.png)
![Rendered by QuickLaTeX.com a + c](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-33f85b217ccce9a7ac4d1f5c86eca32a_l3.png)
![Rendered by QuickLaTeX.com n_{2}](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-22fd85fb8e86a16486c6b9a7dd3c65b0_l3.png)
![Rendered by QuickLaTeX.com n_{3}](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-4f89cfc47acbaf5e875e20c93248133d_l3.png)
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 *+ab+ac](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-24a962835ddf7614ce39fb3f2eea6b90_l3.png)
![Rendered by QuickLaTeX.com ab+ac+*](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-fe1545f53ce4324c0e885d12b098cbc9_l3.png)
![Rendered by QuickLaTeX.com (a+b) * (a+c)](https://algotaf.dhenin.fr/wp-content/ql-cache/quicklatex.com-26311162f1e2dfda2835bde911e16e2c_l3.png)