Définition d'un arbre

Un arbre est une structure de données. Comme pour un arbre naturel, nous distionguons un certain nombre d'éléments constituants :

• nœud : le nœud est le point de départ d'une ou de plusieurs branches. Nous pouvons utiliser la terminologie de la généalogie pour désigner les relations qu'il existe entre les nœuds : le parent, le grand-parent, les enfants, le fils, le frère (nœud de même niveau et de même parent), l'oncle (le frère du parent), le cousin (nœud de même niveau mais de parent différent), etc.
• racine : la racine est un nœud particulier car il ne possède pas de nœud parent.
• feuille : une feuille est un nœud particulier car il ne possède pas d'enfant.

Selon la théorie des graphes, un arbre est un graphe (généralement non orienté car nous n'avons pas de pointeur vers le parent) qui possède uneseule racine (sommet de degré nul)¹, et n'admet pas de cycle.

En plus de ces termes, nous aurons à utiliser différentes notions relatives aux arbres :

• arête : si nous considérons l'arbre comme un graphe non orienté, nous préférerons employer le terme arête à la place de branche pour désigner le segment de droite qui relie deux nœuds.
• profondeur d'un nœud : c'est la distance d'un nœud par rapport à la racine (la racine + le nombre de nœuds entre la racine et le nœud + le nœud lui même).
• hauteur de l'arbre : c'est la profondeur de la feuille la plus basse, ou encore la plus grande profondeur parmi toutes les feuilles.
• taille de l'arbre : c'est le nombre total de nœuds présents dans l'arbre. Selon les cas, nous pouvons préciser qu'il s'agit d'une taille de l'arbre sans la racine ou sans les feuilles.

Jusqu'à présent, nous ne nous sommes préoccupés que de la structure de l'arbre, mais il est intéressant de pouvoir y placer certaines informations (il est temps que l'arbre porte ses fruits). Nous pouvons utiliser chaque nœud pour y placer de l'information. Si ces informations possèdent une manière de les comparer, la structure de l'arbre se prête assez bien à ce genre de besoin, comme nous le verrons plus tard.

Comme l'informatique est par essence dichotomique car basée sur la dualité 0-1 du binaire, nous pouvons nous pencher sur certains arbres particulier, les arbres binaires, car ils sont les plus faciles à implémenter. Nous ne devons cependant pas oublier que la définition même de la structure en arbre admet plus de deux enfants pour chaque nœud, et nous serons amenésà utiliser aussi ce genre d'arbre.

Structure générale d'un arbre binaire

Afin de répondre aux différents besoins, nous avons besoin de trois éléments :

• un moyen d'atteindre le fils de gauche
• la donnée utile, ou un moyen d'atteindre cette donnée
• un moyen d'atteindre le fils de droite

Parcourir un arbre binaire

Pour chaque nœud (y compris la racine), trois possibilités s'offrent à nous :

• Nous nous dirigeons vers la branche de gauche si elle existe (G).
• Nous nous dirigeons vers la branche de droite si elle existe (D).
• Nous traitons la valeur courante (T).

Nous pouvons combiner ces actions de différentes manières, et nous devons considérer la position du traitement de la valeur courante (T).
Ce traitement peut se faire à trois moments :

• Avant toute décision de direction (ex: TGD). Nous parlerons de traitement préfixe.
• Après la première décision (ex: GTD). Nous parlerons de traitement infixe.
• Après toute décision de direction (ex: GDT). Nous parlerons de traitement postfixe.