Terminale - Arbres

Exercices

On donne ci-dessous un tableau caractérisant un arbre :

  1. Peut-on déterminer, à partir du tableau seul, et de façon "rapide" :
    1. Le nombre de feuilles ?
    2. La racine de l'arbre ?
    3. La hauteur de l'arbre ?
  2. Représenter l'arbre correspondant au tableau.
  3. Déterminer la hauteur de cet arbre.
  4. Quel est le résultat de la suite d'opérations arithmétiques associée à cet arbre ?
On considère un arbre généré par la suite d'opérations suivantes : 
A = FEUILLE(6)
B = FEUILLE(10)
C = FEUILLE(2)
D = FEUILLE(5)
E = ARBRE(8, A, B)
F = ARBRE(3, D, C)
G = ARBRE(7, E, F)
  1. Quelle est la hauteur de cet arbre ?
  2. Cet arbre est-il un arbre binaire de recherche ?
  3. Donner sa représentation contigüe.
  4. Donner sa représentation sous forme de tableau.

Voici une liste de nombres entiers :

  1. Construire, dans l'ordre de la liste, l'arbre binaire de recherche correspondant.
  2. Quelle est la hauteur de cet arbre ? Est-il équilibré ?
  3. Construire un arbre équilibré pour cette même liste d'entiers.
  4. Quelle est la hauteur de l'arbre équilibré ?

Cours Sommaire