#!/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):
        assert type(noeud)==NoeudBin
        assert self!=noeud
        assert noeud!=self.gauche and noeud!=self.droit
        if self.gauche == None :
            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 binaireFil(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)

# 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)
# print(n1)