Arbre cousu

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 \varnothing) à 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 :

Arbre cousu en préordre[modifier | modifier le code]

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 préordre xxxx

Arbre cousu en postordre[modifier | modifier le code]

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 postordre

Arbre cousu en inordre[modifier | modifier le code]

Un arbre dont le chaînage suit un parcours infixe de l'arbre : nœud fils gauche, nœud parent, nœud fils droit.

Arbre cousu en inordre

Dans le cas d'un arbre binaire de recherche, ce chaînage correspond à une liste chaînée triée.