8. Structures récursives non-linéaires :les arbres

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 :

• soit la structure vide

• soit un noeud de type T (racine) auquel est associé un nombre fini de sous-arbres disjoints (descendants). Une structure d'arbre est souvent illustrée sous la forme suivante :

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

• Le nombre maximum de noeuds qu'un arbre de profondeur "p" et de degré "d" peut contenir, si tous les noeuds internes ont "d" descendants, est :
  N_d(p)=dⁱ

  car, à la racine, on a 1 noeud,
  au niveau 1, on a d noeuds,
  au niveau 2, on a d² noeuds,
  au niveau p, on a d^p-1 noeuds,

  en particulier, pour un arbre binaire, on a : N₂(P)=2ⁱ=2^p-1

• La profondeur d'un arbre binaire équilibré, ayant N noeuds, est toujours comprise entre
  log₂(N+1) et *log₂(N+2) -(-2)

8.1. Les arbres binaires ordonnés

Table des matières.

Site Hosting: Bronco