Propriétés d’un arbre binaire
Le nombre maximum de nœuds au niveau «l» d’un arbre binaire est 2l-1.
Ici le niveau est le nombre de nœuds sur le chemin de la racine au nœud (y compris la racine et le nœud). Le niveau de la racine est 1.
Le nombre maximum de nœuds dans une arborescence binaire de hauteur «h» est 2h - 1.
Ici la hauteur d'un arbre est le nombre maximum de nœuds sur le chemin racine à feuille. La hauteur d'un arbre avec un seul noeud est considérée comme 1.
Un arbre a un maximum de nœuds si tous les niveaux ont un maximum de nœuds. Le nombre maximal de nœuds dans un arbre binaire de hauteur h est donc 1 + 2 + 4 + .. + 2h-1. Ceci est une suite géométrique simple avec h termes et la somme de cette série est 2h - 1.
Si la hauteur de la racine est considérée comme étant égale à 0. Dans cette convention, la formule ci-dessus devient 2h + 1 - 1
la hauteur minimale possible ou le nombre minimum de niveaux.
Dans un arbre binaire à N nœuds, la hauteur minimale possible ou le nombre minimum de niveaux est ceil(Log2 (N + 1))
Si nous considérons la convention où la hauteur d'une feuille est considérée comme égale à 0, alors la formule ci-dessus pour la hauteur minimale devient ceil(Log2 (N + 1)) - 1
Nombre de niveaux dans un arbre binaire avec L feuilles.
Un arbre binaire avec L feuilles a au moins ceil(Log2(L)) + 1 niveaux
Un arbre binaire a un nombre maximum de feuilles (et un nombre minimum de niveaux) lorsque tous les niveaux sont complètement remplis.
Nombre de feuilles dans un arbre binaire.
Dans un arbre binaire où chaque nœud a 0 ou 2 enfants, le nombre de feuilles est toujours égal à un de plus que les nœuds avec deux enfants.
avec L = Nombre de feuilles
T= Nombre de nœuds internes avec deux enfants
ceil(x) : renvoie le plus petit entier supérieur ou égal à x
