<page>
    <title>Arbre (informatique)</title>
    <id>86120</id>
    <revision>
      <id>28586794</id>
      <timestamp>2008-04-12T19:37:49Z</timestamp>
      <contributor>
        <username>Tucsouffle</username>
        <id>98793</id>
      </contributor>
      <comment>/* Exemples d'arbres */ +arbre bicolore</comment>
      <text xml:space="preserve">{{Voir homonymes| Arbre (homonymie) }}
[[Image:binary_tree.svg|right|200px|thumb|Un [[arbre binaire]]]]
== Généralités ==

En [[informatique]], un '''arbre''' est une [[structure de données]] récursive générale, représentant un [[arbre (mathématiques)|arbre au sens mathématique]]. C'est un cas particulier de [[graphe (théorie des graphes)|graphe]] qui n'a qu'une seule source et aucun cycle.

Dans un arbre, on distingue deux catégories d'éléments :
* les &lt;font id=&quot;feuille&quot;&gt;'''feuilles'''&lt;/font&gt;, éléments ne possédant pas de fils dans l'arbre ;
* les &lt;font id=&quot;noeud&quot;&gt;'''nœuds'''&lt;/font&gt; internes, éléments possédant des fils (sous-branches).
La '''racine''' de l'arbre est le nœud ne possédant pas de parent.

La hauteur d'un arbre est la longueur du plus grand chemin de la racine à une feuille.

Chaque nœud possède une &lt;font id=&quot;étiquette&quot;&gt;'''étiquette'''&lt;/font&gt;, qui est en quelque sorte le « contenu » de l'arbre. L'étiquette peut être très simple: un nombre entier, par exemple. Elle peut également être aussi complexe que l'on veut : un objet, une instance d'une structure de données, un pointeur, etc. Il est presque toujours obligatoire de pouvoir comparer les étiquettes selon une relation d'[[ordre total]], afin d'implanter les algorithmes sur les arbres.

Par exemple, les dossiers de [[Windows 98]] et [[MS-DOS]] forment un arbre.

Les arbres sont en fait rarement utilisés en tant que tels, mais de nombreux types d'arbres avec une structure plus restrictive existent et sont couramment utilisés en [[algorithmique]], notamment pour gérer des [[base de données|bases de données]], ou pour l'indexation de fichiers. Ils permettent alors des recherches rapides et efficaces. Nous vous en donnons ici les principaux exemples :
*Les [[arbre binaire|arbres binaires]] dont chaque nœud a au plus deux fils : ils sont en fait utilisés sous forme d'[[arbre binaire de recherche|arbres binaires de recherche]], de [[Tas_(informatique)|tas]], d'[[Arbre_AVL|AVL]], ou encore d'[[arbre rouge-noir|arbres rouge-noir]]. Les deux derniers exemples sont des cas particuliers d'[[arbre équilibré|arbres équilibrés]], c'est-à-dire d'arbres dont les sous-branches ont environ la même hauteur. 
*Les arbres n-aires qui sont une généralisation des arbres binaires : chaque nœud a au plus n fils. Les [[arbre 2-3-4|arbres 2-3-4]] et les [[arbre B|arbres B]] en sont des exemples d'utilisation et sont eux aussi des [[arbre balancé|arbres balancés]].

== Construction ==
Pour construire un arbre à partir de cases ne contenant que des informations, on peut procéder de l'une des trois façons suivantes : 
# Créer une structure de données composée de : 
## l'étiquette (la valeur contenue dans le nœud), 
## un lien vers ''chaque'' nœud fils, 
## un arbre particulier, l'arbre vide, qui permettra de caractériser les feuilles. Une feuille a pour fils des arbres vides uniquement. 
# Créer une structure de données composée de : 
## l'étiquette (la valeur contenue dans le nœud),
## un lien vers le « premier » nœud fils (nœud fils gauche le cas échéant),
## un autre lien vers le nœud frère (le « premier » nœud frère sur la droite le cas échéant). 
# Créer une structure de données composée de : 
## l'étiquette (la valeur contenue dans le nœud),
## un lien vers le nœud père. 

On note qu'il existe d'autres types de représentation propres à des cas particuliers d'arbres. Par exemple, le [[tas]] est représenté par un tableau d'étiquettes.

== Parcours==
[[image:Boretti_Arbre_niveau.png|thumb|Arbre d'exemple pour les parcours d'arbre]]

