📌 Les tableaux, listes, piles et files sont des structures linéaires, tandis qu’un arbre organise les données de façon hiérarchique.
Une liste aligne les éléments, un arbre les organise en niveaux.
★ À maîtriser
Compléments
Un sous-arbre gauche ou droit est lui-même un arbre, même s’il contient un seul nœud ou est vide.
L’interface du TAD arbre binaire prévoit les opérations suivantes : le constructeur créerArbre, les sélecteurs get_cle, get_gauche et get_droite, les mutateurs insert_gauche et insert_droite, le prédicat estVide
★ À maîtriser
La hauteur se calcule récursivement : un arbre vide a une hauteur de 0 et un arbre non vide a une hauteur égale à 1 plus le maximum des hauteurs de ses deux sous-arbres.
La taille, c’est-à-dire le nombre de nœuds, se calcule récursivement : un arbre vide a une taille de 0 et un arbre non vide a une taille égale à 1 plus les tailles de ses deux sous-arbres.
Compléments
★ À maîtriser
📌 Le parcours infixe visite les nœuds dans l’ordre gauche, racine, droite (GRD), le parcours préfixe dans l’ordre racine, gauche, droite (RGD), et le parcours suffixe ou postfixe dans l’ordre gauche, droite, racine (GDR).
Compléments
GRD : gauche, racine, droite.
★ À maîtriser
Compléments
Une file d’attente où chaque niveau attend son tour avant le suivant.
★ À maîtriser
Compléments
Les éléments d’un arbre binaire de recherche doivent posséder une relation d’ordre totale permettant de comparer deux éléments.
Le premier élément inséré dans un arbre binaire de recherche devient sa racine ; les éléments plus petits sont placés à gauche et les éléments plus grands à droite.
À gauche, les valeurs sont inférieures ou égales ; à droite, elles sont strictement supérieures.
★ À maîtriser
Compléments
📌 La recherche dans un arbre binaire de recherche suit les liens de l’arbre en comparant les clés, tandis que la recherche dichotomique accède directement aux éléments d’un tableau.
Ordres des parcours en profondeur
| Parcours | Ordre |
|---|---|
| Infixe | Gauche, racine, droite (GRD) |
| Préfixe | Racine, gauche, droite (RGD) |
| Suffixe ou postfixe | Gauche, droite, racine (GDR) |
Teste tes connaissances sur Arbres binaires en algorithmique avec 18 questions à choix multiples et corrections détaillées.
1. Un système de fichiers doit représenter les dossiers et sous-dossiers à plusieurs niveaux de profondeur. Quelle propriété distingue le mieux une structure adaptée à cette organisation d’une liste simple ?
2. Dans un modèle de données, des éléments sont reliés de sorte que certains peuvent en contenir ou en désigner d’autres comme enfants. Quelle structure correspond à cette description ?
Mémorisez les concepts clés de Arbres binaires en algorithmique avec 55 flashcards interactives.
Quelle organisation des données caractérise les tableaux, listes, piles et files ?
Une organisation linéaire.
Quelle organisation des données caractérise un arbre ?
Une organisation hiérarchique.
De quels éléments un arbre est-il composé ?
De nœuds pouvant avoir des enfants qui sont eux-mêmes des nœuds.
Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.
Générateur de fiches