Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Calculer la hauteur et la taille d'un arbre ====== HK

====Hauteur d'un arbre :==== 
//rappel :// profondeur maximale d'un arbre.

Programme permettant de calculer la hauteur d'un arbre :
<code python>
#---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
</code>

====Taille d'un arbre :====
//rappel :// nombre de nœuds composant l'arbre

Algorithme permettant de calculer la taille de l'arbre :

<code python>
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
</code>

===En lien avec cette page : ===
[[les_fiches_revisions:structure_des_donnees:arbres| Cours sur les arbres binaires]].

[[les_fiches_revisions:algorithmique:algo_arbres|Algorithmes sur les arbres binaires et les arbres binaires de recherche]].
Wiki NSI

Outils pour utilisateurs

Outils du site

Outils de la page
