Notion d'arbre Un arbre est un ensemble de noeuds organisés de façon hiérarchique à partir d'un noeud distingué qui est la racine, les autres noeuds étant eux-mêmes structurés sous forme d'arbres, les sous-arbres immédiats de l'arbre.
 
Voici trois exemples d'arbres:
 
 
On nomme étiquette l'information attachée aux noeuds, ce qui peut être le cas pour tous les noeuds de l'arbre (deux premiers exemples ci-dessous) ou uniquement aux feuilles (dernier exemple ci-dessous).
 
Intuitivement, les feuilles sont les noeuds qui « n'ont rien au-dessous ».
 
L'arbre dont l'ensemble des noeuds est vide est nommé l'arbre vide. Selon l'usage que l'on veut faire des arbres, l'arbre vide peut exister ou non dans l'ensemble des arbres considérés. Ainsi, on peut voir les arbres de deux façons:

• exactement comme le suggère les dessins ci-dessus: il n'y a rien au dessous des feuilles (et une feuille est alors un arbre qui n'a pas de sous-arbre immédiat),
• en considérant que les sous-arbres des feuilles existent et sont (tous) égaux à l'arbre vide. Pour indiquer l'existence de ces arbres vides, dans les dessins, nous ajouterons les traits au-dessous des feuilles:

 
 

devient

 

 
Un arbre est un arbre binaire lorsque c'est l'arbre vide ou lorsqu'il a exactement deux sous-arbres immédiats et que ceux-ci sont eux-mêmes des arbres binaires.
 
Différentes structures de données « arbre »  
La notion d'arbre peut aider pour représenter toute situation hiérarchique:

• sommaire d'un livre (une partie comportant des chapitres qui comportent des sections qui comportent des sous-sections...),
• analyse grammaticale d'une phrase (une phrase est composée d'un sujet, d'un verbe et d'un complément d'objet, le sujet étant un groupe nominale composé d'un article, d'un adjectif et d'un nom, le verbe...),
• classification des animaux,
• arbre généalogique,
• ...

 
Notons qu'il existe plusieurs « sortes » d'arbres comme structures de données, selon l'endroit où l'on attache les informations (tous les noeuds ou uniquement aux feuilles), selon le nombre de sous-arbres immédiats de chaque noeud (fixe, borné ou non borné) et selon l'existence ou non de l'arbre vide.
 
Nous verrons par la suite les « arbres binaires » (information attachée à chaque noeud, existence de l'arbre vide, pour chaque noeud exactement deux sous-arbres immédiats) et les « arbres généraux » (information attachée à chaque noeud, pas d'arbre vide, pour chaque noeud nombre quelconque de sous-arbres immédiats).