CPGE MP / PSI · Informatique

Arbres binaires — Exercices Python (CodeRunner)

Pr. EL HADIQ Zouhair

Cinq exercices auto-évalués. Convention : un arbre vaut None ou [valeur, gauche, droite].

Rappel de la représentation. a[0] = valeur de la racine, a[1] = sous-arbre gauche, a[2] = sous-arbre droit. Exemple :
a = [4, [2, [1,None,None], [3,None,None]], [6, [5,None,None], [7,None,None]]]

Q1 — Nombre de nœuds

Écrire nb_noeuds(a) renvoyant le nombre de nœuds de l'arbre a.

nb_noeuds([4,[2,None,None],[6,None,None]]) → 3

Q2 — Hauteur

Écrire hauteur(a) (arbre vide → −1, feuille seule → 0).

hauteur([4,[2,None,None],[6,None,None]]) → 1

Q3 — Parcours infixe

Écrire infixe(a) renvoyant la liste des valeurs dans l'ordre gauche → racine → droite.

infixe([4,[2,None,None],[6,None,None]]) → [2, 4, 6]

Q4 — Recherche dans un ABR

Écrire recherche(a, x) qui exploite la propriété d'ordre (gauche < nœud < droite) pour ne descendre que d'un côté.

recherche([4,[2,None,None],[6,None,None]], 6) → True

Q5 — Parcours en largeur

Écrire largeur(a) (niveau par niveau, à l'aide d'une file deque).

largeur([4,[2,None,None],[6,None,None]]) → [4, 2, 6]

Importer exercices-arbres-binaires.xml dans la banque de questions Moodle (CodeRunner).