Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_programmes_a_connaitre:algorithmique_term:taille_arbre [2021/01/19 10:32]
mc created
+++ les_programmes_a_connaitre:algorithmique_term:taille_arbre [2023/01/04 11:44] (Version actuelle)
hk [Calculer la hauteur et la taille d'un arbre]
@@ Ligne 1: / Ligne 1: @@
-====== Calculer la hauteur et la taille d'un arbre ======
+====== 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

Différences

Outils de la page