You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
113 lines
3.0 KiB
113 lines
3.0 KiB
#!/usr/bin/env python3
|
|
# -*- coding: utf-8 -*-
|
|
"""
|
|
Created on Sat Jan 23 19:23:01 2021
|
|
|
|
@author: manu
|
|
"""
|
|
|
|
from File import File_chaine as File
|
|
from Pile import Pile_chaine as Pile
|
|
|
|
|
|
class Arbre:
|
|
"""Un arbre binaire."""
|
|
def __init__(self, val):
|
|
self.valeur = val
|
|
self.gauche = None
|
|
self.droit = None
|
|
|
|
def insere_gauche(self, val):
|
|
"""Insère la valeur val à la racine du fils gauche de l'arbre.
|
|
L'ancien fils gauche devient le fils gauche du nouveau nœud.
|
|
Renvoie le sous arbre créé."""
|
|
nouvel_arbre = Arbre(val)
|
|
nouvel_arbre.gauche = self.gauche
|
|
self.gauche = nouvel_arbre
|
|
return nouvel_arbre
|
|
|
|
def insere_droit(self, val):
|
|
"""Insère la valeur val à la racine du fils droit de l'arbre.
|
|
L'ancien fils droit devient le fils gauche du nouveau nœud.
|
|
Renvoie le sous arbre créé."""
|
|
nouvel_arbre = Arbre(val)
|
|
nouvel_arbre.gauche = self.droit
|
|
self.droit = nouvel_arbre
|
|
return nouvel_arbre
|
|
|
|
|
|
def taille(a):
|
|
"""Renvoie la taille de l'arbre a."""
|
|
if a is None:
|
|
return 0
|
|
return 1 + taille(a.gauche) + taille(a.droit)
|
|
|
|
|
|
def hauteur(a):
|
|
"""Renvoie la hauteur de l'arbre a."""
|
|
if a is None:
|
|
return 0
|
|
return 1 + max(hauteur(a.gauche), hauteur(a.droit))
|
|
|
|
|
|
def parcours_bfs(a):
|
|
"""Affiche tous les nœuds de l'arbre non vide a par un parcours BFS."""
|
|
a_traiter = File()
|
|
a_traiter.enfiler(a)
|
|
while not a_traiter.est_vide():
|
|
noeud = a_traiter.defiler()
|
|
print(noeud.valeur)
|
|
if noeud.gauche is not None:
|
|
a_traiter.enfiler(noeud.gauche)
|
|
if noeud.droit is not None:
|
|
a_traiter.enfiler(noeud.droit)
|
|
|
|
|
|
def parcours_dfs_iter(a):
|
|
"""Affiche tous les nœuds de l'arbre non vide a par un parcours DFS."""
|
|
a_traiter = Pile()
|
|
a_traiter.empiler(a)
|
|
while not a_traiter.est_vide():
|
|
noeud = a_traiter.depiler()
|
|
print(noeud.valeur)
|
|
if noeud.droit is not None:
|
|
a_traiter.empiler(noeud.droit)
|
|
if noeud.gauche is not None:
|
|
a_traiter.empiler(noeud.gauche)
|
|
|
|
|
|
def parcours_dfs_prefixe(a):
|
|
"""Affiche tous les nœuds de l'arbre a par un parcours DFS préfixé."""
|
|
if a is None:
|
|
return
|
|
print(a.valeur)
|
|
parcours_dfs_prefixe(a.gauche)
|
|
parcours_dfs_prefixe(a.droit)
|
|
|
|
|
|
def parcours_dfs_infixe(a):
|
|
"""Affiche tous les nœuds de l'arbre a par un parcours DFS préfixé."""
|
|
if a is None:
|
|
return
|
|
parcours_dfs_infixe(a.gauche)
|
|
print(a.valeur)
|
|
parcours_dfs_infixe(a.droit)
|
|
|
|
|
|
def parcours_dfs_postfixe(a):
|
|
"""Affiche tous les nœuds de l'arbre a par un parcours DFS préfixé."""
|
|
if a is None:
|
|
return
|
|
parcours_dfs_postfixe(a.gauche)
|
|
parcours_dfs_postfixe(a.droit)
|
|
print(a.valeur)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
a = Arbre("A")
|
|
a.insere_gauche("B")
|
|
a.insere_droit("C")
|
|
a.gauche.insere_gauche("D")
|
|
a.gauche.insere_droit("E")
|
|
a.gauche.gauche.insere_droit("G")
|
|
a.droit.insere_gauche("F")
|
|
|