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:42]
mc
+++ 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.
-Algorithme permettant de calculer la hauteur d'un arbre :
+Programme permettant de calculer la hauteur d'un arbre :
 <code python>
-VARIABLE
+#---Classe permettant l'implémentation de l'arbre binaire---
-T : arbre
+class ArbreBinaire:
-x : noeud
+   def __init__(self, valeur):
+      self.valeur = valeur
+      self.enfant_gauche = None
+      self.enfant_droit = None
-DEBUT
+   def insert_gauche(self, valeur):
-HAUTEUR(T) :
+      if self.enfant_gauche == None:
-  si T ≠ NIL :
+         self.enfant_gauche = ArbreBinaire(valeur)
-    x ← T.racine
+      else:
-    renvoyer 1 + max(HAUTEUR(x.gauche), HAUTEUR(x.droit))
+         new_node = ArbreBinaire(valeur)
-  sinon :
+         new_node.enfant_gauche = self.enfant_gauche
-    renvoyer 0
+         self.enfant_gauche = new_node
-  fin si
-FIN
+   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>
@@ Ligne 32: / Ligne 87: @@
 DEBUT
-TAILLE(T) :
+#---Classe permettant l'implémentation de l'arbre binaire---
-  si T ≠ NIL :
+class ArbreBinaire:
-    x ← T.racine
+   def __init__(self, valeur):
-    renvoyer 1 + TAILLE(x.gauche) + TAILLE(x.droit)
+      self.valeur = valeur
-  sinon :
+      self.enfant_gauche = None
-    renvoyer 0
+      self.enfant_droit = None
-  fin si
-FIN
+   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