Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
les_programmes_a_connaitre:algorithmique_term:parcours_arbre [2021/01/19 10:50] mc |
les_programmes_a_connaitre:algorithmique_term:parcours_arbre [2022/05/13 11:18] (Version actuelle) bh [Parcours en largeur d'abord] |
||
---|---|---|---|
Ligne 4: | Ligne 4: | ||
<code python> | <code python> | ||
- | VARIABLE | + | #---Classe permettant l' |
- | T : arbre | + | class ArbreBinaire: |
- | x : noeud | + | def __init__(self, |
+ | self.valeur = valeur | ||
+ | self.enfant_gauche = None | ||
+ | self.enfant_droit = None | ||
- | DEBUT | + | def insert_gauche(self, |
- | PARCOURS-PREFIXE(T) : | + | if self.enfant_gauche == None: |
- | si T ≠ NIL : | + | |
- | x ← T.racine | + | else: |
- | | + | new_node = ArbreBinaire(valeur) |
- | | + | |
- | | + | |
- | fin si | + | |
- | FIN | + | def insert_droit(self, |
+ | if self.enfant_droit == None: | ||
+ | self.enfant_droit = ArbreBinaire(valeur) | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | def get_valeur(self): | ||
+ | | ||
+ | |||
+ | def get_gauche(self): | ||
+ | return self.enfant_gauche | ||
+ | |||
+ | def get_droit(self): | ||
+ | return self.enfant_droit | ||
+ | |||
+ | #---------------------fin de la classe--------------------- | ||
+ | |||
+ | # | ||
+ | racine = ArbreBinaire(' | ||
+ | racine.insert_gauche(' | ||
+ | racine.insert_droit(' | ||
+ | |||
+ | b_node = racine.get_gauche() | ||
+ | b_node.insert_gauche(' | ||
+ | b_node.insert_droit(' | ||
+ | |||
+ | f_node = racine.get_droit() | ||
+ | f_node.insert_gauche(' | ||
+ | f_node.insert_droit(' | ||
+ | |||
+ | c_node = b_node.get_gauche() | ||
+ | c_node.insert_droit(' | ||
+ | |||
+ | g_node = f_node.get_gauche() | ||
+ | g_node.insert_gauche(' | ||
+ | |||
+ | h_node = f_node.get_droit() | ||
+ | h_node.insert_droit(' | ||
+ | #--------fin de la construction de l' | ||
+ | T = racine | ||
+ | |||
+ | """ | ||
+ | Objectif : Parcourir l' | ||
+ | Entrée : T->noeud racine | ||
+ | Sortie: - | ||
+ | """ | ||
+ | def préfixe(T): | ||
+ | if T != None: | ||
+ | print(T.get_valeur()) | ||
+ | préfixe(T.get_gauche()) | ||
+ | préfixe(T.get_droit()) | ||
</ | </ | ||
+ | |||
==== Parcours suffixe ==== | ==== Parcours suffixe ==== | ||
<code python> | <code python> | ||
- | VARIABLE | + | #---Classe permettant l' |
- | T : arbre | + | class ArbreBinaire: |
- | x : noeud | + | def __init__(self, |
+ | self.valeur = valeur | ||
+ | self.enfant_gauche = None | ||
+ | self.enfant_droit = None | ||
- | DEBUT | + | def insert_gauche(self, |
- | PARCOURS-SUFFIXE(T) : | + | if self.enfant_gauche == None: |
- | si T ≠ NIL : | + | |
- | x ← T.racine | + | else: |
- | | + | new_node = ArbreBinaire(valeur) |
- | | + | |
- | | + | |
- | fin si | + | |
- | FIN | + | def insert_droit(self, |
+ | if self.enfant_droit == None: | ||
+ | self.enfant_droit = ArbreBinaire(valeur) | ||
+ | else: | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | def get_valeur(self): | ||
+ | | ||
+ | |||
+ | def get_gauche(self): | ||
+ | return self.enfant_gauche | ||
+ | |||
+ | def get_droit(self): | ||
+ | return self.enfant_droit | ||
+ | |||
+ | #---------------------fin de la classe--------------------- | ||
+ | |||
+ | # | ||
+ | racine = ArbreBinaire(' | ||
+ | racine.insert_gauche(' | ||
+ | racine.insert_droit(' | ||
+ | |||
+ | b_node = racine.get_gauche() | ||
+ | b_node.insert_gauche(' | ||
+ | b_node.insert_droit(' | ||
+ | |||
+ | f_node = racine.get_droit() | ||
+ | f_node.insert_gauche(' | ||
+ | f_node.insert_droit(' | ||
+ | |||
+ | c_node = b_node.get_gauche() | ||
+ | c_node.insert_droit(' | ||
+ | |||
+ | g_node = f_node.get_gauche() | ||
+ | g_node.insert_gauche(' | ||
+ | |||
+ | h_node = f_node.get_droit() | ||
+ | h_node.insert_droit(' | ||
+ | #--------fin de la construction de l' | ||
+ | T = racine | ||
+ | |||
+ | """ | ||
+ | Objectif : Parcourir l' | ||
+ | Entrée : T->noeud racine | ||
+ | Sortie: - | ||
+ | """ | ||
+ | def suffixe(T): | ||
+ | if T != None: | ||
+ | suffixe(T.get_gauche()) | ||
+ | suffixe(T.get_droit()) | ||
+ | print(T.get_valeur()) | ||
</ | </ | ||
==== Parcours infixe ==== | ==== Parcours infixe ==== | ||
<code python> | <code python> | ||
- | VARIABLE | + | #---Classe permettant l' |
- | T : arbre | + | class ArbreBinaire: |
- | x : noeud | + | def __init__(self, |
+ | self.valeur = valeur | ||
+ | self.enfant_gauche = None | ||
+ | self.enfant_droit = None | ||
- | DEBUT | + | def insert_gauche(self, |
- | PARCOURS-INFIXE(T) : | + | if self.enfant_gauche == None: |
- | si T ≠ NIL : | + | |
- | x ← T.racine | + | else: |
- | | + | new_node = ArbreBinaire(valeur) |
- | | + | |
- | | + | |
- | fin si | + | |
- | FIN | + | def insert_droit(self, |
+ | if self.enfant_droit == None: | ||
+ | self.enfant_droit = ArbreBinaire(valeur) | ||
+ | else: | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | def get_valeur(self): | ||
+ | | ||
+ | |||
+ | def get_gauche(self): | ||
+ | return self.enfant_gauche | ||
+ | |||
+ | def get_droit(self): | ||
+ | return self.enfant_droit | ||
+ | |||
+ | #---------------------fin de la classe--------------------- | ||
+ | |||
+ | # | ||
+ | racine = ArbreBinaire(' | ||
+ | racine.insert_gauche(' | ||
+ | racine.insert_droit(' | ||
+ | |||
+ | b_node = racine.get_gauche() | ||
+ | b_node.insert_gauche(' | ||
+ | b_node.insert_droit(' | ||
+ | |||
+ | f_node = racine.get_droit() | ||
+ | f_node.insert_gauche(' | ||
+ | f_node.insert_droit(' | ||
+ | |||
+ | c_node = b_node.get_gauche() | ||
+ | c_node.insert_droit(' | ||
+ | |||
+ | g_node = f_node.get_gauche() | ||
+ | g_node.insert_gauche(' | ||
+ | |||
+ | h_node = f_node.get_droit() | ||
+ | h_node.insert_droit(' | ||
+ | #--------fin de la construction de l' | ||
+ | T = racine | ||
+ | |||
+ | """ | ||
+ | Objectif : Parcourir l' | ||
+ | Dans un arbre binaire de recherche -> Renvoie les valeurs dans l' | ||
+ | Entrée : T->noeud racine | ||
+ | Sortie: - | ||
+ | """ | ||
+ | def infixe(T): | ||
+ | if T != None: | ||
+ | infixe(T.get_gauche()) | ||
+ | print(T.get_valeur()) | ||
+ | infixe(T.get_droit()) | ||
</ | </ | ||
// | // | ||
+ | |||
+ | ==== Parcours en largeur d' | ||
+ | |||
+ | <code python> | ||
+ | #---Classe permettant l' | ||
+ | class ArbreBinaire: | ||
+ | def __init__(self, | ||
+ | self.valeur = valeur | ||
+ | self.enfant_gauche = None | ||
+ | self.enfant_droit = None | ||
+ | |||
+ | def insert_gauche(self, | ||
+ | if self.enfant_gauche == None: | ||
+ | | ||
+ | else: | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | def insert_droit(self, | ||
+ | if self.enfant_droit == None: | ||
+ | | ||
+ | else: | ||
+ | | ||
+ | | ||
+ | | ||
+ | |||
+ | def get_valeur(self): | ||
+ | return self.valeur | ||
+ | |||
+ | def get_gauche(self): | ||
+ | return self.enfant_gauche | ||
+ | |||
+ | def get_droit(self): | ||
+ | return self.enfant_droit | ||
+ | |||
+ | # | ||
+ | |||
+ | # | ||
+ | racine = ArbreBinaire(' | ||
+ | racine.insert_gauche(' | ||
+ | racine.insert_droit(' | ||
+ | |||
+ | b_node = racine.get_gauche() | ||
+ | b_node.insert_gauche(' | ||
+ | b_node.insert_droit(' | ||
+ | |||
+ | f_node = racine.get_droit() | ||
+ | f_node.insert_gauche(' | ||
+ | f_node.insert_droit(' | ||
+ | |||
+ | c_node = b_node.get_gauche() | ||
+ | c_node.insert_droit(' | ||
+ | |||
+ | g_node = f_node.get_gauche() | ||
+ | g_node.insert_gauche(' | ||
+ | |||
+ | h_node = f_node.get_droit() | ||
+ | h_node.insert_droit(' | ||
+ | # | ||
+ | T = racine | ||
+ | |||
+ | """ | ||
+ | Objectif : Parcourir l' | ||
+ | Entrée : T->noeud racine | ||
+ | Sortie: - | ||
+ | """ | ||
+ | f = [] | ||
+ | |||
+ | def parcours_largeur(T): | ||
+ | f.append(T) | ||
+ | while len(f) !=0: | ||
+ | x=f.pop(0) | ||
+ | return x | ||
+ | if T.get_gauche != None: | ||
+ | T.get_gauche.append(x.gauche) | ||
+ | f.append(T.get_gauche) | ||
+ | if T.get_droit !=None: | ||
+ | T.get_droit.append(x.droit) | ||
+ | f.append(T.get_droit) | ||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | ===En lien avec cette page : === | ||
+ | [[les_fiches_revisions: | ||
+ | |||
+ | [[les_fiches_revisions: |