Parcours d'un arbre binaire
Les quatre parcours d'un arbre binaire (préfixe, infixe, suffixe, en largeur), leur ordre de visite, le lien avec les notations préfixée, infixée et postfixée d'une expression, et la reconstruction de l'arbre à partir de deux parcours.
- 29 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Comprendre
Quelques cartes du deck
Arbre binaire : de quoi s'agit-il ?
Voir la réponse
Arbre enraciné dont chaque nœud a au plus deux fils, distingués comme fils gauche et fils droit, qui sont chacun la racine d'un sous-arbre.
Gauche et droite comptent : un nœud dont l'unique fils est à gauche et un nœud dont l'unique fils est à droite donnent deux arbres binaires différents.
Arbre binaire : P a pour fils Q (gauche) et R (droit) ; Q n'a qu'un fils droit, S ; R a pour fils T (gauche) et U (droit). Quel est le parcours suffixe ?
- S Q T U R P
- P Q S R T U
- Q S P T R U
- P Q R S T U
Voir la réponse
S Q T U R P
Suffixe : sous-arbre gauche (S Q), sous-arbre droit (T U R), puis P. P Q S R T U est le préfixe, Q S P T R U l'infixe et P Q R S T U le parcours en largeur du même arbre.
Le parcours … d'un arbre binaire de recherche donne ses valeurs dans l'ordre ….
Voir la réponse
Le parcours infixe d'un arbre binaire de recherche donne ses valeurs dans l'ordre croissant.
Tout le sous-arbre gauche est plus petit que la racine, tout le sous-arbre droit plus grand : gauche, racine, droite est déjà trié.
Parcours préfixe : de quoi s'agit-il ?
Voir la réponse
Parcours en profondeur qui visite la racine, puis le sous-arbre gauche, puis le sous-arbre droit.
La racine passe en premier à chaque niveau : c'est l'ordre pour recopier un arbre ou écrire une expression en notation préfixée.