Le tournoi de foot
Un tournoi à élimination directe : quatre équipes, deux demi-finales, une finale. Chaque match oppose deux équipes. Le gagnant monte d’un cran.
Dessine ce tournoi : tu obtiens un arbre où chaque match a exactement deux fils.
On appelle cela un arbre binaire.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Arbre binaire | Un arbre où chaque nœud a au plus deux enfants. | Le tournoi de foot |
| Fils gauche | L’enfant placé à gauche d’un nœud. | arbre["M"][0] |
| Fils droit | L’enfant placé à droite d’un nœud. | arbre["M"][1] |
| None | Le mot de Python qui veut dire : rien. Ici, pas de fils. | ["A", None] |
| Parcours | Visiter tous les nœuds, dans un ordre précis. | Niveau par niveau |
| Parcours en largeur | Visiter niveau par niveau, de gauche à droite. On utilise une file. | M, T, C, A, S, E, R |
| Parcours préfixe | Visiter un nœud, puis son côté gauche, puis son côté droit. | M, T, A, R, C, S, E |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À toi : lis le tournoi
À toi de jouer
À toi : lis le tournoi
3 questionsTes réponses sont corrigées ici et ne sont pas conservées. Un compte garde tes résultats.
Gauche et droite
Dans un arbre binaire, un nœud a au plus deux fils : un gauche et un droit. Il peut en avoir un seul, ou aucun.
La place compte : un fils tout seul peut être à gauche ou à droite. Ce ne sont pas deux arbres identiques.
Un arbre binaire en Python
On note l’arbre dans un dictionnaire. Chaque nom donne une liste de deux cases : le fils gauche, puis le fils droit.
S’il manque un fils, on écrit None. Une feuille a donc [None, None].
À toi : lire un arbre binaire
# Chaque nœud : [fils gauche, fils droit]. None veut dire : pas de fils.
arbre = {
"M": ["T", "C"],
"T": ["A", None],
"C": ["S", "E"],
"A": [None, "R"],
"S": [None, None],
"E": [None, None],
"R": [None, None],
}
print("Fils gauche de M :", arbre["M"][0])
print("Fils droit de M :", arbre["M"][1])
print("Fils droit de T :", arbre["T"][1])
for nom in arbre:
if arbre[nom][0] is None and arbre[nom][1] is None:
print(nom, "est une feuille")
# Quels sont les fils de C ? Et ceux de A ?
Exemple travaillé : le dictionnaire en tableau
| Nœud | Fils gauche | Fils droit | Rôle |
|---|---|---|---|
| M | T | C | racine |
| T | A | rien | nœud avec un seul fils |
| C | S | E | nœud avec deux fils |
| A | rien | R | nœud avec un seul fils |
| S, E, R | rien | rien | feuilles |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.