Un arbre est formé d’une racine qui est l’élément à la base de l’arbre, et d’un nombre fini d’arbres qui lui sont
raccordés appelés sousarbres.
Chaque élément d’un arbre peut avoir plusieurs successeurs (vous avez deux parents) mais un seul prédécesseur.
Seule la racine n’a pas de prédécesseur.
b. Terminologie
Les arbres utilisent une terminologie particulière qui reprend en gros celle de la nature et de la généalogie :
q Un noeud ou sommet est un élément quelconque de l’arbre. Dans un arbre généalogique, chaque individu
représente un noeud ou sommet : il a plusieurs successeurs mais un seul prédécesseur.
q La racine est le premier élément de l’arbre, n’ayant pas de prédécesseur dans la hiérarchie.
q Une feuille ou noeud terminal, ou noeud final est un élément qui n’a pas de successeur.
q Un noeud interne est un noeud qui n’est ni racine, ni feuille, qui a donc un prédécesseur et des successeurs.
q Un arc relie deux noeuds.
q Une branche est le chemin qui relie la racine à une feuille.
Du côté du rapprochement généalogique légèrement sexiste, vous trouverez les termes suivants :
q Le père est le prédécesseur unique d’un noeud.
q Les fils sont les n successeurs d’un noeud.
q Les noeuds de père identique sont des frères.
q Le noeud le plus à gauche de l’arbre est l’aîné.
Un arbre peut être décrit horizontalement et verticalement.
c. Description horizontale
Horizontalement, un arbre naire est un arbre dont le nombre maximum de fils par noeud est n. Les fils sont
regroupés par niveaux. Un niveau est l’ensemble des noeuds à égale distance de la racine. Le premier niveau est la
racine, le deuxième les fils de la racine, le troisième les fils des fils, et ainsi de suite. Quand chaque noeud d’un niveau
a exactement n fils, le niveau est dit saturé.
Un arbre est strictement complet si tous les niveaux sont complets. Il est simplement complet au sens large si tous
les niveaux intermédiaires sont complets mais qu’il manque des feuilles. Dans un arbre strictement complet, la racine
et tous les noeuds internes ont exactement n fils, ni plus ni moins.
d. Description verticale
La hauteur d’un arbre est le nombre de noeuds du plus long chemin direct, la plus longue branche entre la racine et
une feuille, racine et feuille inclues. Si l’arbre dispose d’une racine, de deux fils et qu’un des fils a une feuille, la
hauteur de l’arbre est 3.
e. L’arbre binaire
Un arbre binaire est un arbre dont chaque noeud a au plus deux fils. Depuis la racine, l’arbre binaire est constitué de
deux sousarbres différenciés, le sousarbre droit et le sousarbre gauche.
Il existe des arbres à trois, quatre, n fils. Cependant seuls les arbres binaires seront abordés ici et notamment les
arbres binaires ordonnés. Le schéma suivant montre un arbre binaire strictement complet de hauteur 3.
- 2 -
© ENI Editions - All rigths reserved - Jonifar lina
188
raccordés appelés sousarbres.
Chaque élément d’un arbre peut avoir plusieurs successeurs (vous avez deux parents) mais un seul prédécesseur.
Seule la racine n’a pas de prédécesseur.
b. Terminologie
Les arbres utilisent une terminologie particulière qui reprend en gros celle de la nature et de la généalogie :
q Un noeud ou sommet est un élément quelconque de l’arbre. Dans un arbre généalogique, chaque individu
représente un noeud ou sommet : il a plusieurs successeurs mais un seul prédécesseur.
q La racine est le premier élément de l’arbre, n’ayant pas de prédécesseur dans la hiérarchie.
q Une feuille ou noeud terminal, ou noeud final est un élément qui n’a pas de successeur.
q Un noeud interne est un noeud qui n’est ni racine, ni feuille, qui a donc un prédécesseur et des successeurs.
q Un arc relie deux noeuds.
q Une branche est le chemin qui relie la racine à une feuille.
Du côté du rapprochement généalogique légèrement sexiste, vous trouverez les termes suivants :
q Le père est le prédécesseur unique d’un noeud.
q Les fils sont les n successeurs d’un noeud.
q Les noeuds de père identique sont des frères.
q Le noeud le plus à gauche de l’arbre est l’aîné.
Un arbre peut être décrit horizontalement et verticalement.
c. Description horizontale
Horizontalement, un arbre naire est un arbre dont le nombre maximum de fils par noeud est n. Les fils sont
regroupés par niveaux. Un niveau est l’ensemble des noeuds à égale distance de la racine. Le premier niveau est la
racine, le deuxième les fils de la racine, le troisième les fils des fils, et ainsi de suite. Quand chaque noeud d’un niveau
a exactement n fils, le niveau est dit saturé.
Un arbre est strictement complet si tous les niveaux sont complets. Il est simplement complet au sens large si tous
les niveaux intermédiaires sont complets mais qu’il manque des feuilles. Dans un arbre strictement complet, la racine
et tous les noeuds internes ont exactement n fils, ni plus ni moins.
d. Description verticale
La hauteur d’un arbre est le nombre de noeuds du plus long chemin direct, la plus longue branche entre la racine et
une feuille, racine et feuille inclues. Si l’arbre dispose d’une racine, de deux fils et qu’un des fils a une feuille, la
hauteur de l’arbre est 3.
e. L’arbre binaire
Un arbre binaire est un arbre dont chaque noeud a au plus deux fils. Depuis la racine, l’arbre binaire est constitué de
deux sousarbres différenciés, le sousarbre droit et le sousarbre gauche.
Il existe des arbres à trois, quatre, n fils. Cependant seuls les arbres binaires seront abordés ici et notamment les
arbres binaires ordonnés. Le schéma suivant montre un arbre binaire strictement complet de hauteur 3.
- 2 -
© ENI Editions - All rigths reserved - Jonifar lina
188