Un arbre binaire est un cas particulier de structure arborescente, où chaque nœud ne possède que deux fils au maximum.
On distingue le fils gauche et le fils droit et par extension, le sous-arbre gauche et le sous-arbre droit..
À retenir
La taille est la hauteur d’un arbre binaire sont liées par l’inégalité:
Les parcours en profondeur s’écrivent simplement:
parcours préfixe(arbre)
affiche(valeur)
parcours préfixe(sous-arbre gauche)
parcours préfixe(sous-arbre droit)
parcours infixe(arbre)
parcours infixe(sous-arbre gauche)
affiche(valeur)
parcours infixe(sous-arbre droit)
parcours postfixe(arbre)
parcours postfixe(sous-arbre gauche)
parcours postfixe(sous-arbre droit)
affiche(valeur)
À retenir
Un parcours en profondeur (ou en largeur) visite une et une seule fois chaque nœud. La complexité en temps est linéaire.