Arbre cousu
{{#invoke:Bandeau|ébauche}}
En algorithmique, un arbre cousu, ou threaded tree en anglais<ref>Une référence pour la traduction en français : Modèle:Lien web.</ref>, est une structure de données, basée sur un arbre binaire.
Principe
Coudre un arbre binaire revient à :
- parcourir cet arbre en parcours préfixe, postfixe ou infixe ;
- dans le cadre de ce parcours, lier le fils droit de chaque feuille (originellement, il s'agit de <math>\varnothing</math>) à son successeur.
Il est nécessaire de matérialiser les nouvelles liaisons de manière différente des liaisons père-fils de l'arbre de départ. Dans le cas contraire, la figure ne serait plus un arbre (présence de cycles).
Types
D'une manière générale, on dénombre trois sortes d'arbre cousus :
Arbre cousu en préordre
Un arbre dont le chaînage suit un parcours préfixe de l'arbre : nœuds parents en premier, nœuds enfants ensuite.
Arbre cousu en postordre
Un arbre dont le chaînage suit un parcours postfixe de l'arbre : nœuds enfants en premier, nœuds parents en dernier.
Arbre cousu en inordre
Un arbre dont le chaînage suit un parcours infixe de l'arbre : nœud fils gauche, nœud parent, nœud fils droit.
Dans le cas d'un arbre binaire de recherche, ce chaînage correspond à une liste chaînée triée.
Historique
Le concept d'arbre cousu est dû à Joseph Morris qui le publia en 1979<ref>Modèle:Article </ref>.
Notes et références
<references />
