# -*- coding: utf-8 -*-

############################################################
# Tracé d'un arbre binaire avec le module Turtle de Python
# Version 7
# nsi.gecif.net
# Octobre 2026
############################################################

import turtle

############################################################
# Arbre binaire sous forme de tuples : (valeur, gauche, droite)
############################################################

def taille_arbre(a):
    if a is None:
        return 0
    return 1 + taille_arbre(a[1]) + taille_arbre(a[2])

def profondeur(a):
    if a is None:
        return 0
    return 1 + max(profondeur(a[1]), profondeur(a[2]))

############################################################
# Infixe pour ordre horizontal
############################################################

def parcours_infixe(a, niveau, infos):
    if a is None:
        return
    parcours_infixe(a[1], niveau+1, infos)
    infos.append((a, niveau))
    parcours_infixe(a[2], niveau+1, infos)

############################################################
# Calcul positions
############################################################

def calcul_positions(a):
    infos = []
    parcours_infixe(a, 0, infos)
    if not infos:
        return {}

    n = len(infos)
    prof_max = max(niv for (_, niv) in infos)

    largeur = 800.0
    hauteur = 800.0
    marge = 120.0

    if n > 1:
        esp_x = (largeur - 2*marge) / (n - 1)
    else:
        esp_x = 0

    if prof_max > 0:
        esp_y = (hauteur - 2*marge) / prof_max
    else:
        esp_y = 0

    positions = {}
    for i, (noeud, niv) in enumerate(infos):
        x = -largeur/2 + marge + i*esp_x
        y = hauteur/2 - marge - niv*esp_y
        positions[id(noeud)] = (x, y, noeud[0])

    return positions, esp_x, esp_y

############################################################
# Dessin
############################################################

def dessiner_noeud(x, y, r, val):
    turtle.penup()
    turtle.goto(x, y-r)
    turtle.pendown()
    turtle.color("black")
    turtle.circle(r)
    turtle.penup()
    turtle.goto(x, y-r/2)
    turtle.color("red")
    turtle.write(str(val), align="center", font=("Arial", int(r), "normal"))
    turtle.color("black")

def dessiner_arete(x1, y1, x2, y2):
    turtle.penup()
    turtle.goto(x1, y1)
    turtle.pendown()
    turtle.goto(x2, y2)

############################################################
# Redessin complet
############################################################

def dessiner_arbre(a):
    global positions, rayon, arbre

    turtle.clear()

    positions, esp_x, esp_y = calcul_positions(a)

    rayon = min(25, esp_x/3, esp_y/3)
    rayon = max(rayon, 12)

    def rec(noeud):
        if noeud is None:
            return
        x, y, val = positions[id(noeud)]

        if noeud[1] is not None:
            xg, yg, _ = positions[id(noeud[1])]
            dessiner_arete(x, y-rayon, xg, yg+rayon)
            rec(noeud[1])

        if noeud[2] is not None:
            xd, yd, _ = positions[id(noeud[2])]
            dessiner_arete(x, y-rayon, xd, yd+rayon)
            rec(noeud[2])

    rec(a)

    for k in positions:
        x, y, val = positions[k]
        dessiner_noeud(x, y, rayon, val)

    turtle.title("Arbre de taille " + str(taille_arbre(arbre)))
    print("Arbre mis à jour :", arbre)

############################################################
# Interaction
############################################################

selected = None
arbre = (1, (2,None,None), (3,None,None))
next_value = 4

def trouver_noeud(x, y):
    for k in positions:
        nx, ny, val = positions[k]
        if abs(x - nx) <= rayon and abs(y - ny) <= rayon:
            return k
    return None

def chercher(a, target_id):
    if a is None:
        return None
    if id(a) == target_id:
        return a
    g = chercher(a[1], target_id)
    if g is not None:
        return g
    return chercher(a[2], target_id)

############################################################
# Suppression d'une feuille
############################################################

def supprimer_feuille(a, target_id):
    if a is None:
        return None
    if id(a) == target_id:
        return None
    return (a[0],
            supprimer_feuille(a[1], target_id),
            supprimer_feuille(a[2], target_id))

############################################################
# Remplacement du tuple dans l'arbre
############################################################

def noeud_global_replace(a, target_id, new_tuple):
    if a is None:
        return None
    if id(a) == target_id:
        return new_tuple
    return (a[0],
            noeud_global_replace(a[1], target_id, new_tuple),
            noeud_global_replace(a[2], target_id, new_tuple))

############################################################
# Gestion clic gauche (ajout)
############################################################

def clic_gauche(event):
    global selected, arbre, next_value

    x = event.x - 400
    y = 400 - event.y

    noeud_id = trouver_noeud(x, y)

    if noeud_id is not None:
        selected = noeud_id
        return

    if selected is None:
        return

    sx, sy, sval = positions[selected]
    cote = "gauche" if x < sx else "droite"

    noeud = chercher(arbre, selected)

    if cote == "gauche":
        if noeud[1] is not None:
            print("Fils gauche déjà existant")
            selected = None
            return
        val = next_value
        next_value += 1
        noeud = (noeud[0], (val, None, None), noeud[2])
        arbre = noeud_global_replace(arbre, selected, noeud)

    else:
        if noeud[2] is not None:
            print("Fils droit déjà existant")
            selected = None
            return
        val = next_value
        next_value += 1
        noeud = (noeud[0], noeud[1], (val, None, None))
        arbre = noeud_global_replace(arbre, selected, noeud)

    selected = None
    dessiner_arbre(arbre)

############################################################
# Gestion clic droit (suppression)
############################################################

def clic_droit(event):
    global arbre

    x = event.x - 400
    y = 400 - event.y

    noeud_id = trouver_noeud(x, y)
    if noeud_id is None:
        return

    noeud = chercher(arbre, noeud_id)

    if noeud[1] is None and noeud[2] is None:
        arbre = supprimer_feuille(arbre, noeud_id)
        print("Feuille supprimée")
        dessiner_arbre(arbre)
    else:
        print("Ce noeud n'est pas une feuille")

############################################################
# Lancement
############################################################

print("Pour ajouter une feuille à l'arbre binaire cliquez GAUCHE sur un noeud qui ne possédant pas encore 2 fils, puis cliquez GAUCHE à sa gauche ou à sa doite.")
print("Pour supprimer une feuille à l'arbre binaire cliquez DROIT sur une feuille.")
print("La valeur de la nouvelle feuille est auto-incrémentée à chaque ajout d'un noeud")
print("La mise à jour de l'arbre s'affiche alors dans la console sous forme d'un tuple de tuple")
print("La taille de l'arbre est affichée en temps réel dans la barre de titre\n")

turtle.setup(800,800,400,0)
turtle.speed(0)
turtle.hideturtle()
turtle.tracer(0)

dessiner_arbre(arbre)

turtle.listen()  # indispensable en Python 3.2.5

canvas = turtle.getcanvas()
canvas.bind("<Button-1>", clic_gauche)
canvas.bind("<Button-3>", clic_droit)

turtle.done()