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

############################################################
# Tracé d'un arbre binaire avec le module Turtle de Python
# Version 4
# 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   # marge large pour expansion future

    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

    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)

    print("Arbre mis à jour :", arbre)

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

selected = None
arbre = (1, (2,None,None), (3,None,None))  # arbre initial

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 on_click(x, y):
    global selected, arbre

    noeud_id = trouver_noeud(x, y)

    if noeud_id is not None:
        selected = noeud_id
        return

    if selected is None:
        return

    # déterminer gauche ou droite
    sx, sy, sval = positions[selected]
    cote = "gauche" if x < sx else "droite"

    # retrouver le tuple du noeud sélectionné
    def chercher(a):
        if a is None:
            return None
        if id(a) == selected:
            return a
        g = chercher(a[1])
        if g is not None:
            return g
        return chercher(a[2])

    noeud = chercher(arbre)

    if cote == "gauche":
        if noeud[1] is not None:
            print("Noeud fils déjà existant")
        else:
            val = turtle.numinput("Nouveau noeud", "Valeur du fils gauche :", 0)
            noeud = (noeud[0], (int(val), None, None), noeud[2])
            arbre = noeud_global_replace(arbre, selected, noeud)

    else:
        if noeud[2] is not None:
            print("Noeud fils déjà existant")
        else:
            val = turtle.numinput("Nouveau noeud", "Valeur du fils droit :", 0)
            noeud = (noeud[0], noeud[1], (int(val), None, None))
            arbre = noeud_global_replace(arbre, selected, noeud)

    selected = None
    dessiner_arbre(arbre)

############################################################
# 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))

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

print("Pour ajouter une feuille à l'arbre binaire :")
print(" 1 : cliquez sur un noeud N ne possédant pas encore 2 fils")
print(" 2 : cliquez légèrement à gauche de N pour ajouter un fils gauche, ou à droite de N pour ajouter un fils droit")
print(" 3 : saisissez la valeur de la nouvelle feuille")
print(" 4 : la mise à jour de l'arbre s'affiche alors dans la console sous forme d'un tuple de tuple\n")

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

dessiner_arbre(arbre)
turtle.onscreenclick(on_click)

turtle.done()