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.
|
1 2 3 4 5 6 7 8 |
let rec long_max a = match a with | Vide -> [], 0 | Noeud(g, e, d) -> let (bg, lg) = long_max g and (bd, ld) = long_max d in if lg > ld then (e :: bg, lg + 1) else (e :: bd, ld + 1);; val long_max : 'a arbre -> 'a list * int = <fun> |
|
1 2 3 4 5 6 7 8 |
let rec poids_max a = match a with | Vide -> [], 0 | Noeud(g, e, d) -> let (bg, pg) = poids_max g and (bd, pd) = poids_max d in if pg > pd then (e :: bg, e + pg) else (e :: bd, e + pd);; val poids_max: int arbre -> int list * int = <fun> |
Voici ce que donnent ces deux fonctions sur l’arbre cité en exemple au début de cette section :
|
1 2 |
long_max exemple;; - : int list * int = ([5; 10; 7; 9; 8], 5) |
|
1 2 |
poids_max exemple;; - : int list * int = ([5; 10; 12; 15], 42) |
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) :
|
1 2 3 4 5 6 |
let zigzag a = let rec aux dir = function | Vide -> [] | Noeud(g, e, d) -> e :: aux (not dir) (if dir then g else d) in (aux true a, aux false a);; val zigzag: 'a arbre -> 'a list * 'a list = <fun> |
Voici ce que donne cette fonction sur l’arbre cité en exemple au début de cette section :
|
1 2 |
zigzag exemple;; - : int list * int list = ([5; 3], [5; 10; 7; 9; 8]) |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres