Aucun de ses nœuds n’a exactement un fils.
Explication
Un arbre binaire localement complet ne possède aucun nœud de degré 1. Avoir toutes les feuilles à la même profondeur est une propriété d’une autre forme particulière d’arbre binaire.
Il comporte un nœud particulier désigné comme racine.
Explication
Un arbre enraciné est muni d’un nœud particulier appelé racine. Le fait d’avoir exactement deux fils n’est pas requis pour distinguer un arbre enraciné.
3, car la profondeur est la distance du chemin depuis la racine.
Explication
La profondeur est la distance du chemin reliant la racine au nœud, donc trois arêtes donnent une profondeur de 3. La racine est à la profondeur 0, et non à la première étape du décompte.
Le sous-arbre gauche est parcouru entièrement avant le sous-arbre droit
Explication
Le parcours en profondeur conventionnel achève l’exploration du sous-arbre gauche avant de passer au sous-arbre droit. Traiter les nœuds par niveaux décrit le parcours en largeur, et non cette règle d’ordre.
Un triplet (r, T1, T2), où r est une valeur de type Element et T1 et T2 sont les sous-arbres gauche et droit.
Explication
La définition associe à la racine r deux sous-arbres ordonnés, l’un gauche et l’autre droit ; l’arbre vide possède, lui, plusieurs notations possibles. Un couple avec un seul sous-arbre ne décrit pas la structure binaire indiquée.
5, d’après la formule $$\frac{n+1}{2}$$.
Explication
Pour un arbre binaire localement complet de taille , le nombre de feuilles est . La formule donne le nombre de nœuds internes, et non celui des feuilles.
Par niveaux croissants, puis de gauche à droite dans chaque niveau
Explication
Le parcours en largeur traite les nœuds niveau par niveau, de gauche à droite au sein de chaque niveau. Achever un sous-arbre avant de passer au suivant caractérise plutôt le parcours en profondeur.
Une valeur et deux pointeurs, sag et sad, vers les sous-arbres gauche et droit.
Explication
Chaque nœud contient sa valeur ainsi que les pointeurs sag et sad, associés respectivement aux sous-arbres gauche et droit. Des indices de tableau correspondent à une autre manière de représenter certaines structures, et non à ces champs de l’implémentation chaînée.
Par un pointeur Null, qui indique l’absence de nœud.
Explication
Dans cette représentation chaînée, le pointeur Null signale qu’il n’y a pas d’arbre. Un nœud contenant une valeur nulle reste une structure de nœud, ce qui ne correspond pas à cette représentation de l’arbre vide.
Un pointeur vers un nœud alloué contenant e et les pointeurs G et D.
Explication
Cette forme de creerArbre alloue un nœud qui contient e et conserve G et D comme pointeurs vers ses sous-arbres. L’appel sans argument, lui, renvoie nullptr, mais ce comportement ne s’applique pas à l’appel avec trois arguments.
Chaque nœud possède au plus un fils.
Explication
Dans un arbre filiforme, chaque nœud a un degré d’au plus 1, ce qui autorise les nœuds ayant un seul fils. L’absence de nœuds de degré 1 caractérise plutôt un arbre localement complet.
Non, car la représentation distingue la position gauche de la position droite du sous-arbre.
Explication
Dans un arbre binaire étiqueté, la position du fils est conservée : T′ à gauche ne donne pas le même arbre que T′ à droite. L’identité de la racine et du sous-arbre présent ne suffit donc pas à rendre ces deux représentations équivalentes.
Le nombre de fils que possède le nœud.
Explication
Le degré d’un nœud correspond au nombre de fils qu’il possède. Le nombre de liens qui le séparent de la racine relève plutôt de sa profondeur.
Comme un nœud interne, puisque son degré est au moins 1.
Explication
Un nœud ayant trois fils a un degré de 3 et est donc un nœud interne, dont le degré est au moins 1. Une feuille, au contraire, est un nœud de degré 0.
La récursion ou, de façon itérative, une pile
Explication
Le parcours en profondeur s’implémente naturellement par récursion ou itérativement avec une pile. Une file est associée au parcours en largeur, car elle soutient le traitement des nœuds par niveaux.
C’est un graphe connexe et acyclique.
Explication
Un arbre en théorie des graphes est à la fois connexe et dépourvu de cycle. Un graphe acyclique qui n’est pas connexe ne satisfait pas la condition de connexité.
Après le sous-arbre gauche et avant le sous-arbre droit
Explication
En infixe, on traite d’abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Traiter la racine avant les deux sous-arbres correspond à l’ordre préfixe.
Pour représenter une information hiérarchique ou organiser des données.
Explication
En informatique, un arbre enraciné sert de modèle hiérarchique pour représenter l’information ou structurer des données. Une séquence sans relation hiérarchique ne correspond pas à cet usage caractéristique.
8, car la taille compte le nombre de nœuds.
Explication
La taille d’un arbre est égale à son nombre de nœuds, donc cet arbre a une taille de 8. La racine fait partie des nœuds et n’est pas retranchée du compte.
Un arbre dont toutes les feuilles sont à la même profondeur et dont chaque niveau est entièrement rempli.
Explication
Un arbre binaire complet a toutes ses feuilles à la même profondeur et chaque niveau est entièrement rempli. Le remplissage des niveaux jusqu’à l’avant-dernier avec un dernier niveau aligné à gauche décrit l’arbre parfait dans le vocabulaire donné.
Une file, qui organise le traitement des nœuds par niveaux
Explication
Une file permet de traiter successivement les nœuds découverts dans l’ordre nécessaire au parcours en largeur. Une pile est plutôt la structure utilisée pour un parcours en profondeur itératif.
Elle détruit récursivement les sous-arbres gauche et droit, puis libère le nœud avec delete.
Explication
La fonction applique la destruction récursive aux sous-arbres gauche et droit avant de libérer le nœud courant avec delete. Libérer le nœud avant de traiter ses descendants ne respecte pas l’ordre de destruction décrit.
Mémorisez les réponses avec 46 flashcards sur Arbres binaires et parcours.
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.
Consultez la fiche de révision complète sur Arbres binaires et parcours.
Voir la fiche →Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.
Générateur de QCM