Théorie des graphes

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

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.

L=T+1
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




Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :