Récapitulatif donnees

Arbre représentant une structure hierarchique

• Savoir ce qu'est une Arborescence c'est à dire un Arbre possédant une ???
• Un Arbre peut-il posséder des boucles ou des cycles ?
• Savoir ce qu'est un Noeud
• Savoir ce qui caractérise une Racine
• Savoir ce qui caractérise une Feuille

• Pouvoir tracer l'arbre représentant une situation (plateau de jeu, page HTML, maison...)

• Définir un Arbre comme

  • soit un Arbre Vide
  • soit l'ensemble d'un Noeud et des sous-arbres auxquelles il mène

• Identifier les sous-arbres d'un Arbre dont on vous donne la Racine

Arbre Binaire

• Définir un Arbre Binaire comme

  • soit un Arbre Vide
  • soit l'ensemble d'un Noeud et de ses DEUX sous-arbres

• Savoir que la position du fils Gauche et du fils Droit ne code pas la même information dans le cas d'un Arbre Binaire.

• Donner l'idée générale d'organisation d'un Arbre Binaire

• Savoir utiliser les fonctions d'interface d'un Arbre Binaire (et des Noeuds)

  • nouveauNoeud(x:Elt) -> Noeud
  • contenu(noeud:Noeud) -> Elt
  • nAV() -> Arbre
  • nouvelArbre(noeud:Noeud, g:Arbre, d:Arbre) -> Arbre
  • racine(arbre:Arbre) -> Noeud
  • gauche(arbre:Arbre) -> Arbre
  • droite(arbre:Arbre) -> Arbre

• Savoir trouver la Taille d'un Arbre Binaire connaissant sa géométrie

• Savoir qu'il existe deux choix pour la profondeur d'une Racine
• Savoir trouver la Profondeur d'un Noeud
• Savoir trouver la Hauteur d'un Arbre
• Définir Arbre Binaire Complet
• Comprendre que pour un Arbre Binaire Complet : hauteur = log2(taille+1) si on prend une profondeur de Racine à 1
• Définir Arbre Binaire Filiforme
• Comprendre que pour un Arbre Binaire Filiforme : hauteur = taille si la profondeur de la Racine est de 1

• Estimer la hauteur d'un Arbre Binaire quelconque :

  • Profondeur 1 pour la racine : ⌈log2(taille+1)⌉ ≤ hauteur ≤ taille
  • Profondeur 0 pour la racine : ⌊log2(taille)⌋ ≤ hauteur ≤ taille - 1

• Que vaut log2(2) ?

• Que vaut log2(4) ?
• Que vaut log2(8) ?
• Que vaut log2(16) ?

A faire !

A faire !

A faire !

A faire !