Arbres et Arbres binaires
Un arbre est un graphe non orienté, connexe, et sans cycle. Un arbre binaire est lui généralement défini comme un graphe orienté, connexe, et sans cycle. Comme évoqué en cours, on omet néanmoins généralement le fait qu’il soit orienté dans les représentations pour ne pas les alourdir.
Dans la plupart des applications, on distingue un nœud particulier qu’on appelle
la racine : on dessine alors l’arbre avec la racine en haut . Une restriction consiste alors à considérer des arbres binaires,en voici une définition:
Un arbre binaire est :
– soit l’arbre vide, qu’on note souvent nil (et qu’on ne représente généralement pas dans les dessins)
– soit une racine ayant un fils gauche et un fils droit, qui sont tous deux des arbres binaires.
Un arbre binaire est donc défini de façon récursive.
- Le cours en pdf: définitions. Attention: certains éléments sont utiles à la compréhension du chapitre, par exemple: pourquoi équilibrer un arbre, mais sont hors programme NSI, vérifiez avec le support du programme inséré en en tête. (Arbres complets, parfaits etc.)
- Parcourir un arbre: parcours en largeur, profondeur: préfixe, infixe, postfixe.
- Le notebook Jupyter associé: activité et éléments cours. Vous aurez besoin d’importer la classe BinaryTree.