Exercices

Chapitre 3: Arbres
  1. Trouver une situation où la représentation sous forme d'arbre est adaptée, et donner un exemple d'arbre dans cette situation avec la signification des nœuds et des arêtes utilisées.
  2. La racine d'un arbre en informatique est-elle en haut ou en bas d'un arbre?
  3. Combien de racines un arbre peut-il avoir?
  4. Un arbre binaire complet est un arbre qui est plein à chaque niveau de l'arbre, ce qui signifie qu'il n'y a pas place pour un autre nœud à n'importe quel niveau de l'arbre, sauf aux feuilles. Combien les nœuds sont dans un arbre binaire complet à trois niveaux? Que diriez-vous de 4 niveaux? Que diriez-vous 5 niveaux?
  5. Dans un arbre binaire complet, quelle est la relation entre le nombre de feuilles dans l'arbre et le nombre total de nœuds dans l'arbre?
  6. Les calculs écrits sur une calculatrice sont transformés en arbres binaires avec des nœuds de deux types: des nœuds d'opérations (+, -, * , /), et des nœuds de nombres (0, 1, ...,9). Proposer l'écriture d'un arbre pour l'opération suivante: 5 * 4 + 3 * 2.