Structures de données: Arbres
39 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Quelle propriété n'est pas vraie pour un arbre ?

  • Il existe un nœud particulier nommé racine.
  • Un arbre est sans cycle.
  • Tout nœud a plusieurs pères. (correct)
  • Un arbre est connexe.

    • Quel élément est considéré comme la racine d'un arbre ?

  • Le nœud qui est le dernier ajouté.
  • Le nœud qui a plusieurs pères.
  • Le nœud avec le plus de fils.
  • Le nœud unique qui n'a pas de père. (correct)

    • Comment appelle-t-on les nœuds trouvés sur le chemin entre un nœud donné et la racine ?

  • Descendants.
  • Frères.
  • Fils.
  • Ancêtres. (correct)

    • Combien d'arêtes un arbre avec n sommets doit-il avoir pour être acyclique ?

    <p>n - 1.</p> Signup and view all the answers

    Que se passe-t-il lorsqu'on ajoute une arête à un arbre ?

    <p>L'arbre devient cyclique.</p> Signup and view all the answers

    Quel est le résultat de la suppression de toute arête dans un arbre ?

    <p>L'arbre devient non connexe.</p> Signup and view all the answers

    Dans un arbre, un nœud est un descendant si :

    <p>Son ancêtre est un nœud parent.</p> Signup and view all the answers

    Quand dit-on qu'un nœud a plusieurs fils ?

    <p>Quand il n'est pas une feuille.</p> Signup and view all the answers

    Quel est l'ordre d'évaluation des nœuds lors d'un parcours en largeur d'abord ?

    <p>+, ×, ×, −, 2, a, 2, +, a, ×, a, b, 3, b</p> Signup and view all the answers

    Quel type de structure de données est utilisé pour mettre en œuvre le parcours en largeur ?

    <p>Une file</p> Signup and view all the answers

    Dans l'algorithme de parcours en largeur d'un arbre binaire, que se passe-t-il pour chaque nœud traité ?

    <p>Ses enfants sont ajoutés à un niveau inférieur.</p> Signup and view all the answers

    Quel est le principal avantage d'un parcours en profondeur par rapport à un parcours en largeur ?

    <p>Il consomme moins de mémoire.</p> Signup and view all the answers

    Dans un parcours en profondeur, l'ordre d'évaluation des nœuds dépend de quoi ?

    <p>De la structure de l'arbre.</p> Signup and view all the answers

    Qu'est-ce qui définit une feuille dans un arbre ?

    <p>Un nœud sans enfants</p> Signup and view all the answers

    Comment est calculée la hauteur moyenne d'un arbre T ?

    <p>HM(T) = somme des hauteurs de tous les nœuds / taille(T)</p> Signup and view all the answers

    Quelle est la définition d'un nœud intérieur dans un arbre ?

    <p>Un nœud qui a au moins 1 enfant</p> Signup and view all the answers

    Quel est le rôle de la racine dans un arbre ?

    <p>C'est l'ancêtre de tous les nœuds</p> Signup and view all the answers

    Quel est le calcul de la hauteur d'un arbre noté h(T) ?

    <p>h(T) = max(h(n)) pour tout nœud de l’arbre</p> Signup and view all the answers

    Qu'est-ce qu'un arbre binaire ?

    <p>Un arbre où chaque nœud a 0, 1 ou 2 enfants</p> Signup and view all the answers

    Quelle est la définition du bord gauche d'un arbre ?

    <p>Le chemin depuis la racine en suivant des fils gauches</p> Signup and view all the answers

    Comment est noté le nombre de feuilles dans un arbre ?

    <p>nf(T)</p> Signup and view all the answers

    Quelle est la hauteur maximale d'un arbre binaire de taille n selon le lemme donné ?

    <p>$n - 1$</p> Signup and view all the answers

    Quelle est la relation correcte entre la taille d'un arbre binaire et le nombre de feuilles ?

    <p>Tout arbre ayant f feuilles a une hauteur h(T) supérieure ou égale à $ ext{ceil}( ext{log}_2 f)$.</p> Signup and view all the answers

    Quel type d'arbre binaire doit avoir tous ses niveaux remplis sauf le dernier et les feuilles orientées à gauche ?

    <p>Arbre binaire parfait</p> Signup and view all the answers

    Combien de feuilles un arbre binaire localement complet avec n nœuds internes possède-t-il ?

    <p>$n + 1$</p> Signup and view all the answers

    Quelle est la hauteur d'un arbre binaire filiforme ?

    <p>n - 1</p> Signup and view all the answers

    Quel est le nombre total de nœuds d'un arbre binaire de hauteur h ?

    <p>$2^{h+1} - 1$</p> Signup and view all the answers

    Qu'est-ce qu'un arbre binaire complet ?

    <p>Un arbre où chaque niveau est complètement rempli.</p> Signup and view all the answers

    Quel est l'énoncé correct concernant les différences entre les types d'arbres binaires ?

    <p>Un arbre binaire parfait est un cas particulier d'arbre localement complet.</p> Signup and view all the answers

    Quel est l'ordre de traitement des nœuds lors d'un parcours préfixe d'un arbre binaire ?

    <p>Racine - Gauche - Droite</p> Signup and view all the answers

    Lors d'un parcours infixe, à quel moment le nœud est-il traité ?

    <p>Après avoir parcouru l'arbre gauche et avant l'arbre droit</p> Signup and view all the answers

    Quel algorithme correspond au parcours postfixe d'un arbre binaire ?

    <p>ParcoursEnProfondeur(r.Gauche); ParcoursEnProfondeur(r.Droit); traitement_postfixe(r);</p> Signup and view all the answers

    Lors d'un parcours en profondeur, que se passe-t-il si le nœud est vide ?

    <p>On traite l'arbre vide et termine le parcours</p> Signup and view all the answers

    Dans un parcours postfixe, quel est le dernier nœud à être traité ?

    <p>Le nœud racine</p> Signup and view all the answers

    Quel parcours traite le nœud à la deuxième occurrence ?

    <p>Infixe</p> Signup and view all the answers

    Quel est le premier nœud à être traité lors d'un parcours préfixe ?

    <p>Le nœud racine</p> Signup and view all the answers

    Quel parcours traite en dernier les nœuds d'un arbre selon l'algorithme ?

    <p>Postfixe</p> Signup and view all the answers

    Quel est l'ordre de traitement lors d'un parcours infixe ?

    <p>Gauche - Racine - Droite</p> Signup and view all the answers

    Dans quel parcours un nœud est-il traité à la première occurrence ?

    <p>Préfixe</p> Signup and view all the answers

    Study Notes

    Arbres

    • Les arbres sont des structures de données importantes et utilisées en informatique.
    • Ils sont utilisés dans les arbres généalogiques, les arbres de classification et les arbres d'expression.
    • Un arbre est un ensemble de nœuds reliés entre eux par des arêtes.
    • Trois propriétés caractérisent les arbres enracinés :
      • Un nœud particulier est désigné comme racine.
      • Chaque nœud (autre que la racine) est relié à un nœud parent par une arête.
      • Un arbre est connexe (il existe un chemin entre chaque paire de nœuds).
      • Un arbre est sans cycle.
    • Un nœud peut avoir 0 ou plusieurs fils.
    • Chaque nœud a exactement un père (sauf la racine).

    Définition récursive des arbres

    • Un nœud unique est un arbre, où le nœud est la racine.
    • Si r est un nouveau nœud, et T1, T2,…, Tk sont des arbres ayant pour racines r1, r2,…, rk respectivement, alors l'arbre avec r comme racine et r1, r2,…, rk comme fils est un arbre. Une arête est ajoutée entre r et chaque ri.

    Propriétés d'un arbre

    • Pour un arbre T à n sommets, il y a équivalence entre les propriétés suivantes :
      • T est un arbre
      • T est connexe, et la suppression d'une arête quelconque le rend non connexe.
      • T est acyclique à n - 1 arêtes.
      • T est acyclique, et l'ajout d'une arête quelconque le rend cyclique.

    Chemins, ancêtres, descendants

    • Les ancêtres d'un nœud sont les nœuds sur le chemin unique entre ce nœud et la racine.
    • Le nœud d est un descendant de a si et seulement si a est un ancêtre de d.
    • La longueur d'un chemin est le nombre d'arêtes qu'il contient.

    Généalogie

    • La racine est un ancêtre de tous les nœuds.
    • Chaque nœud est un descendant de la racine.
    • Les nœuds ayant le même parent sont appelés enfants.
    • Un nœud n et tous ses descendants forment un sous-arbre.

    Feuilles et nœuds intérieurs

    • Une feuille est un nœud sans enfants.
    • Un nœud intérieur est un nœud avec au moins un enfant.
    • Chaque nœud de l'arbre est soit une feuille, soit un nœud intérieur.

    Mesures sur les arbres

    • La taille d'un arbre T (notée taille(T)) est le nombre de nœuds.
    • Le nombre de feuilles est noté nf(T).
    • La hauteur d'un nœud n (notée h(n)) est la longueur du chemin depuis la racine jusqu'à n.
    • La hauteur d'un arbre T (notée h(T)) est la plus grande hauteur parmi les nœuds de l'arbre.
    • La hauteur moyenne d'un arbre T (notée HM(T)) est la moyenne des hauteurs de tous ses nœuds.
    • La hauteur moyenne externe d'un arbre T (notée HME(T)) est la moyenne des longueurs de tous les chemins depuis la racine qui se terminent par une feuille.

    Arbres binaires

    • Tous les nœuds d'un arbre binaire ont 0, 1 ou 2 enfants.

    • L'enfant gauche d'un nœud n est la racine du sous-arbre gauche de n.

    • L'enfant droit d'un nœud n est la racine du sous-arbre droit de n.

    • Le bord gauche d'un arbre est le chemin qui part de la racine et ne traverse que des fils gauche.

    • Le bord droit d'un arbre est le chemin qui part de la racine et ne traverse que des fils droit.

    Exemples d'arbres binaires particuliers

    • Arbre binaire filiforme :
      • Un seul nœud à la hauteur 0.
      • Deux nœuds à la hauteur 1.
      • Quatre nœuds à la hauteur 2.
      • ...
      • 2h nœuds à la hauteur h.
      • Nombre total de nœuds dans un arbre de hauteur h : 2h+1-1.
    • Arbre binaire parfait :
      • Tous les niveaux sont remplis sauf le dernier.
      • Les feuilles sont les plus à gauche possible.
    • Arbre binaire localement complet :
      • Chaque nœud a 0 ou 2 enfants.

    Propriétés sur les arbres

    • h(T) ≤ taille(T) – 1 ; Egalité obtenue pour un arbre filiforme.
    • Pour tout arbre binaire T de taille n et de hauteur h : log₂n ≤ h ≤ n - 1.
    • Tout arbre binaire non vide T ayant f feuilles a une hauteur h(T) supérieure ou égale à [log₂f].
    • Un arbre binaire localement complet ayant n nœuds internes a (n + 1) feuilles.

    Exploration d'arbres

    • Pas aussi simple que dans le cas des listes.
    • Pas d'ordre naturel.
    • Deux types de parcours :
      • En largeur d'abord.
      • En profondeur d'abord.

    Parcours en largeur d'abord

    • L'ordre d'évaluation des noeuds est donné par les différents niveaux des noeuds (Niveau 1, Niveau 2,...).

    Type de données

    • Une structure de données chaînée est mise en œuvre pour représenter un nœud d'arbre.

    Parcours en profondeur d'abord

    • L'ordre d'évaluation des nœuds dépend de la méthode de parcours (préfixe, infixe, post fixe).

    Visite de chaque noeud

    • Les différents types de parcours (préfixe, infixe, post fixe) dépendent de l'ordre de traitement des nœuds.

    Algorithmes pour les parcours d'arbre binaire

    • Algorithmes pour l'implémentation des différents parcours d'arbre (préfixe, infixe, post fixe). L'idée générale consiste à visiter un nœud, puis ses sous-arbres gauche et droit, suivant un ordre basé sur la position du nœud.

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Cours 7 - Arbres - IN305 PDF

    Description

    Ce quiz explore les structures de données appelées arbres, essentielles en informatique. Vous apprendrez leurs propriétés, leurs définitions récursives et leurs applications pratiques. Testez vos connaissances sur les bases des arbres et leur fonctionnement.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser