ColabTurtleArbreBinaire 0.0.4

A module using ColabTurtlePlus to draw binary trees

ColabTurtleArbreBinaire

Ce module permet de représenter un arbre binaire et de visualiser son parcours à l'aide du module ColabTurtlePlus (un module dérivé du module turtle pour les notebooks Google Colab et Jupyter).

Dans ce module, un arbre binaire est représenté en Python à l'aide d'une liste de la façon suivante :

• [] représente l'arbre vide.
• [v, sag, sad] représente un arbre non vide avec :
  • v la valeur de sa racine ;
  • sag son sous-arbre de gauche ;
  • sad son sous-arbre de droite.

Ce module est destiné à l'enseignement de l'informatique. Il a pour but de fournir un support graphique pour accompagner les élèves dans l'apprentissage des algorithmes classiques sur les arbres binaires (de recherche). Il ne fournit pas cependant ces algorithmes qui seront abordés en classe avec le professeur.

Installation

Il faut préalablement installer le module en exécutant la commande shell suivante dans une cellule :

!pip install ColabTurtleArbreBinaire

Utilisation

Pour importer le module, exécuter le code suivant dans une autre cellule :

from ColabTurtleArbreBinaire import *

Exemples

Les exemples donnés ci-après peuvent être directement testés dans ce cahier Google Colab.

Exécutez la cellule suivante pour stocker en mémoire l'arbre binaire abr0 qui sera utilisé dans les exemples qui suivent.

abr0 = [
    30,
        [9,
            [7,
                [5, [], []],
                [6, [], []]
            ],
            [13,
                [10, [], []],
                []
            ]
        ],
        [42,
            [31, [], []],
            [54, [], []]
        ]
]

Les abres ayant pour valeur des chaînes de caractères sont aussi pris en charge :

abr1 = [
    'G',
        ['D',
            ['C',
                ['A', [], []],
                ['B', [], []]
            ],
            ['F',
                ['E', [], []],
                []
            ]
        ],
        ['I',
            ['H', [], []],
            ['J', [], []]
        ]
]

abr2 = [
    'Albatros',
        ['Baleine',
            ['Cachalot',
                ['Dauphin', [], []],
                ['Éléphant', [], []]
            ],
            ['Faucon',
                ['Gazelle', [], []],
                []
            ]
        ],
        ['Héron',
            ['Iguane', [], []],
            ['Jaguar', [], []]
        ]
]

Affichage d'un arbre

dessiner(abr0) # avec les arbres vides

dessiner(abr0, dessiner_vide=False) # sans les arbres vides

Animation du parcours d'un arbre

dessiner_parcours(abr0, dessiner_vide=False, parcours='largeur')

Remarque. 'largeur' peut être remplacé par 'infixe', 'préfixe', 'suffixe' ou 'postfixe'.

Animation de la recherche d'une valeur dans un arbre

dessiner_recherche(abr0, 13, dessiner_vide=False, parcours='largeur')

Remarque. 'largeur' peut être remplacé par 'infixe', 'préfixe', 'suffixe' ou 'postfixe'.

Animation de l'insertion d'une valeur dans un arbre binaire de recherche

dessiner_insertion(abr0, 34)

Remarque. L'animation montre simplement où le noeud sera ajouté sans modifier l'arbre passé en paramètre.