===Parcours en largeur===
Le &lt;b&gt;parcours en largeur&lt;/b&gt; correspond à un parcours par ''niveau'' de nœuds de l'arbre. 
Un niveau est un ensemble de nœuds internes 
ou&lt;ref&gt;Le « ou » est large : un ''niveau'' peut recouvrir à la fois des nœuds et des feuilles ; en effet, toutes les feuilles d'un arbre ne sont pas nécessairement situées à la même « distance » du nœud racine.&lt;/ref&gt; 
de feuilles situés à la même 
« distance »&lt;ref&gt;La notion de ''distance'' est relative dans ce contexte : elle correspond usuellement au nombre d'arcs — ou d'arêtes — composant le plus court chemin depuis le nœud racine jusqu'au nœud considéré, interne ou feuille. En théorie, elle peut être plus élaborée. Un arbre étant un graphe particulier, ses arcs ou arêtes peuvent être pondérés. Cette pondération peut servir à l'évaluation d'une mesure entre deux nœuds quelconques de l'arbre. On parle de ''longueur'' du (plus court) chemin entre deux nœuds d'un arbre, la longueur étant distincte de la différence des hauteurs respectives.&lt;/ref&gt; 
du nœud racine — on parle aussi de nœud ou de feuille de même hauteur dans l'arbre considéré. 
L'ordre de parcours d'un niveau donné est habituellement conféré, de manière récursive, par l'ordre de parcours des nœuds parents — nœuds du niveau immédiatement supérieur. 

Ainsi, si l'arbre précédent est utilisé, le parcours sera &lt;tt&gt;A&lt;/tt&gt;, &lt;tt&gt;B&lt;/tt&gt;, &lt;tt&gt;C&lt;/tt&gt;, &lt;tt&gt;D&lt;/tt&gt;, &lt;tt&gt;E&lt;/tt&gt;, &lt;tt&gt;F&lt;/tt&gt; puis &lt;tt&gt;G&lt;/tt&gt;.

&lt;!-- Balise à déplacer dans une section ad hoc (section Références ou Notes) si d'autres notes sont créées. --&gt; 
&lt;references /&gt;

===Parcours en profondeur===
Le &lt;b&gt;parcours en profondeur&lt;/b&gt; est un parcours [[récursif]] sur un arbre. Il existe trois ordres pour cette méthode de parcours.

====Parcours en profondeur préfixé====
Dans ce mode de parcours, le nœud courant est traité avant le traitement des nœuds gauches et droits.
Ainsi, si l'arbre précédent est utilisé, le parcours sera &lt;tt&gt;A&lt;/tt&gt;, &lt;tt&gt;B&lt;/tt&gt;, &lt;tt&gt;D&lt;/tt&gt;, &lt;tt&gt;E&lt;/tt&gt;, &lt;tt&gt;C&lt;/tt&gt;, &lt;tt&gt;F&lt;/tt&gt; puis &lt;tt&gt;G&lt;/tt&gt;.

====Parcours en profondeur infixé====
Dans ce mode de parcours, le nœud courant est traité entre le traitement des nœuds gauches et droits.
Ainsi, si l'arbre précédent est utilisé, le parcours sera &lt;tt&gt;D&lt;/tt&gt;, &lt;tt&gt;B&lt;/tt&gt;, &lt;tt&gt;E&lt;/tt&gt;, &lt;tt&gt;A&lt;/tt&gt;, &lt;tt&gt;F&lt;/tt&gt;, &lt;tt&gt;C&lt;/tt&gt; puis &lt;tt&gt;G&lt;/tt&gt;.

====Parcours en profondeur suffixé====
Dans ce mode de parcours, le nœud courant est traité après le traitement des nœuds gauches et droits.
Ainsi, si l'arbre précédent est utilisé, le parcours sera &lt;tt&gt;D&lt;/tt&gt;, &lt;tt&gt;E&lt;/tt&gt;, &lt;tt&gt;B&lt;/tt&gt;, &lt;tt&gt;F&lt;/tt&gt;, &lt;tt&gt;G&lt;/tt&gt;, &lt;tt&gt;C&lt;/tt&gt; puis &lt;tt&gt;A&lt;/tt&gt;. Ce mode de parcours correspond à une [[notation polonaise inversée]].

== Exemples d'arbres ==
* Les [[Arbre binaire|arbres binaires]];
* Les [[Arbre B|arbres B]] (B-Tree);
* Les [[Arbre équilibré|arbres équilibrés]];
* Les [[Arbre syntaxique|arbres syntaxiques]];
* Les [[tas]];
* Les [[arbre couvrant de poids minimal|arbres couvrants]];
* Les [[octree]]s;
* Les [[Arbre AVL|Arbres AVL]];
* Les [[Arbre bicolore|Arbres bicolore]].

{{Wiktionnaire|arbre}}

[[Catégorie:Arbre (structure de données)]]

[[da:Træ (datastruktur)]]
[[de:Baum (Graphentheorie)]]
[[en:Tree (data structure)]]
[[es:Árbol (estructura de datos)]]
[[id:Pohon (struktur data)]]
[[it:Albero (informatica)]]
[[ja:木構造 (データ構造)]]
[[lt:Medis (duomenų struktūra)]]
[[nl:Tree]]
[[no:Tre (datastruktur)]]
[[pl:Drzewo (informatyka)]]
[[pt:Árvore (estrutura de dados)]]
[[uk:Дерево (структура даних)]]
[[zh:树 (数据结构)]]</text>
    </revision>
  </page>