(*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*) (*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*) type 'a arbre = | Vide | Noeud of 'a * 'a arbre * 'a arbre ;; (* Question 1 *) let ex = Noeud (3, Vide, Noeud (5, Vide, Vide));; (* pour les tests ulterieurs *) let arb1 = Noeud ( 1, Noeud (14, Vide, Vide), Noeud (3, Noeud (2, Vide, Vide), Noeud (5, Vide, Vide) ));; (* 1 14 3 2 5 *) (* Question 2 *) let rec nb_noeuds arbre = match arbre with | Vide -> 0 | Noeud (_, fils_gauche, fils_droit) -> 1 + (nb_noeuds fils_gauche) + (nb_noeuds fils_droit) ;; nb_noeuds ex;; nb_noeuds arb1;; (* Question 3 *) let rec nb_feuilles arbre = match arbre with | Vide -> 0 | Noeud (_, Vide, Vide) -> 1 | Noeud (_, fils_gauche, fils_droit) -> nb_feuilles fils_gauche + nb_feuilles fils_droit ;; nb_feuilles arb1;; nb_feuilles ex;; let rec nb_feuillesbis arbre = match arbre with | Vide -> 0 | Noeud (_, fils_gauche, fils_droit) -> if fils_gauche = Vide && fils_droit = Vide then 1 else nb_feuillesbis fils_gauche + nb_feuillesbis fils_droit ;; nb_feuillesbis arb1;; nb_feuillesbis ex;; (* Question 4 *) let rec somme_etiquettes arbre = match arbre with | Vide -> 0 | Noeud (etiquette, fils_gauche, fils_droit) -> etiquette + (somme_etiquettes fils_gauche) + (somme_etiquettes fils_droit) ;; somme_etiquettes ex;; somme_etiquettes arb1;; (* Question 5 *) let rec max_etiquettes arbre = match arbre with | Vide -> failwith "Arbre vide" | Noeud (etiquette, Vide, Vide) -> etiquette | Noeud (etiquette, fils_gauche, Vide) -> max etiquette (max_etiquettes fils_gauche) | Noeud (etiquette, Vide, fils_droit) -> max etiquette (max_etiquettes fils_droit) | Noeud (etiquette, fils_gauche, fils_droit) -> max etiquette (max (max_etiquettes fils_gauche) (max_etiquettes fils_droit)) ;; max_etiquettes arb1;; (* Alternative si les ̩etiquettes sont des entiers *) let rec max_etiquettes arbre = match arbre with | Vide -> min_int | Noeud (etiquette, fils_gauche, fils_droit) -> max etiquette (max (max_etiquettes fils_gauche) (max_etiquettes fils_droit)) ;; min_int;; (* - : int = -4611686018427387904 *) max_etiquettes ex;; (* Question 6 *) let rec somme_feuilles arbre = match arbre with | Vide -> 0 | Noeud (etiquette, Vide, Vide) -> etiquette | Noeud (etiquette, fils_gauche, fils_droit) -> (somme_etiquettes fils_gauche) + (somme_etiquettes fils_droit) ;; somme_feuilles arb1;; somme_feuilles ex;; (* Question 7 *) let rec parcours_prefixe arbre = match arbre with | Vide -> [] | Noeud (etiquette, fils_gauche, fils_droit) -> etiquette :: (parcours_prefixe fils_gauche) @ (parcours_prefixe fils_droit) ;; parcours_prefixe ex;; parcours_prefixe arb1;; let arb2 = Noeud ( 1, Noeud (4, Vide, Vide), Noeud (3, Noeud (2, Vide, Vide), Noeud (1, Noeud (2, Vide, Vide), Vide) ));; parcours_prefixe arb2;; (* Question 8 *) let rec max_min_etiquettes arbre = match arbre with | Vide -> failwith "Arbre vide" | Noeud (etiquette, Vide, Vide) -> (etiquette, etiquette) | Noeud (etiquette, fils_gauche, Vide) -> let maxi_g, mini_g = max_min_etiquettes fils_gauche in (max etiquette maxi_g, min etiquette mini_g) | Noeud (etiquette, Vide, fils_droit) -> let maxi_d, mini_d = max_min_etiquettes fils_droit in (max etiquette maxi_d, min etiquette mini_d) | Noeud (etiquette, fils_gauche, fils_droit) -> let maxi_g, mini_g = max_min_etiquettes fils_gauche in let maxi_d, mini_d = max_min_etiquettes fils_droit in (max etiquette (max maxi_g maxi_d), min etiquette (min mini_g mini_d)) ;; max_min_etiquettes ex;; max_min_etiquettes arb1;; max_min_etiquettes arb2;; (* Question 9 *) let rec max_somme_branche arbre = match arbre with | Vide -> 0 | Noeud (etiquette, Vide, Vide) -> etiquette | Noeud (etiquette, fils_gauche, fils_droit) -> etiquette + (max (max_somme_branche fils_gauche) (max_somme_branche fils_droit)) ;; max_somme_branche arb1;; max_somme_branche arb2;; let rec max_somme_branchebis arbre = match arbre with | Vide -> 0 | Noeud (etiquette, Vide, Vide) -> etiquette | Noeud (etiquette, fils_gauche, fils_droit) -> let maxb_g = max_somme_branche fils_gauche in let maxb_d = max_somme_branche fils_droit in if maxb_g > maxb_d then etiquette + maxb_g else etiquette + maxb_d ;; max_somme_branchebis arb1;; max_somme_branchebis arb2;; (* On peut refaire le TP avec le nouveau type, mais pas d̩finir l'exemple propos̩ qui n'est pas un arbre binaire strict. Certaines fonctions sont plus simples (e.g. min_max_etiquettes) *)