Parcours Arbre

Question 1

Quel est l’ordre du parcours préfixe ?

Answer 1

Racine → Enfant gauche → Enfant droit

moyen mnémotechnique:

Je prends soin de moi, ensuite mes enfants

Question 2

À quoi sert le parcours suffixe ?

Answer 2

Le parcours suffixe (postordre) est utilisé quand le traitement d’un nœud dépend du traitement de ses enfants, par exemple :
• Évaluation d’expressions arithmétiques (arbres binaires d’expressions)
• Suppression d’un arbre (on supprime les enfants avant le parent)
• Calculs de programmation dynamique sur les arbres (comme dans le calcul des tailles de sous-arbres, les diamètres, ou des coûts optimaux)

Moyen mnémotechnique:
Je commence par mes enfants ensuite par moi

Question 3

Qu’est-ce que le parcours symétrique ?

Answer 3

Enfant gauche → Racine → Enfant droit (binaire uniquement)

Question 4

Quel parcours utilise une file ?

Answer 4

Parcours par niveau (largeur)

Question 5

À quoi sert le parcours par niveau ?

Answer 5

Découverte du plus court chemin (labyrinthe, BFS)

Question 6

Ordre du parcours préfixe ?

Answer 6

Racine → Gauche → Droite

Question 7

Ordre du parcours suffixe ?

Answer 7

Gauche → Droite → Racine

Question 8

Ordre du parcours symétrique ?

Answer 8

Gauche → Racine → Droite

Question 9

Parcours utilisé dans un algorithme de retour arrière ?

Answer 9

En backtracking classique (DFS + pré-order) :

Tu fais un choix (tu “visites” le nœud),

tu explores toutes les options qui découlent de ce choix (tu creuses le chemin plus profondément),

puis tu annules ce choix (tu « backtrackes ») pour revenir en arrière et essayer la suivante.

Question 10

Quelle structure utilise le parcours par niveau ?

Answer 10

Une file

Question 11

Quel parcours est adapté à l’évaluation d’expressions binaires ?

Answer 11

Symétrique

Question 12

Vrai ou Faux : Le parcours symétrique fonctionne sur tout type d’arbre

Answer 12

Faux (arbres binaires seulement)

Question 13

Vrai ou Faux : Le parcours préfixe est équivalent à DFS

Answer 13

Vrai pour les arbres

Question 14

Vrai ou Faux : Le parcours par niveau explore l’arbre en profondeur

Answer 14

Faux

Question 15

À quoi sert le parcours suffixe dans le minimax ?

Answer 15

Évaluer les coups des feuilles vers la racine

Question 16

Quel parcours donne un ordre topologique d’un arbre ?

Answer 16

Préfixe ou suffixe (pas unique)

Question 17

Vrai ou Faux : Le parcours préfixe traite la racine en dernier

Answer 17

Faux

Question 18

Pseudo-code : traitement dans parcours préfixe

Answer 18

Traitement(x) avant appel récursif aux enfants

Question 19

Dans un arbre, combien d’arêtes y a-t-il par rapport aux nœuds ?

Answer 19

n-1

Question 20

Peut-on utiliser BFS pour les arbres ?

Answer 20

Oui, c’est le parcours par niveau

Question 21

À quoi sert un parcours par niveau dans les arbres binaires de recherche ?

Answer 21

Identifier la hauteur ou les niveaux

Question 22

Quel parcours d’arbre est utile pour du tri ?

Answer 22

In-ordre (symétrique) dans un arbre binaire de recherche

Question 23

Vrai ou Faux : Le parcours par niveau est équivalent à BFS

Answer 23

Vrai

Question 24

Comment représenter un arbre pour le parcours par niveau ?

Answer 24

Utiliser une file FIFO

Question 25

Quels parcours utilisent une récursion directe ?

Answer 25

Préfixe, suffixe, symétrique

Question 26

Que veut dire parcours préfixe ?

Answer 26

On traite la racine avant de visiter ses enfants (traitement → récursion à gauche → récursion à droite).

Question 27

Explique l’utilité du parcours suffixe dans un algorithme de minimax.

Answer 27

On traite les enfants avant le parent, donc on peut remonter les valeurs vers le haut de l’arbre.

Question 28

Pourquoi le parcours symétrique est-il utile dans les arbres binaires de recherche ?

Answer 28

Car il donne les valeurs triées (in-order traversal).

Question 29

Explique ce qu’est le parcours par niveau et son utilité.

Answer 29

On visite tous les nœuds à un niveau avant de passer au suivant. Il est utile pour trouver la hauteur ou explorer un arbre comme un graphe.

Question 30

Que veut dire parcours en profondeur dans un arbre ?

Answer 30

C’est un parcours qui suit un chemin jusqu’au bout avant de revenir en arrière. Exemple : préfixe, suffixe.

Question 31

Que veut dire BFS ?

Answer 31

BFS signifie Breadth-First Search, soit en français parcours en largeur. C’est un algorithme de parcours de graphe (ou d’arbre) qui explore les sommets niveau par niveau, en partant d’un sommet source.

Question 32

Comment fonctionne BFS ?

Answer 32

1. On démarre d’un sommet source s : * On le marque comme découvert. * On l’ajoute à une file (queue). 2. Tant que la file n’est pas vide : * On retire un sommet u de la file. * On traite u (ex. : l'afficher, l'ajouter à un résultat). * Pour chaque voisin v de u non découvert : - On le marque comme découvert. - On l'ajoute à la file pour exploration plus tard.

Question 33

Complète le pseudo-code du parcours préfixe : Préfixe(x): Traitement(x) pour y dans enfants(x): ______

Answer 33

Préfixe(y)

Question 34

Quel parcours donnerait : Gauche → Racine → Droite ?

Answer 34

Symétrique (In-order)

Question 35

Pourquoi le parcours suffixe est préférable dans un arbre d’évaluation ?

Answer 35

Parce qu'on veut les résultats des enfants avant de traiter le parent

Question 36

Quand le parcours par niveau ne fonctionne-t-il pas efficacement ?

Answer 36

Sur des arbres très déséquilibrés (file → complexité mémoire élevée)

Question 37

Complexité du parcours préfixe ?

Answer 37

Θ(n), où n est le nombre de nœuds

Question 38

Structure utilisée pour le parcours par niveau ?

Answer 38

File (queue)