Nous définissons ici la notion d’arbre, et en particulier les arbres binaires, ainsi que le vocabulaire qui leur est associé.
I. Arbres quelconques
1) Définition d’un arbre enraciné
Un arbre enraciné (ou arborescence) est constitué de nœuds organisés de manière hiérarchique : c’est un graphe non orienté, connexe, sans cycle dans lequel on a choisi un nœud particulier appelé la racine. Chaque nœud peut être étiqueté par une information.
Doc 1Arbre enraciné, étiqueté par des nombres entiers
2) Caractéristiques d’un arbre
Dans un arbre, chaque nœud a exactement un seul nœud père, à l’exception de l’unique nœud racine qui n’en a pas. Chaque nœud peut avoir un nombre arbitraire de fils, dont il est le père.
La taille d’un arbre est son nombre de nœuds (9 sur le document 1).
Les nœuds qui n’ont pas de fils sont appelés les feuilles ou nœuds externes. Les autres sont des nœuds internes.
L’arité d’un nœud est son nombre de fils. Deux nœuds ayant le même père sont dits nœuds frères (nœuds 67 et 79 sur le document 1).
La profondeur d’un nœud est la longueur du chemin le plus court vers la racine (la racine a donc pour profondeur 0). La hauteur d’un arbre est la profondeur du nœud le plus profond (0 s’il est réduit à la racine et, par convention, −1 si l’arbre est vide). L’arbre du document 1 a pour hauteur 3.
À noterLa hauteur d’un arbre est parfois définie différemment, telle que la hauteur de l’arbre vide soit 0 et celle de l’arbre réduit à une racine soit 1.
II. Arbres binaires
1) Définitions
Un arbre binaire est un arbre dont chaque nœud a au plus deux fils généralement ordonnés : le fils gauche et le fils droit.
Doc 2Arbre binaire enraciné, étiqueté avec des lettres
Un arbre binaire est équilibré si, pour chaque nœud interne, les sous-arbres gauche et droit ont une hauteur qui diffère de 1 au plus.
Un arbre binaire est complet (à gauche) si tous ses niveaux sont remplis, sauf éventuellement le dernier (et que les feuilles du dernier niveau sont tassées à gauche).
Doc 3Arbre binaire complet à gauche
Attention
Les qualificatifs complet ou équilibré, pour un arbre binaire, ont des définitions variables : soyez toujours attentif à la définition qui est donnée.
2) Parcours d’un arbre binaire
Un parcours d’arbre définit dans quel ordre on parcourt ses nœuds.
Dans le cas où un arbre est parcouru en largeur d’abord, l’arbre est parcouru étage par étage : la racine, puis les fils de la racine, puis les petits-fils de la racine… jusqu’aux feuilles. À chaque étage, les nœuds sont parcourus de gauche à droite.
Exemple : Sur l’arbre du document 2, on obtient : T–Y–O–P–H–N.
Dans le cas où il est parcouru en profondeur d’abord, l’un des deux sous-arbres est complètement exploré avant que l’exploration du second ne commence. On distingue trois types de parcours selon l’ordre dans lequel le sous-arbre gauche, le sous-arbre droit et la racine sont explorés :
Dans un parcours préfixe, ou préordre, chaque nœud est visité avant que ses fils le soient. On part de la racine, puis on visite le fils gauche, puis le fils droit. Exemple : sur le document 2, T–Y–P–O–H–N.
Dans un parcours infixe, ou en ordre, chaque nœud est visité après son fils gauche mais avant son fils droit (fils gauche, racine, fils droit). Exemple : sur le document 2, P–Y–T–H–O–N.
Dans un parcours postfixe, ou postordre, chaque nœud est visité après que ses fils le soient (fils gauche, fils droit, racine). Exemple : sur le document 2, P–Y–H–N–O–T.