Le cas particulier des arbres binaires
Définition d’un arbre binaire
Un arbre binaire est un arbre pour lequel chaque nœud possède au maximum de sous-arbres, un sous-arbre gauche et un sous-arbre droit.
Source
SAG : Sous-arbre gauche
SAD : sous-arbre droit
Source
Source
Source
Mesures d’un arbre binaire
Parmi les mesures les plus courantes, il existe la taille, la hauteur et la profondeur.
La taille est le nombre total de noeuds.
Pour la profondeur et la hauteur il est possible de concevoir deux définitions.
La profondeur est le nombre de niveaux qui séparent deux noeuds.
La hauteur est la plus grande valeur de toutes les profondeurs d’un arbre. C’est le nombre de niveaux qui séparent la racine de l’une des feuilles les plus éloignées de la racine.
Un arbre binaire réduit à un nœud-racine est donc de hauteur 0 (‘zéro’).
Ici la profondeur est définie comme le nombre de noeuds qui séparent deux nœuds de l’arbre binaire, inclus les nœuds de départ et d’arrivée.
Et la hauteur est la plus grande valeur de toutes profondeurs d’un arbre binaire.
C’est le nombre de nœuds qui séparent le nœud-racine de l’un des nœuds-feuilles les plus éloignées du nœud-racine, en comptant le nœud-racine et le nœud-feuille.
Un arbre binaire réduit à un nœud-racine est donc de hauteur 1.
Un arbre binaire est dit complet lorsque tous les noeuds possèdent 0 ou 2 noeuds.
Si h est la hauteur de cet arbre, alors :
>> sa taille est égale à 2 puissance h, moins 1.
>> le nombre de feuilles est égal à 2 puissance (h – 1).
<< Cliquez pour plus d’informations <<