« Arbres binaires/Définitions et propriétés » : différence entre les versions

Contenu supprimé Contenu ajouté
m Robot : Remplacement de texte automatisé (-\n(==={0,3})(?: *)([^\n=]+)(?: *)\1(?: *)\n +\n\1 \2 \1\n)
Ligne 8 :
}}
 
== Définition formelle d'un arbre binaire ==
 
Un arbre binaire est un [[w:arbre|arbre]] dont chaque nœud comporte au plus deux fils. C'est une structure de données qui apparaît souvent dans les problèmes algorithmiques classiques.
Ligne 23 :
'''Remarque :''' on appelle aussi '''sous-arbre''' le fils d'un arbre binaire.
 
=== Représentation des arbres binaires ===
[[Fichier:Arbre_binaire_ordonne.svg|Un exemple d'arbre binaire|thumb]]
 
Ligne 33 :
On peut parfois rencontrer la notion de nœud interne et de nœud externe : un nœud externe correspond à une feuille, un nœud interne à ce que l’on nomme nœud. Ici, les nœuds indexés par les entiers 4, 7, 8, 9 sont des feuilles.
 
=== Notion de parenté ===
 
[[Fichier:Arbre_binaire.svg|thumb|100px]]
Ligne 39 :
Par analogie avec un arbre généalogique, il semble intéressant de définir la notion de parenté dans un arbre binaire. On dit ainsi que la racine d'un arbre <math>a_1</math> est le '''père''' d'un arbre <math>a_2</math> si <math>a_2</math> est un fils (droit ou gauche) de <math>a_1</math>. Par abus de langage, on associera un nœud à sa racine, de sorte que dans l'arbre ci-contre, <math>n_1</math> est le père de <math>n_2</math> et <math>n_3</math>.
 
== Indexation des éléments ==
{{...}}
 
== 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.
Ligne 82 :
}}
 
== Squelette d'un arbre binaire ==
{{...}}