Algorithmes sur les arbres binaires

Ce chapitre présente quelques algorithmes de référence sur les arbres binaires.

Parcours d’arbre binaire

Parcours en largeur

Ce parcours s’effectue profondeur par profondeur (niveau par niveau), de la gauche vers la droite.

Parcours en ordre infixe

Ce parcours en profondeur explore d’abord le sous-arbre gauche, puis le nœud, puis le sous-arbre droit.

Parcours en ordre préfixe

e parcours en profondeur explore d’abord le nœud puis le sous-arbre gauche, puis le sous-arbre droit.

Parcours en ordre suffixe

Ce parcours en profondeur explore d’abord le sous-arbre gauche, puis le sous- arbre droit et enfin le nœud.

Arbre binaire de recherche

Un arbre binaire de recherche (ou ABR) est un arbre binaire tel que :

• les nœuds contiennent des valeurs comparables ;
• Pour tout nœud-père n, on a fg ≤ n < fd , où fg et fd sont respectivement les nœuds racines des sous-arbres gauche et sous-arbres droit (s’ils existent).