#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Dec 11 09:16:27 2025

@author: pjoulaud
"""

class NoeudBin:
    def __init__(self, etiquette, left=None, right=None):
        self.e = etiquette
        if type(left)==NoeudBin:
            self.gauche = left
        elif type(left)==str:
            self.gauche = NoeudBin(left)
        else :
            self.gauche = None
        if type(right)==NoeudBin:
            self.droit = right
        elif type(right)==str:
            self.droit = NoeudBin(right)
        else :
            self.droit = None
    def ajoute_un_fils(self, noeud, a_gauche=True):
        assert type(noeud)==NoeudBin
        assert self!=noeud
        assert noeud!=self.gauche and noeud!=self.droit
        if a_gauche :
            self.gauche = noeud
        else:
            self.droit = noeud
    
    def __repr__(self):
        return "NoeudBin bin : "+self.e
    
    # def __str__(self):
    #     if self.fils :
    #         chaine = "\n"
    #         for f in self.fils :
    #             chaine = chaine + " " + f.__str__()
    #         return self.e + chaine
    #     return self.e

def taille(n:NoeudBin)->int:
    if n == None :
        return 0 #cas de base
    else :
        return 1 + taille(n.gauche) + taille(n.droit)

def hauteur(n:NoeudBin)->int:
    if n == None :
        return -1 #cas de base
    else :
        return 1 + max(hauteur(n.gauche), hauteur(n.droit))

def nbFeuilles(n:NoeudBin)->int:
    if n == None :
        return 0 #cas de base
    if n.gauche==None and n.droit==None :
        return 1
    else :
        return nbFeuilles(n.gauche) + nbFeuilles(n.droit)

def nbNoeudInterne(n:NoeudBin)->int:
    if n == None :
        return 0 #cas de base
    elif n.gauche==None and n.droit==None :
        return 0
    else :
        return 1 + nbNoeudInterne(n.gauche) + nbNoeudInterne(n.droit)

def creerListeNoeud(l:list)->list:
    ma_liste = []
    for e in l :
        ma_liste.append(NoeudBin(e))
    return ma_liste

def tailleTuple(t:tuple)->int :
    if len(t)==0:
        return 0
    return 1 + tailleTuple(t[1])+tailleTuple(t[2])

def hauteurTuple(t:tuple)->int :
    if len(t)==0:
        return -1
    return 1 + max(hauteurTuple(t[1]),hauteurTuple(t[2]))
        

def nbFeuilleTuple(t:tuple)->int:
    if len(t)==0:
        return 0
    elif len(t[1])+len(t[2])==0:
        return 1
    else :
        return nbFeuilleTuple(t[1])+nbFeuilleTuple(t[2])

def nbNoeudInterneTuple(t:tuple)->int:
    if len(t)==0:
        return 0
    elif len(t[1])==0 and len(t[2])==0:
        return 0
    else :
        return 1+nbNoeudInterneTuple(t[1])+nbNoeudInterneTuple(t[2])

def tupleVersPoo(t:tuple)->NoeudBin:
    if len(t)==0:
        return None
    else :
        n = NoeudBin(t[0])
        if len(t[1])!=0:
            n.ajoute_un_fils(tupleVersPoo(t[1]))
        if len(t[2])!=0:
            n.ajoute_un_fils(tupleVersPoo(t[2]), a_gauche=False)    
        return n

def binaireFil2(n:NoeudBin)->bool:
    if n == None :
        return True
    if n.gauche!=None and n.droit!=None :
        return False
    elif n.gauche==None : 
        return binaireFil(n.droit)
    elif n.droit==None :
        return binaireFil(n.gauche)

def binaireFil(n:NoeudBin)->bool:
    if hauteur(n)<=0 :
        return False
    if n.gauche!=None and n.droit!=None :
        return False
    elif n.gauche==None : 
        if hauteur(n)==1:
            return True
        else :
            return binaireFil(n.droit)
    elif n.droit==None : 
        if hauteur(n)==1:
            return True
        else :
            return binaireFil(n.gauche)

def localComplet(n:NoeudBin)->bool:
    if n==None:
        return True
    elif n.gauche==None and n.droit==None:
        return True
    elif n.gauche==None or n.droit==None:
        return False
    else :
        return localComplet(n.gauche) and localComplet(n.droit)
    
def complet(n:NoeudBin)->bool:
    if n==None:
        return True
    elif hauteur(n.gauche) != hauteur(n.droit):
        return False
    else :
        return complet(n.gauche) and complet(n.droit)

def parcoursPrefixe2(n:NoeudBin)->str:
    if n==None :
        return ""
    else :
        return n.e + parcoursPrefixe2(n.gauche) + parcoursPrefixe2(n.droit)    

def parcoursInfixe(n:NoeudBin)->str:
    if n==None:
        return ""
    else :
        return parcoursInfixe(n.gauche) + n.e + parcoursInfixe(n.droit)    
    
def parcoursPostfixe(n:NoeudBin)->str:
    if n==None :
        return ""
    else :
        return parcoursPostfixe(n.gauche) + parcoursPostfixe(n.droit) + n.e   

def estABR(n:NoeudBin)->bool :
    print(n)
    if n==None:
        return True
    if n.gauche==None and n.droit==None:
        return True
    elif n.gauche==None:
        return n.e>n.droit.e and estABR(n.droit)
    elif n.droit==None:
        return n.e<n.gauche.e and estABR(n.gauche)
    else :
        return n.gauche.e<n.e<n.droit.e and estABR(n.gauche) and estABR(n.droit)

def plusPetitElemABR(n:NoeudBin)->str:
    assert estABR(n)
    if  n.gauche==None:
        return n.e
    else :
        return plusPetitElemABR(n.gauche)

def plusGrandElemABR(n:NoeudBin)->str:
    assert estABR(n)
    if  n.droit==None:
        return n.e
    else :
        return plusGrandElemABR(n.droit)        

def estPresentDansABR(val, n:NoeudBin)->bool:
    assert estABR(n)
    if n==None:
        return False
    elif val==n.e :
        return True
    elif val<n.e:
        return estPresentDansABR(val, n.gauche)
    else:
        return estPresentDansABR(val, n.droit)

def insererCleDansABR(val, n:NoeudBin)->NoeudBin:
    assert estABR(n)
    if n==None:
        return NoeudBin(val)
    if val<n.e :
        if n.gauche==None:
            #return n.ajoute_un_fils(NoeudBin(val))
            n.gauche = NoeudBin(val)
            return n
        else :
            return insererCleDansABR(val, n.gauche)
    if val>n.e :
        if n.droit==None:
            #return n.ajoute_un_fils(NoeudBin(val), a_gauche=False)
            n.droit = NoeudBin(val)
            return n
        else :
            return insererCleDansABR(val, n.droit)
        



# n1, n2, n3, n4, n5 = NoeudBin("1"), NoeudBin("2"), NoeudBin("3"), NoeudBin("4"), NoeudBin("5")
n_a, n_b, n_c, n_d, n_e = NoeudBin("A"), NoeudBin("B"), NoeudBin("C"), NoeudBin("D"), NoeudBin("E")
n_f, n_g, n_h, n_i, n_j = NoeudBin("F"), NoeudBin("G"), NoeudBin("H"), NoeudBin("I"), NoeudBin("J")
n_k, n_l, n_m, n_n, n_o = NoeudBin("K"), NoeudBin("L"), NoeudBin("M"), NoeudBin("N"), NoeudBin("O")
n_p, n_q = NoeudBin("P"), NoeudBin("Q")
n_a.ajoute_un_fils(n_b)
n_a.ajoute_un_fils(n_c)
n_b.ajoute_un_fils(n_d)
n_d.ajoute_un_fils(n_e)
n_b.ajoute_un_fils(n_e)
n_c.ajoute_un_fils(n_f)
n_c.ajoute_un_fils(n_g)
n_e.ajoute_un_fils(n_h)
n_e.ajoute_un_fils(n_i)
n_i.ajoute_un_fils(n_n)
n_i.ajoute_un_fils(n_o)
n_f.ajoute_un_fils(n_j)
n_f.ajoute_un_fils(n_k)
n_g.ajoute_un_fils(n_l)
n_g.ajoute_un_fils(n_m)
n_m.ajoute_un_fils(n_p)
n_m.ajoute_un_fils(n_q)
toto= tupleVersPoo(('B',('A', (), ()),('C', (),())))
tata= tupleVersPoo(('A',
                    ('B', 
                     ('D',(),()),
                     ('E',
                      ('H',(),()),
                      ('I',
                       ('N',(),()),
                       ('O',(),())))),
                    ('C', 
                     ('F',
                      ('J',(),()),
                      ('K',(),())),
                     ('G',
                      ('L',(),()),
                      ('M',
                       ('P',(),()),
                       ('Q',(),()))))))
titi= tupleVersPoo(('A',(),('B',('C',(),('D',(),())),())))
tyty= tupleVersPoo(('A',
                   ('B',('D',(),()),('E',(),())),
                   ('C',('F',(),()),('G',(),()))))
tutu= tupleVersPoo(('J',
                   ('D',('C',(),()),('E',(),())),
                   ('R',('Q',(),()),('S',(),()))))
'',(),()