Arbres binaires


Nous avons déjà rencontré des arbres binaires dans le chapitre précédente: diviser pour régner, plus particulièrement avec le tri fusion: à chaque étape, une liste est découpée en deux sous-listes, créant ainsi une structure hiérarchique binaire.

Cette structure de donnée, si elle peut sembler restrictive de prime abord par rapport à une structure arborescente plus générale, est en réalité dune très grande richesse.

Dans ce premier chapitre consacré aux arbres binaires, nous allons en étudier la structure et les algorithmes fondamentaux qui lui sont attachés.

Dans un second chapitre, nous étudierons un type particulier darbres binaires, les arbres binaires de recherche.