Corrigé exercice 3 les arbres

Q1a
Nombre de nœuds = 7 (taille max pour une hauteur h : 2h - 1 = 1).
Q1b
profondeur maximale du nœud racine = 4
NB : par convention, ici un arbre réduit à un seul nœud est de hauteur 1
Q2
Taille : 7
Hauteur : 3 (par convention h(Δ) = 1)

Q3
Taille : 7
Hauteur : 4

Q4

def hauteur(self):
    return self.racine.hauteur()

Q5

def taille(self) -> int:
   if self.gauche == None and self.droite == None:
      return 1
   elif self.gauche == None:
      return 1 + self.droite.taille()
   elif self.droite == None:
      return 1 + self.gauche.taille()
   else:
      return 1 + self.gauche.taille() + self.droite.taille()
def taille(self):
   return self.racine.taille()

Q6a
2(h-1) – 1 < taille ≤ 2h – 1
doù t_min = 2(h-1) – 1

Q6b

def bien_construit(self) -> bool:
   return 2**(self.racine.hauteur() - 1) - 1 < self.racine.taille() <= 2**self.racine.hauteur() - 1