Un arbre est une structure homogène dont chaque élément, appelé noeud, contient de l'information et plusieurs liens (pointeurs) vers des éléments du même type.
D'une manière plus formelle, on peut dire qu'un arbre de type de base
T est :
Fig.8.1. Illustration d'une structure d'arbre
Définitons
Le niveau d'un noeud est le nombre d'arcs qu'il faut parcourir pour arriver à ce noeud. La racine est de niveau 1.
La profondeur d'un arbre (ou hauteur) est le nombre maximum d'arcs qu'il faut parcourir pour aller de la racine à une feuille.
Les noeuds terminaux (qui n'ont pas de descendants) sont appelés feuilles. Les noeuds non-terminaux sont appelés noeuds intérieurs.
Un noeud Y, situé immédiatement sous un noeud X, est appelé le descendant (direct) de X. Inversement, X est appelé l'ancêtre (direct) de Y.
Le nombre de sous-arbres associés à un noeud (nombre de descendants directs) est appelé le degré du noeud. Le degré d'un arbre correspond au degré le plus élevé de ses noeuds. Une chaîne (liste linéaire) est un arbre de degré 1.
Le chemin d'un noeud est la suite d'arcs qui mènent de la racine à ce noeud. La longueur du chemin d'un noeud est donc égale au niveau de ce noeud.
Un arbre est dit équilibré si, à chaque niveau, la profondeur des différents sous-arbres ne varie pas de plus d'un niveau.
Un arbre ordonné est un arbre où la position respective des sous-arbres reflète une relation d'ordre.
Un arbre de degré 2 est appelé arbre binaire. Un arbre de degré supérieur à 2 est appelé arbre multiple.
Propriétés
car, à la racine, on a 1 noeud,
au niveau 1, on a d noeuds,
au niveau 2, on a d2 noeuds,
au niveau p, on a dp-1 noeuds,
en particulier, pour un arbre binaire, on a : N2(P)=2i=2p-1
Site Hosting: Bronco