from collections import deque

class Arbre:
    def __init__(self,racine,*enfants):
        self.root = racine
        self.enfants = enfants
    
    """ Parcours""" 

    # en profondeur, ordre préfixe

    def Prefixe(self , L = []):
        L.append(self.root)
        for child in self.enfants:
            child.Prefixe( L )
        return L

    # en profondeur, ordre postfixe

    def Postfixe(self , L = []):
        for child in self.enfants:
            child.Postfixe( L )
        L.append(self.root)
        return L

    # en largeur

    def Largeur(self):
        F , L = deque([]) , []
        L.append(self.root)
        F.append(self)

        while F:
            for child in F[0].enfants:
                L.append(child.root)
                F.append(child)
            F.popleft()
        
        return L


    """ affichages """

    # sous forme de liste

    def AfficheListe(self , ordre):
        if ordre == 'prefixe':
            print( self.Prefixe() )
        elif ordre == 'postfixe':
            print( self.Postfixe() )
        elif ordre == 'largeur':
            print( self.Largeur() )

    # avec marges

    def Affiche(self , space = 0):
        spaces = " " * space
        print(spaces , self.root)
        for child in self.enfants:
            child.Affiche(space + 2)


tree = Arbre('A',
        Arbre(
            'B',
            Arbre( 'C' , 
                Arbre('D' , Arbre('Z') ) , 
                Arbre('E' , Arbre('X') , Arbre('Y') , Arbre('P') ) 
            ),
            Arbre( 'F' , Arbre('G') , Arbre('H') )
        ),
        Arbre(
            'I',
            Arbre( 'J' , Arbre('K') , Arbre('L') ),
            Arbre( 'M' , Arbre('N') , Arbre('O') )
        ) )

tree.AfficheListe('prefixe')
tree.AfficheListe('postfixe')
tree.AfficheListe('largeur')
tree.Affiche()