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

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

import turtle

############################################################
# Représentation : (valeur, gauche, droite) ou None
############################################################

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

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

############################################################
# Parcours pour calculer positions logiques (ordre horizontal)
############################################################

def parcours_infixe(arbre, niveau, infos):
    if arbre is None:
        return
    # gauche
    parcours_infixe(arbre[1], niveau + 1, infos)
    # nœud courant
    infos.append((arbre, niveau))
    # droite
    parcours_infixe(arbre[2], niveau + 1, infos)

############################################################
# Calcul des positions en pixels dans 800x800
############################################################

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

    # nombre de nœuds et profondeur max
    n = len(infos)
    prof_max = max(niv for (_, niv) in infos)

    # fenêtre : -400..400 en X et Y, on garde des marges
    largeur = 800.0
    hauteur = 800.0
    marge = 60.0

    if n > 1:
        esp_x = (largeur - 2.0 * marge) / (n - 1)
    else:
        esp_x = 0.0

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

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

    return positions, esp_x, esp_y, prof_max

############################################################
# Dessin des nœuds et arêtes
############################################################

def dessiner_noeud(x, y, r, valeur):
    turtle.penup()
    turtle.goto(x, y - r)
    turtle.pendown()
    turtle.color("black")
    turtle.circle(r)

    turtle.penup()
    turtle.goto(x, y - r / 2.0)
    turtle.color("red")
    turtle.write(str(valeur), 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)

def dessiner_arbre(arbre):
    if arbre is None:
        print("Arbre vide")
        return

    n = taille_arbre(arbre)
    prof = profondeur(arbre)

    turtle.setup(800, 800, 0, 0)
    turtle.title("Arbre binaire de taille " + str(n))
    turtle.speed(0)
    turtle.hideturtle()

    positions, esp_x, esp_y, prof_max = calcul_positions(arbre)

    # rayon adapté à l’espacement
    r = 20.0
    if esp_x > 0:
        r = min(r, esp_x / 3.0)
    if esp_y > 0:
        r = min(r, esp_y / 3.0)
    r = max(8.0, r)

    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 - r, xg, yg + r)
            rec(noeud[1])

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

    rec(arbre)

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

    turtle.done()

############################################################
# Exemples d'arbres binaires
############################################################

arbre = (1, (2, None, None), (3, None, None))
#arbre = (1, (2, None, (4,None,None)), (3, (5,None,None), (6,None,None)))
#arbre = (2,(1,(0,None,None),None),(5,(4,(3,None,None),None),(12,(9,(8,(6,None,(7,None,None)),None),(10,None,(11,None,None))),(13,None,(14,None,(18,(17,(15,None,(16,None,None)),None),(19,None,None)))))))

dessiner_arbre(arbre)