Arbre

On peut aussi représenter un arbre binaire en utilisant un dictionnaire où chaque clé est un nœud et la valeur associée est une liste contenant son fils gauche et son fils droit (None s'il n'y a pas de fils).

arbre = {
    5: [3, 8],
    3: [None, None],
    8: [None, None]
}
 
def parcours_infixe(noeud, arbre):
    """
    Objectif :
    Affiche les étiquettes de l'arbre en parcours infixe (gauche, racine, droite).
    Entrée :
    noeud : tout type ou None : la clé du nœud de départ du parcours
    arbre : dict : le dictionnaire représentant l'arbre binaire
    Sortie :
    """
    if noeud is not None:  #on ne parcourt que si le nœud existe
        fils_gauche, fils_droit = arbre[noeud]
        parcours_infixe(fils_gauche, arbre)
        print(noeud)
        parcours_infixe(fils_droit, arbre)
 
parcours_infixe(5, arbre)  #affiche 3, 5, 8

En terminale On peut représenter un arbre binaire en créant une classe Noeud, où chaque nœud possède une étiquette (sa valeur) et deux fils : gauche et droit (qui valent None s'il n'y a pas de fils).

class Noeud:
    def __init__(self, etiquette, gauche=None, droit=None):
        """
        Objectif :
        Crée un nœud d'arbre binaire.
        Entrée :
        etiquette : tout type : la valeur portée par le nœud
        gauche    : Noeud ou None : le fils gauche du nœud
        droit     : Noeud ou None : le fils droit du nœud
        Sortie :
        """
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit
 
#construction d'un petit arbre binaire
arbre = Noeud(5, Noeud(3), Noeud(8))
 
def parcours_infixe(noeud):
    """
    Objectif :
    Affiche les étiquettes de l'arbre en parcours infixe (gauche, racine, droite).
    Entrée :
    noeud : Noeud ou None : le nœud de départ du parcours
    Sortie :
    """
    if noeud is not None:  #on ne parcourt que si le nœud existe
        parcours_infixe(noeud.gauche)
        print(noeud.etiquette)
        parcours_infixe(noeud.droit)
 
parcours_infixe(arbre)  #affiche 3, 5, 8