Numérique et sciences informatiques (spécialité) · Terminale · Algorithmique

Algorithmes sur les arbres binaires

• Un arbre binaire est vide, ou formé d'une racine avec un fils gauche et un fils droit, eux-mêmes des arbres binaires : presque tous les algorithmes s'écrivent donc par récursivité, avec le cas vide comme cas de base.
• Taille = nombre de nœuds ; hauteur = longueur du plus long chemin de la racine à un nœud (un arbre réduit à sa racine est de hauteur 0, l'arbre vide de hauteur −1 par convention).
• Parcours en profondeur : préfixe (racine, gauche, droit), infixe (gauche, racine, droit), suffixe (gauche, droit, racine) ; seul l'ordre des trois étapes change.
• Parcours en largeur : niveau par niveau, de gauche à droite, avec une file ; ce n'est pas une récursion.