Wiki NSI

rappel : profondeur maximale d'un arbre.

Programme permettant de calculer la hauteur d'un arbre :

#---Classe permettant l'implémentation de l'arbre binaire---
class ArbreBinaire:
   def __init__(self, valeur):
      self.valeur = valeur
      self.enfant_gauche = None
      self.enfant_droit = None
 
   def insert_gauche(self, valeur):
      if self.enfant_gauche == None:
         self.enfant_gauche = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_gauche = self.enfant_gauche
         self.enfant_gauche = new_node
 
   def insert_droit(self, valeur):
      if self.enfant_droit == None:
         self.enfant_droit = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_droit = self.enfant_droit
         self.enfant_droit = new_node
 
   def get_valeur(self):
      return self.valeur
 
   def get_gauche(self):
      return self.enfant_gauche
 
   def get_droit(self):
      return self.enfant_droit
 
#---------------------fin de la classe---------------------
 
#--------début de la construction de l'arbre binaire-------
racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')
 
b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')
 
f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')
 
c_node = b_node.get_gauche()
c_node.insert_droit('E')
 
g_node = f_node.get_gauche()
g_node.insert_gauche('I')
 
h_node = f_node.get_droit()
h_node.insert_droit('J')
#--------fin de la construction de l'arbre binaire--------
T = racine
 
"""
Objectif : définir la hauteur d'un arbre binaire
Entrée : T->noeud racine
Sortie: hauteur de l'arbre
""" 
def hauteur(T):
    if T!=None:
        return 1+(max(hauteur(T.get_gauche()),(hauteur(T.get_droit()))))
    else:
        return 0

rappel : nombre de nœuds composant l'arbre

Algorithme permettant de calculer la taille de l'arbre :

VARIABLE
T : arbre
x : noeud
 
DEBUT
#---Classe permettant l'implémentation de l'arbre binaire---
class ArbreBinaire:
   def __init__(self, valeur):
      self.valeur = valeur
      self.enfant_gauche = None
      self.enfant_droit = None
 
   def insert_gauche(self, valeur):
      if self.enfant_gauche == None:
         self.enfant_gauche = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_gauche = self.enfant_gauche
         self.enfant_gauche = new_node
 
   def insert_droit(self, valeur):
      if self.enfant_droit == None:
         self.enfant_droit = ArbreBinaire(valeur)
      else:
         new_node = ArbreBinaire(valeur)
         new_node.enfant_droit = self.enfant_droit
         self.enfant_droit = new_node
 
   def get_valeur(self):
      return self.valeur
 
   def get_gauche(self):
      return self.enfant_gauche
 
   def get_droit(self):
      return self.enfant_droit
 
#---------------------fin de la classe---------------------
 
#--------début de la construction de l'arbre binaire-------
racine = ArbreBinaire('A')
racine.insert_gauche('B')
racine.insert_droit('F')
 
b_node = racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')
 
f_node = racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')
 
c_node = b_node.get_gauche()
c_node.insert_droit('E')
 
g_node = f_node.get_gauche()
g_node.insert_gauche('I')
 
h_node = f_node.get_droit()
h_node.insert_droit('J')
#--------fin de la construction de l'arbre binaire--------
T = racine
 
"""
Objectif : définir la taille d'un arbre binaire
Entrée : T->noeud racine
Sortie: taille de l'arbre
""" 
def taille(T):
    if T != None:
        return 1+taille(T.get_gauche())+taille(T.get_droit())
    else:
        return 0

Cours sur les arbres binaires.

Algorithmes sur les arbres binaires et les arbres binaires de recherche.