Arbre cousu
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
La notion d'arbre cousu s'applique à un arbre binaire. Coudre cet arbre 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
) à son successeur.
Attention : il est nécessaire de matérialiser les nouvelles liaisons de manière différente que les 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).
D'une manière générale, on dénombre trois sortes d'arbre cousus :
[modifier] Arbre cousu en préordre
Un arbre dont le chaînage suit un parcours préfixe de l'arbre: Noeud parent en premiers, noeuds enfants ensuite.
[modifier] Arbre cousu en postordre
Un arbre dont le chaînage suit un parcours postfixe de l'arbre: Noeuds enfants en premiers, noeud parent en dernier.
[modifier] Arbre cousu en inordre
Un arbre dont le chaînage suit un parcours infixe de l'arbre: Noeuds fils gauche, noeud parent, noeud droite.
Dans le cas d'un arbre binaire de recherche, ce chaînage correspond à une liste chaînée triée.
