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

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

import turtle

############################################################
# 1. Calcul de la taille de l'arbre (nombre de nœuds)
############################################################
def taille_arbre(arbre):
    if arbre is None:
        return 0
    return 1 + taille_arbre(arbre[1]) + taille_arbre(arbre[2])

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

############################################################
# 3. Placement des nœuds : calcul des positions (x,y)
############################################################
def placer_noeuds(arbre, x, y, dx, dy, positions):
    """
    arbre : tuple représentant le nœud
    x,y : position du nœud
    dx : espacement horizontal
    dy : espacement vertical
    positions : dictionnaire {id(arbre): (x,y,valeur)}
    """
    if arbre is None:
        return

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

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

############################################################
# 4. Dessin d’un cercle représentant un nœud
############################################################
def dessiner_noeud(x, y, r, valeur):
    turtle.penup()
    turtle.goto(x, y - r)
    turtle.pendown()
    turtle.color("black")
    turtle.circle(r)

    # écrire la valeur en rouge
    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")

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

############################################################
# 6. Dessin complet de l’arbre
############################################################
def dessiner_arbre(arbre):
    if arbre is None:
        print("Arbre vide")
        return

    # calculs préliminaires
    n = taille_arbre(arbre)
    prof = profondeur(arbre)

    # configuration fenêtre
    turtle.setup(800, 800,0,0)
    turtle.title("Arbre binaire de taille " + str(n))
    turtle.speed(0)
    turtle.hideturtle()

    # calcul des positions
    positions = {}
    dx_initial = 200.0  # espacement horizontal initial
    dy = 80.0           # espacement vertical entre niveaux

    placer_noeuds(arbre, 0, 300, dx_initial, dy, positions)

    # rayon des cercles dépendant de la profondeur
    r = max(15, int(50.0 / prof))

    # dessiner les arêtes
    for noeud in positions:
        x, y, val = positions[noeud]
        # retrouver les fils
        for fils in (0, 1):  # gauche = 1, droit = 2 dans le tuple
            # fils gauche = arbre[1], fils droit = arbre[2]
            pass

    # dessiner les arêtes correctement
    def dessiner_rec(arbre):
        if arbre is None:
            return
        x, y, val = positions[id(arbre)]
        # fils gauche
        if arbre[1] is not None:
            x2, y2, _ = positions[id(arbre[1])]
            dessiner_arete(x, y - r, x2, y2 + r)
            dessiner_rec(arbre[1])
        # fils droit
        if arbre[2] is not None:
            x2, y2, _ = positions[id(arbre[2])]
            dessiner_arete(x, y - r, x2, y2 + r)
            dessiner_rec(arbre[2])

    dessiner_rec(arbre)

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

    turtle.done()

############################################################
# 7. Exemple d’arbre fourni dans 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)
                    )
                )
            )
        )
    )
)

############################################################
# 8. Lancer l’affichage
############################################################
dessiner_arbre(arbre)