Arbre cousu

Arbre cousu

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 \empty \,) à 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

Un arbre dont le chaînage suit un parcours préfixe de l'arbre: Nœud parent en premiers, nœuds enfants ensuite.

Arbre cousu en préordre

Arbre cousu en postordre

Un arbre dont le chaînage suit un parcours postfixe de l'arbre: Nœuds enfants en premiers, nœud parent en dernier.

Arbre cousu en postordre

Arbre cousu en inordre

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

Arbre cousu en inordre

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arbre cousu de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Arbre Cousu — 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… …   Wikipédia en Français

  • Arbre Binaire — En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus… …   Wikipédia en Français

  • Arbre binaire — Pour les articles homonymes, voir Arbre (homonymie). En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine.… …   Wikipédia en Français

  • Armorial des communes du Pas-de-Calais-1 (A-C) — Cette page donne les armoiries (figures et blasonnements) des communes du Pas de Calais de A à C. Armorial des communes du Pas de Calais 1 (A C) Armorial des communes du Pas de Calais 2 (D H) Armorial des communes du Pas de Calais 3 (I P)… …   Wikipédia en Français

  • Capelle-en-Artois — Capelle lès Hesdin Capelle lès Hesdin Détail Administration Pays France Région Nord Pas de Calais …   Wikipédia en Français

  • Capelle-les-Hesdin — Capelle lès Hesdin Capelle lès Hesdin Détail Administration Pays France Région Nord Pas de Calais …   Wikipédia en Français

  • Capelle-lès-Hesdin — 50° 20′ 32″ N 1° 59′ 52″ E / 50.3422222222, 1.99777777778 …   Wikipédia en Français

  • Armorial Des Communes Des Hautes-Pyrénées — Cette page donne les armoiries (figures et blasonnements) des communes des Hautes Pyrénées. Sommaire  …   Wikipédia en Français

  • Armorial des communes des Hautes-Pyrenees — Armorial des communes des Hautes Pyrénées Cette page donne les armoiries (figures et blasonnements) des communes des Hautes Pyrénées. Sommaire  …   Wikipédia en Français

  • Armorial des communes des Hautes-Pyrénées — Cette page donne les armoiries (figures et blasonnements) des communes des Hautes Pyrénées. Sur les autres projets Wikimedia : « Armorial des communes des Hautes Pyrénées », sur Wikimedia Commons (ressources multimédia) …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”