Qu'est-ce qu'un arbre binaire en NSI et pourquoi est-ce important
Les arbres binaires sont une structure de données fondamentale en terminale NSI. Un arbre binaire est composé de nœuds, chacun ayant au maximum deux fils (gauche et droit). Le nœud supérieur est la racine. Les nœuds sans fils sont des feuilles. La taille est le nombre total de nœuds, la hauteur est la distance maximale entre la racine et une feuille. Un arbre binaire de recherche (ABR) est un arbre où, pour chaque nœud, tous les éléments du sous-arbre gauche sont inférieurs et tous ceux du sous-arbre droit sont supérieurs. Cette propriété permet une recherche efficace en O(log n) dans le cas équilibré. Les parcours d'arbres sont incontournables au bac : le parcours préfixe (racine, gauche, droite), infixe (gauche, racine, droite) et suffixe (gauche, droite, racine) sont des parcours en profondeur. Le parcours en largeur utilise une file. En Python, un arbre se représente généralement avec une classe Noeud possédant trois attributs : valeur, gauche et droit. Sur NSI-Lycée, les arbres sont expliqués avec des visualisations interactives et des exercices progressifs. Consultez revisemaths.fr pour la récursivité mathématique sous-jacente, et alloexercices.fr pour des exercices supplémentaires.
