En théorie des graphes, qu’est-ce qu’un arbre ?
Un graphe connexe et acyclique.
Qu’est-ce qu’un arbre enraciné ?
Un arbre muni d’un nœud particulier appelé racine.
À quoi sert un arbre enraciné en informatique ?
À modéliser une représentation hiérarchique de l’information ou une structure de données.
Comment se définit la taille d’un arbre ?
C’est son nombre de nœuds.
Comment se définit le degré d’un nœud dans ce cours ?
C’est le nombre de fils qu’il possède.
Quel degré caractérise une feuille ?
Un degré de 0.
Quelle borne limite le degré de chaque nœud d’un arbre binaire ?
Au plus 2.
Comment se définit la profondeur d’un nœud dans un arbre ?
C’est la distance du chemin reliant la racine à ce nœud.
Comment définit-on la hauteur d’un arbre ?
La profondeur maximale de ses nœuds.
Combien de nœuds de degré 1 possède un arbre binaire localement complet ?
Aucun.
Combien de feuilles possède un arbre binaire localement complet de taille ?
feuilles.
Quelle est la propriété des degrés des nœuds d’un arbre filiforme ?
Tous ses nœuds ont un degré d’au plus 1.
Quelles propriétés définissent un arbre binaire complet dans ce cours ?
Ses feuilles sont à la même profondeur et chaque niveau est entièrement rempli.
Comment les nœuds du dernier niveau d’un arbre binaire parfait sont-ils disposés ?
Ils sont alignés à gauche.
Quelles formes peut prendre un arbre binaire étiqueté ?
Il est vide, noté (), ∅ ou Λ, ou de la forme (r, T1, T2), où r est de type Element.
Que désignent T1 et T2 dans (r, T1, T2) ?
T1 et T2 sont respectivement les sous-arbres gauche et droit.
Quels éléments chaque nœud contient-il dans l’implémentation chaînée présentée ?
Une valeur et deux pointeurs, sag et sad.
Comment l’implémentation chaînée représente-t-elle un arbre vide ?
Par un pointeur Null.
Que teste la fonction `estVide` sur un arbre ?
Elle teste si l’arbre vaut `nullptr`.
Que renvoie `creerArbre()` sans argument ?
`nullptr`.
Que crée `creerArbre(e, G, D)` ?
Un nœud contenant `e` et les pointeurs `G` et `D`.
Que détruit récursivement la fonction `detruire` ?
Les sous-arbres gauche et droit d’un nœud non nul.
Que fait `detruire` au nœud après avoir détruit ses sous-arbres ?
Elle le libère avec `delete`.
Comment le parcours en largeur ordonne-t-il les nœuds selon leur niveau ?
Par niveaux croissants.
Quelle structure de données permet d’implémenter itérativement le parcours en largeur ?
Une file.
Dans un parcours en profondeur, quel sous-arbre est exploré entièrement en premier ?
Le sous-arbre gauche.
Quelles méthodes permettent d’implémenter un parcours en profondeur ?
La récursion ou une pile utilisée itérativement.
En parcours préfixe, quand la racine est-elle traitée ?
Avant le sous-arbre gauche.
En parcours infixe, quand la racine est-elle traitée ?
Après le sous-arbre gauche et avant le sous-arbre droit.
En parcours postfixe, quand la racine est-elle traitée ?
Après le sous-arbre droit.
Quel système informatique est représentable par un arbre ?
Le système de fichiers sous UNIX.
Quelle compétition sportive peut être représentée par un arbre ?
Les rencontres d’un tournoi sportif.
Quelles relations hiérarchiques peut-on décrire dans un arbre ?
Les relations prédécesseur-successeur, ancêtre-descendant et parent-enfant.
Dans quel sens peut-on orienter les arêtes d’un arbre enraciné ?
Du haut vers le bas, en partant de la racine.
Que contient le niveau d’un arbre ?
Les nœuds de profondeur .
Quelles bornes encadrent la hauteur d’un arbre binaire de taille ?
.
Combien de feuilles possède toujours un arbre filiforme ?
Une seule feuille.
Quelle propriété caractérise les fils droits d’un peigne gauche ?
Tout fils droit est une feuille.
Combien de nœuds comporte le niveau d’un arbre complet de profondeur ?
nœuds pour chaque .
Pourquoi (r, T′, Λ) et (r, Λ, T′) sont-ils distincts ?
La position gauche ou droite du fils est conservée.
De quoi dépendent les opérations d’ajout, de suppression et d’accès dans un arbre binaire ?
Du type d’arbre binaire utilisé.
Quelle structure peut représenter un arbre parfait, comme un tas binaire ?
Un tableau.
Comment la fonction `affichage_parenthese` encadre-t-elle l’arbre ?
Elle l’encadre de parenthèses.
Dans quel ordre `affichage_parenthese` affiche-t-elle les éléments d’un nœud ?
La valeur du nœud, son sous-arbre gauche, puis son sous-arbre droit.
Quels sont les trois moments de visite d’un nœud en parcours en profondeur ?
En descendant, puis en remontant après chacun de ses sous-arbres.
Quel ordre suit la variante main droite du parcours en profondeur ?
Elle explore d’abord les sous-arbres droits.
Teste tes connaissances avec un QCM de 22 questions sur Arbres binaires et parcours.
1. Quelle condition définit un arbre binaire localement complet, ou strict ?
2. Qu’est-ce qui distingue un arbre enraciné d’un arbre sans racine désignée ?
Révisez le cours complet dans la fiche de révision de Arbres binaires et parcours.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards