Correction : Algorithmes sur les arbres - Parcours

Parcours préfixe

Simple affichage des étiquettes

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)			
			

Récupération de la liste des nœuds parcourus

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
			

Parcours infixe

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)			
			

Parcours suffixe

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)	
			

Parcours en largeur

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)			
			

Applications

Nombre de feuilles

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)
			

Feuille la plus haute

Dans un parcours en largeur d'abord, la feuille la plus haute est la première feuille rencontrée lors du parcours :

Tri avec un ABR

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			
			

Cet arbre est-il un ABR ?

		
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
			

Profondeur d'un nœud

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))
		  

Arbres arithmétiques

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 ()