Parcours dans un arbre binaire

10.6.1 Branches d'un arbre

Une branche d’un arbre est une liste {[a_{0};a_{1};...;a_{m}]} où {a_{0}} est la racine et où chaque {a_{k+1}} est un fils de {a_{k}(}on remplace évidemment ici les noeuds par les étiquettes correspondantes). La fonction long_max renvoie le couple formé par une branche de longueur maximum (une seule, en cas d’ex aequo) et sa longueur. Le poids d’une branche est la somme de ses étiquettes. La fonction poids_max renvoie le couple formé par une branche de poids maximum (une seule, en cas d’ex aequo) et son poids.

Voici ce que donnent ces deux fonctions sur l’arbre cité en exemple au début de cette section :

Une branche est en zigzag si elle formée par des alternances entre fils gauche et fils droite. La fonction zigzag renvoyant le couple des deux branches en zigzag d’un arbre (suivant qu’on décide de partir à gauche ou à droite à la racine) :

Voici ce que donne cette fonction sur l’arbre cité en exemple au début de cette section :

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :