#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Dec 11 09:05:59 2024

@author: pjoulaud
"""
from __future__ import annotations


class Noeud :
    def __init__(self, etiquette, gauche:Noeud=None, droit:Noeud=None):
        self.etiquette = etiquette
        self.g = gauche
        self.d = droit
        
    def __repr__(self):
        return f"    noeud {self.etiquette}\n    /   \ \n {self.g}  {self.d}"
    
    def ajoute_fils_g(self, n):
        self.g = n
    def ajoute_fils_d(self, n):
        self.d = n
    def m_taille(self):
        if self is None :
            return 0
        else :
            if self.g is not None :
                taille_g = self.g.m_taille()
            else :
                taille_g = 0
            if self.d is not None :
                taille_d = self.d.m_taille()
            else :
                taille_d = 0
            return 1 + taille_g + taille_d

def taille(n:Noeud)->int:
    if n is None :
        return 0
    else :
        return 1 + taille(n.g) + taille(n.d)

def hauteur(n:Noeud)->int:
    if n is None :
        return -1
    else :
        return 1 + max(hauteur(n.g), hauteur(n.d))

def feuille(n:Noeud)->int:
    if n is None :
        return 0
    elif n.g is None and n.d is None :
        return 1
    else :
        return  feuille(n.g) + feuille(n.d)

def noeud(n:Noeud)->int:
    if n is None :
        return 0
    elif n.g is None and n.d is None :
        return 0
    else :
        return  1 + noeud(n.g) + noeud(n.d)

def estFiliforme(n:Noeud)->bool :
    if n.g is not None and n.d is not None:
        return False
    elif n.g is not None :
        return estFiliforme(n.g)
    elif n.d is not None :
        return estFiliforme(n.d)
    else :
        return True

def localComplet(n:Noeud)->bool :
    if n.g is None and n.d is None:
        return True
    elif n.g is None or n.d is None :
        return False
    else :
        return localComplet(n.g) and localComplet(n.d)

def Complet(n:Noeud)->bool :
    if n is None :
        return True
    elif n.g is None and n.d is None:
        return True
    elif n.g is None or n.d is None :
        return False
    elif hauteur(n.g) != hauteur(n.d):
        return False
    else :
        return Complet(n.g) and Complet(n.d)

def Parfait(n:Noeud)->bool :
    if n is None :
        return True
    elif hauteur(n.g)==hauteur(n.d):
        return Complet(n.g) and Parfait(n.d)
    elif hauteur(n.g)==hauteur(n.d)+1 :
        return Parfait(n.g) and Complet(n.d)
    else:
        return False

def prefixe(n:Noeud) :
    print(n.etiquette, end=' - ')
    if n is None :
        return
    if n.g is not None :
        prefixe(n.g)
    if n.d is not None :
        prefixe(n.d)

def infixe(n:Noeud) :
    if n is None :
        return
    if n.g is not None :
        prefixe(n.g)
    print(n.etiquette, end=' - ')
    if n.d is not None :
        prefixe(n.d)

def postfixe(n:Noeud) :
    """
    Parameters
    ----------
    n : Noeud
        Noeud arbre binaire.
    
    >>> n1, n2, n3, n4, n5, n6, n7 = Noeud('1'), Noeud('2'), Noeud('3'), Noeud('4'), Noeud('5'), Noeud('6'), Noeud('7') 
    >>> n1.ajoute_fils_g(n2)
    >>> n1.ajoute_fils_d(n3)
    >>> n3.ajoute_fils_g(n4)
    >>> n3.ajoute_fils_d(n5)
    >>> n2.ajoute_fils_g(n6)
    >>> n6.ajoute_fils_d(n7)
    >>> prefixe(n1)
    1 - 2 - 6 - 7 - 3 - 4 - 5 - None
    """
    if n is None :
        return
    if n.g is not None :
        prefixe(n.g)
    if n.d is not None :
        prefixe(n.d)
    print(n.etiquette, end=' - ')

def estUnArbreBinaire(n:Noeud)->bool:
    if n.g==None and n.d==None : #c' est une feuille
        return True
    elif n.g==None : #pas de sous arbre gauche
        if n.etiquette<n.d.etiquette and estUnArbreBinaire(n.d):
            return True
        else :
            return False
    elif n.d==None : #pas de sous arbre droit
        if n.g.etiquette<n.etiquette and estUnArbreBinaire(n.g):
            return True
        else :
            return False
    else : #il y a un sous arbre gauche et un sous arbre droit
        if n.g.etiquette<n.etiquette and estUnArbreBinaire(n.g)\
            and n.etiquette<=n.d.etiquette and estUnArbreBinaire(n.d):
            return True
        else :
            return False

def plusPetitElem(n:Noeud)->int:
    if n.g==None :
        return n.etiquette
    else :
        return plusPetitElem(n.g)

def plusGrandElem(n:Noeud)->int:
    if n.d==None :
        return n.etiquette
    else :
        return plusGrandElem(n.d)

def estPresent(n:Noeud, elem:str)->bool:
    if elem == n.etiquette:
        return True
    elif elem<n.etiquette and n.g is not None :
        return estPresent(n.g, elem)
    elif elem>n.etiquette and n.d is not None :
        return estPresent(n.d, elem)  
    else :
        return False

def insertionElem(n:Noeud, elem:str)->bool:
    if elem<n.etiquette and n.g is None:
        n.ajoute_fils_g(Noeud(elem))
    elif elem<n.etiquette and n.g is not None:
        insertionElem(n.g, elem)
    elif elem>n.etiquette and n.d is None:
        n.ajoute_fils_d(Noeud(elem))
    elif elem>n.etiquette and n.d is not None:
        insertionElem(n.d, elem)
        

n1 = Noeud('1')   
n2 = Noeud('2')
n3 = Noeud('3')
n4 = Noeud('4')
n5 = Noeud('5')     
n6 = Noeud('6')  
n7 = Noeud('7') 
n1.ajoute_fils_g(n2)
n1.ajoute_fils_d(n3)
n3.ajoute_fils_g(n4)
n3.ajoute_fils_d(n5)
n2.ajoute_fils_g(n6)
n6.ajoute_fils_d(n7)
print('taille : ', taille(n1))
print(n1.m_taille())
print('hauteur', hauteur(n1))
print('feuille', feuille(n1))
print('noeud', noeud(n1))
print('estFiliforme', estFiliforme(n1))
print('estFiliforme', estFiliforme(n5))
print('localComplet', localComplet(n1))
print('Complet', Complet(n1))
print('Parfait', Parfait(n1))
print('prefixe')
print(prefixe(n1))
print('infixe')
print(infixe(n1))
print('postfixe')
print(postfixe(n1))
n11 =  Noeud('11')   
n12 = Noeud('12')
n13 = Noeud('13')
n14 = Noeud('14')
n15 = Noeud('15')     
n16 = Noeud('16')  
n17 = Noeud('17') 
n13.ajoute_fils_g(n12)
n13.ajoute_fils_d(n14)
n12.ajoute_fils_g(n11)
print('arbre binaire de recherche')
print(estUnArbreBinaire(n1))
print('arbre binaire de recherche II')
print(estUnArbreBinaire(n11))
print('est présent : ')
print(estPresent(n13, '14'))
insertionElem(n13, '25')