« Arbres binaires/Définitions et propriétés » : différence entre les versions
Contenu supprimé Contenu ajouté
Ligne 43 :
== Profondeur dans un arbre ==
Dans un arbre <math>A</math>, on définit rapidement la notion de chemin de la racine (notée <math>a_0</math>) vers une feuille <math>a</math> de <math>A</math> : c'est la donnée d'une suite <math>(a_0, a_1, \dots, a_p=a)</math> de nœuds de l'arbre, tels que pour tout <math>i \in [1, p]</math>, <math>a_i</math> soit le fils de <math>a_{i-1}</math>. La longueur de ce chemin est alors égale à <math>p</math>, le nombre de nœuds du chemin.
{{Définition
| titre = Définition : profondeur
| contenu =
On appelle profondeur d'un nœud ou d'une feuille dans un arbre binaire le nombre d'arêtes qu'il faut parcourir pour atteindre ce nœud à partir de la racine de l'arbre, elle correspond à la longueur du chemin de la racine vers ce nœud.
}}
{{Définition
| titre = Défintion : hauteur
| contenu =
On appelle hauteur d'un arbre <math>A</math> la pronfondeur maximale des nœuds de l'arbre : c'est la plus grande longueur d'un chemin de la racine <math>a_0</math> de <math>A</math> vers une feuille de l'arbre.
}}
Dans le dernier exemple, les nœuds <math>n_2</math> et <math>n_3</math> ont une profondeur de <math>1</math>, la racine <math>n_1</math> une profondeur nulle. La hauteur de l'arbre vaut <math>2</math>.▼
{{Théorème
| contenu =
Une arbre binaire <math>A</math> de hauteur <math>h</math> et possédant <math>n</math> nœuds et feuilles vérifie :
:<math>h \leq n \leq 2^h - 1</math>.
}}
{{Démonstration déroulante}}
▲Dans le dernier exemple, les nœuds <math>n_2</math> et <math>n_3</math> ont une profondeur de 1, la racine <math>n_1</math> une profondeur nulle.
== Squelette d'un arbre binaire ==
| |||