NSI Terminale
def parcours_prefixe(arbre):
print(arbre.valeur)
if arbre.filsgauche is not None:
parcours_prefixe(arbre.filsgauche)
if arbre.filsdroit is not None:
parcours_prefixe(arbre.filsdroit)
Au lieu de les afficher, il peut être utile de récupérer la liste des nœuds dans l'ordre de leur parcours; pour cela, au lieu de simplement afficher la valeur de l'étiquette de chaque noeud, on l'ajoutera à la fin d'un tableau.
def parcours_prefixe_tab(arbre, parcours):
parcours.append(arbre.valeur)
if arbre.filsgauche is not None:
parcours_prefixe_tab(arbre.filsgauche, parcours)
if arbre.filsdroit is not None:
parcours_prefixe_tab(arbre.filsdroit, parcours)
return parcours # indispensable : la méthode append ne renvoie rien !
parcours = parcours_prefixe_tab(arbre, []) # passage d'un tableau vide en argument au paramètre 'parcours' de la fonction
def parcours_infixe(arbre):
if arbre.filsgauche is not None:
parcours_infixe(arbre.filsgauche)
print(arbre.valeur)
if arbre.filsdroit is not None:
parcours_infixe(arbre.filsdroit)
def parcours_infixe(arbre):
if arbre.filsgauche is not None:
parcours_infixe(arbre.filsgauche)
if arbre.filsdroit is not None:
parcours_infixe(arbre.filsdroit)
print(arbre.valeur)
def parcours_largeur(arbre):
file = File()
file.enfiler(arbre)
while not file.est_vide():
s = file.defiler()
print(s.valeur)
if s.filsgauche is not None:
file.enfiler(s.filsgauche)
if s.filsdroit is not None:
file.enfiler(s.filsdroit)
def nb_feuilles(arbre)->int:
if arbre.filsgauche is None and arbre.filsdroit is None:
return 1
if arbre.filsgauche is None:
return nb_feuilles(arbre.filsdroit)
elif arbre.filsdroit is None:
return nb_feuilles(arbre.filsgauche)
else:
return nb_feuilles(arbre.filsgauche) + nb_feuilles(arbre.filsdroit)
Dans un parcours en largeur d'abor, la feuille la plus haute est la première feuille rencontrée lors du parcours :
Il faut tout simplement, après l'avoir créé à partir du tableau non trié, faire un parcours infixe d'un ABR:
def tri_ABR(L: list)->list:
tab = []
abr = ABR(None)
for element in L:
abr = abr.inserer(element)
L = abr.parcours_infixe_tab() # version du parcours infixe qui renvoie la liste des nœuds
return L
from classe_arbre import *
def est_abr(arbre)->bool:
if arbre.filsgauche is None and arbre.filsdroit is None:
return True
return (arbre.filsgauche.valeur < arbre.valeur < arbre.filsdroit.valeur) and est_abr(arbre.filsdroit) and est_abr(arbre.filsgauche)
pas_abr = Arbre(1, Arbre(3, Arbre(4, Arbre(6), Arbre(8))), Arbre(9, Arbre(2), Arbre(4)))
abr = Arbre(23, Arbre(12, Arbre(6), Arbre(13)), Arbre(36, Arbre(28), Arbre(45)))
print(est_abr(pas_abr)) # False
print(est_abr(abr)) # True
def prof(arbre, valeur, niveau = 0)->bool:
if arbre is None:
return -1
if arbre.valeur == valeur:
return niveau
if arbre.filsgauche is None:
return prof(arbre.filsdroit, valeur, niveau+1)
elif arbre.filsdroit is None:
return prof(arbre.filsgauche, valeur, niveau+1)
else:
return max(prof(arbre.filsdroit, valeur, niveau+1), prof(arbre.filsgauche, valeur, niveau+1))
La solution de ce problème d'analyse syntaxique est proposée ici par Simon Oudet, élève de terminale NSI en 2021-2022.
Simon traite tout d'abord une chaîne de caractère en parenthésage absolu puis créé une fonction construisant ce parenthésage.
La fonction encodeArbreArith est basée sur la détermination d'un pivot central ( ou du moins le plus central possible ) dans l'expression qui permet de limiter le déséquilibre
de l'arbre arithmétique correspondant.
C'est bien sur une fonction récursive, exploitant ici la structure récursive de l'arbre lui même.
Le module arbres contient toutes les fonctions permettant de créer un arbre binaire.
import arbres as arb
def encodeArbreArith (expr, a, b) :
"""
ne fonctionne que avec un parenthésage absolu et avec + d'une opération
(pour l'instant)
(((5)+(7))-(8))
((5)*((55)+(8)))
input : expr : l'expression sans espace et avec un parenthésage absolu
a : l'index de la première parenthèse
b : l'index de la dernière
"""
piv = 0
mini = float ("inf")
nb = 0
nb_actu = 0
for i in range (a, b + 1) :
if (expr [i] == "(") :
nb += 1
nb_actu += 1
elif (expr [i] == ")") :
nb_actu -= 1
elif (expr [i - 1] == ")") and (expr [i + 1] == "(") and nb_actu < mini :
mini = nb_actu
piv = i
if (nb == 1): # seulement un chiffre dans la parenthèse
return arb.Arbre (expr [a+1:b])
return arb.Arbre (expr [piv], encodeArbreArith (expr, a + 1, piv - 1), encodeArbreArith (expr, piv + 1, b - 1))
def init (expr) :
"""
fait un traitement de l'expression
afin qu'elle puisse etre traite dans
la fonction principale
- 5 -> (5)
"""
sup = ["*", "/"]
rep = ""
for i in expr :
if (i in sup) :
pass
rep = ""
en_cour = False
for i in expr :
if (48 <= ord (i)) and (ord (i) <= 57) : # est un chiffre
if not (en_cour) :
rep += "("
en_cour = True
elif (en_cour) :
rep += ")"
en_cour = False
rep += i
return rep
print ("start")
print ()
# ex = "(5+6)*(15-16)+3"
ex = init ("(((5+6)*(15-16))+3)")
arbre = encodeArbreArith (ex, 0, len (ex) - 1)
arbre.dessine ()