Aller au contenu

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 largeur

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 infixe

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 préfixe

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.

Parcours infixe

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 fgn < fd , où fg et fd sont respectivement les nœuds racines des sous-arbres gauche et sous-arbres droit (s’ils existent).

ABR