Cours sur les arbres, arbres binaires
Comprendre le principe du parcours en largeur d'un arbre binaire, son implémentation itérative à l'aide d'une file, et savoir le coder en Python et en C.
Un arbre d'expression est un arbre binaire qui représente une expression arithmétique : les feuilles contiennent des nombres entiers, les nœuds internes contiennent des opérateurs : '+', '-', '*', '/'.
On souhaite implémenter une structure de données permettant de gérer un dictionnaire de contacts,où chaque contact est identifié par un entier strictement positif (par exemple un identifiant unique).
Lorsqu'on enregistre des données — qu'il s'agisse d'un texte, d'une image ou de tout autre contenu — on stocke en réalité une suite de symboles (caractères, pixels, etc.). Traditionnellement, chaque symbole est représenté par un nombre fixe de bits : par exemple, en ASCII, un caractère occupe 8 bits ..
sommes des feuilles, noeuds voisins, chemin
Somme des feuilles, arbre complet, miroir d'un arbre
Dans ce TD, nous allons implémenter des arbres binaires en Python. On choisit de représenter l'arbre vide par la liste vide, et un arbre de racine étiquetée par e et fils fg et fd par la liste [e, fg, fd]
Maîtriser les trois méthodes de parcours en profondeur d'un arbre binaire (infixe, préfixe, postfixe) et savoir les implémenter en Python (POO et listes) ainsi qu'en C.
Distinguer les différentes catégories d'arbres binaires (plein, complet, parfait, équilibré) et comprendre leurs propriétés caractéristiques ainsi que leurs applications.
Comprendre la nature récursive des structures arborescentes et maîtriser les définitions formelles des arbres enracinés, des arbres binaires étendus, des arbres binaires complets ainsi que leurs propriétés fondamentales.
Maîtriser les relations fondamentales entre le nombre de nœuds, la hauteur et le nombre de feuilles dans un arbre binaire.
Comprendre la structure hiérarchique des arbres binaires, leur terminologie, leurs applications et maîtriser leur implémentation en Python et en C.