Source : Scratch Wiki en français
Structure de donnée « arbre binaire »
Un arbre binaire est une structure de données concrète, associé au type abstrait éponyme.
SD concrète
- nom
- arbre binaire
- nom anglais
- binary tree
- type
- séquentielle, graphe
Structure de données concrète.
Informations supplémentaires
Utile pour la création de structures avancées, ou l'optimisation d'algorithmes.
Définition
Un arbre binaire est un graphe connexe et acyclique, dont les nœuds sont ordonnés hiérarchiquement.
La structure de données peut être définie par induction structurelle de plusieurs manières :
- un arbre binaire est soit :
- un nœud possédant une étiquette typée ainsi que deux sous-arbres gauche et droit ;
- un élément vide (ou sentinelle, généralement noté ⊥) ;
- un arbre binaire est soit :
Implémentation
Voici un tutoriel expliquant comment implémenter un arbre binaire en Scratch.
Implémentation naïve
L'implémentation suivante est rudimentaire et adaptée aux usages simples de la structure de données concrète.
Voir aussi
- Arbre binaire sur Wikipédia ;
- Type abstrait éponyme sur Wikipédia ;
- Structure de données et type abstrait ;
- Langage Scratch
- Tutoriels
