C5 : Outils pour visualiser les arbres

Dessiner un arbre implémenté à l'aide de tuples (ou de listes)

Les fonctions ci-dessous permettent de dessiner un arbre implémenté à l'aide de tuples avec None pour l'arbre vide.

Vous pouvez les utiliser dans un fichier à part et les importer.

import matplotlib.pyplot as plt

def hauteur(t):
    if t == None:
        return 0
    else:
        _, t1, t2 = t
        return max([hauteur(t1), hauteur(t2)]) + 1

def draw_tree_aux(t, rect, dy, labels):
    if t == None:
        return None
    x1, x2, y1, y2 = rect
    xm = (x1 + x2) // 2
    x, t1, t2 = t
    draw_tree_aux(t1, (x1, xm, y1, y2 - dy), dy, labels)
    draw_tree_aux(t2, (xm, x2, y1, y2 - dy), dy, labels)
    if t1 != None:
        a, b = ((xm, (x1 + xm) // 2), (y2, y2 - dy))
        plt.plot(a, b, 'k', marker='o', markersize=20, markerfacecolor='white')
    if t2 != None:
        c, d = ((xm, (x2 + xm) // 2), (y2, y2 - dy))
        plt.plot(c, d, 'k', marker='o', markersize=20, markerfacecolor='white')
    if labels:
        plt.text(xm, y2, str(x), fontsize=10,
                 horizontalalignment='center', verticalalignment='center')

def draw_tree(t, labels=True):
    d = 512
    pad = 20
    dy = (d - 2 * pad) / (hauteur(t))
    draw_tree_aux(t, (pad, d - pad, pad, d - pad), dy, labels)
    plt.axis([0, d, 0, d])
    plt.axis('off')
    plt.show()

# ==== Exemple d'utilisation ====
if __name__ == '__main__':
    arbre = (2,(5,None,None),(8,None,(3,None,None)))
    draw_tree(arbre)