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

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

import turtle

############################################################
# 1. Taille de l'arbre
############################################################
def taille_arbre(arbre):
    if arbre is None:
        return 0
    return 1 + taille_arbre(arbre[1]) + taille_arbre(arbre[2])

############################################################
# 2. Profondeur de l'arbre
############################################################
def profondeur(arbre):
    if arbre is None:
        return 0
    return 1 + max(profondeur(arbre[1]), profondeur(arbre[2]))

############################################################
# 3. Largeur du sous-arbre (nombre de feuilles)
############################################################
def largeur(arbre):
    if arbre is None:
        return 1
    return largeur(arbre[1]) + largeur(arbre[2])

############################################################
# 4. Placement des nœuds
############################################################
def placer_noeuds(arbre, x, y, dx, dy, positions):
    if arbre is None:
        return

    positions[id(arbre)] = (x, y, arbre[0])

    # fils gauche
    if arbre[1] is not None:
        placer_noeuds(arbre[1], x - dx, y - dy, dx/2, dy, positions)

    # fils droit
    if arbre[2] is not None:
        placer_noeuds(arbre[2], x + dx, y - dy, dx/2, dy, positions)

############################################################
# 5. Dessin des nœuds
############################################################
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)
    turtle.color("red")
    turtle.write(str(valeur), align="center", font=("Arial", int(r/1.5), "normal"))
    turtle.color("black")

############################################################
# 6. Dessin des arêtes
############################################################
def dessiner_arete(x1, y1, x2, y2):
    turtle.penup()
    turtle.goto(x1, y1)
    turtle.pendown()
    turtle.goto(x2, y2)

############################################################
# 7. Dessin complet
############################################################
def dessiner_arbre(arbre):
    if arbre is None:
        print("Arbre vide")
        return

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

    # Fenêtre en haut à gauche
    turtle.setup(800, 800, 0, 0)
    turtle.title("Arbre binaire de taille " + str(n))
    turtle.speed(0)
    turtle.hideturtle()

    # Espacement dynamique
    dx_initial = 300.0 / larg * 2.0
    dy = 600.0 / prof

    # Taille des cercles
    r = max(10, int(40.0 / prof))

    # Placement des nœuds
    positions = {}
    placer_noeuds(arbre, 0, 350, dx_initial, dy, positions)

    # Dessin des arêtes
    def rec(arbre):
        if arbre is None:
            return
        x, y, val = positions[id(arbre)]

        if arbre[1] is not None:
            x2, y2, _ = positions[id(arbre[1])]
            dessiner_arete(x, y - r, x2, y2 + r)
            rec(arbre[1])

        if arbre[2] is not None:
            x2, y2, _ = positions[id(arbre[2])]
            dessiner_arete(x, y - r, x2, y2 + r)
            rec(arbre[2])

    rec(arbre)

    # Dessin des nœuds
    for noeud in positions:
        x, y, val = positions[noeud]
        dessiner_noeud(x, y, r, val)

    turtle.done()

############################################################
# 8. Arbre de l'énoncé
############################################################
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)
                    )
                )
            )
        )
    )
)

############################################################
# 9. Affichage
############################################################
dessiner_arbre(arbre)