This page was exported from Enseignement de l'informatique et du numérique au lycée Boissy d'Anglas [ https://icn-isn-boissy.yj.fr/wp ]

Export date:Thu May 16 18:19:18 2024 / +0000 GMT

___________________________________________________


Title: Corrigé exercice 2 les arbres

---------------------------------------------------



1.a. Il y a 4 feuilles, d'étiquette 12, val, 21 et 32.1.b. Le sous-arbre gauche du nœud 23 est 19-21.1.c. La hauteur de l'arbre est 4. Sa taille est 9.1.d. Les valeurs possibles de val sont 16 et 17.



2.a. Parcours infixe : 12-13-15-16-18-19-21-23-322.b. Parcours suffixe : 12-13-16-15-21-19-32-23-18



3.a. 







3.b.



racine = Noeud(18)
racine.insere([15, 13, 12, 16, 23, 32, 19, 21])




(d'autres solutions sont possibles)



3.c. bloc 3 – bloc 2ne rentre pas dans bloc 1



4.



class Noeud():
    def __init__(self, v):
        self.ag = None
        self.ad = None
        self.v = v

    def insere(self, v):
        n = self
        est_insere = False
        while not est_insere:
            if v == n.v:
                est_insere = True
            elif v < n.v:
                if n.ag != None:
                    n = n.ag
                else:
                    n.ag = Noeud(v)
                    est_insere = True
            else:
                if n.ad != None:
                    n = n.ad
                else:
                    n.ad = Noeud(v)
                    est_insere = True

    def insere_tout(self, vals):
        for v in vals:
            self.insere(v)

    def recherche(self, v):
        arbre = self
        while not arbre is None:
            if arbre.v == v:
                return True
            if v < arbre.v:
                arbre = arbre.ag
            else:
                arbre = arbre.ad
        return False


    # version récursive (non demandée)

    def recherche_rec(self, v):
        if self is None:
            return False
        if self.v == v:
            return True
        if v < self.v:
            if self.ag is not None:
                return self.ag.recherche_rec(v)
            else:
                return False
        else:
            if self.ad is not None:
                return self.ad.recherche_rec(v)
            else:
                return False


racine = Noeud(18)
racine.insere_tout([12, 13, 15, 14, 19, 21, 32, 23])
print(racine.recherche(149))
print(racine.recherche(12))


---------------------------------------------------


Images: https://icn-isn-boissy.yj.fr/wp/wp-content/uploads/2022/10/image.png



---------------------------------------------------




---------------------------------------------------


Post date: 2022-10-14 08:46:31

Post date GMT: 2022-10-14 06:46:31

Post modified date: 2022-10-14 09:19:42

Post modified date GMT: 2022-10-14 07:19:42



____________________________________________________________________________________________


Export of Post and Page as text file has been powered by [ Universal Post Manager ] plugin from www.gconverters.com