Terminale NSI : Exercices Arbres

Voici le tableau décrivant un arbre :

  1. Représenter l'arbre correspondant.
  2. Quelle est la hauteur de cet arbre ?
  3. Cet arbre est-il binaire ? complet ? dégénéré ?
  4. Quel est le résultat de cette expression numérique ?
  2. La hauteur de l'arbre est 3.

  3. L'arbre est binaire car chaque noeud possède au plus deux enfants.

    L'arbre n'est pas complet (tous les feuilles ne sont pas au niveau hiérarchique le plus bas).

    L'arbre est localement complet (tous les noeuds possèdent 2 ou aucun enfant).

    L'arbre n'est pas dégénéré (filiforme).

  4. $((2 \times 3) - 1) \times (5 + (8 \div 2)) = (6 - 1) \times (5 + 4) = 5 \times 9 = 45$

On donne l'arbre suivant :

  1. Calculer toutes les longueurs de cheminement.
  2. En déduire les profondeurs moyennes.

    • Longueur de cheminement : LC(B) = H(1) + H(2) + H(3) + .... + H(12) + H(13)

      $LC(B) = 0 + 2 \times 1 + 4 \times 2 + 4 \times 3 + 2 \times 4 = 0 + 2 + 8 + 12 + 8 = 30$

    • Longueur de cheminement externe : LCE(B) = H(8) + H(12) + H(13) + H(5) + H(6) + H(10) + H(11)

      LCE(B) = 3 + 4 + 4 + 2 + 2 + 3 + 3 = 21

    • Longueur de cheminement interne : LCI(B) = LC(B) - LCE(B) = 30 - 21 = 9

    • Profondeur moyenne : $ PM(B) = \frac{LC(B)}{T(B)} = \frac{30}{13} \approx 2,31$

    • Profondeur moyenne externe : $ PME(B) = \frac{LCE(B)}{NF(B)} = \frac{21}{7} \approx 3$

    • Profondeur moyenne interne : $ PMI(B) = \frac{LCI(B)}{T(B)-NF(B)} = \frac{9}{13-7} = \frac{3}{2} = 1,5$

On donne une liste aléatoire de 13 entiers : [22, 31, 56, 12, 51, 8, 35, 7, 3, 14, 44, 2, 6]

  1. Construire dans l'ordre de la liste l'arbre binaire de recherche associé.

  2. Quelle est la hauteur de cet arbre ?

  3. Construire un arbre équilibré pour cette même liste d'entiers.

  4. Quelle est la hauteur de l'arbre équilibré ?

    2. La hauteur de l'arbre est de 5.
    4. La hauteur de l'arbre équilibré est de 3.