Terminale · Numérique et sciences informatiques

Arbres et arbres binaires

Reconnaître un arbre comme structure hiérarchique, distinguer un arbre binaire, et décrire ses éléments et son parcours.

Aperçu gratuit
Illustration de la fiche « Arbres et arbres binaires »

Les points essentiels

  • Un arbre est une structure hiérarchique formée de nœuds reliés par des arêtes.
  • Dans un arbre, chaque nœud sauf la racine possède un unique parent ; la racine n'en a aucun.

Les mots à connaître

Arbre
Structure de données hiérarchique composée de nœuds reliés par des arêtes, où chaque nœud sauf la racine a exactement un parent.
Racine
Nœud unique de l'arbre qui n'a pas de parent.

Un exemple pour comprendre

Soit un arbre binaire dont la racine A a pour enfant gauche B et pour enfant droit C. B est une feuille, C est une feuille. Donne le parcours infixe.

On part de A. Étape 1 : parcourir le sous-arbre gauche, ici le nœud B, qui est une feuille. Étape 2 : traiter la racine A. Étape 3 : parcourir le sous-arbre droit, ici le nœud C. Le parcours infixe est donc B, A, C.

Première page de l’Essentiel : Arbres et arbres binaires
Ketty