Thème 1

Arbres

Coupe du monde

Résultat

Huitièmes de finale

Etats-Unis - Pays-Bas
Argentine - Australie
France - Pologne
Angleterre - Sénégal
Croatie - Japon
Brésil - Corée du Sud
Espagne - Maroc
Portugal - Suisse

Quarts de finale

Brésil - Croatie
Argentine - Pays-Bas
Maroc - Portugale
Angleterre - France

Demi-finales

Argentine - Croatie
France - Maroc

Finales

Argentine - France


<html>
    <head>
        <link href="/static/css/style.css" rel="stylesheet">
        <titre>Activité</titre>
    </head>
    <body>
        <h1>Les arbres</h1>
        <div>
            Lorem ipsum dolor sit amet, consectetur adipiscing elit.
            <ul>
                <li> Nulla dignissim magna et velit condimentum vulputate.</li>
                <li> Donec non dictum diam, porttitor condimentum augue.</li>
                <li> Vestibulum vel vulputate libero, ac tincidunt massa.</li>
            </ul>
        </div>  
        <footer>
            Duis dictum felis nec ipsum dictum, sit amet gravida diam ullamcorper.
        </footer>
    </body>
</html>

Les Arbres

Thème 3 - Partie A

Définitions

&

1ères Propriétés

Définition

Un arbre est une structure de donnée constituée de nœuds.

Le sommet de l'arbre s'appelle la racine.
Le nœud B situé sous un nœud A est appelé enfant du nœud A
Un nœud qui ne possède pas d'enfant est appelé feuille.

exercice

Déterminer la racine de cet arbre ?
Déterminer les feuilles de cet arbre ?

Métriques sur les arbres

Taille et hauteur

On définit la taille d'un arbre comme le nombre de nœuds qui le composent.
On définit la hauteur d'un arbre comme le plus grand nombre de nœuds qui constituent la branche contenant le plus de nœuds sans compter la racine.

exercice

Déterminer la taille de cet arbre ?
Déterminer la hauteur de cet arbre ?

Arbre binaire

En informatique, un arbre binaire est un arbre dont chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit.

exercice

Implémentation


class Noeud:

    def __init__(self, valeur, gauche, droit):
        self.valeur = valeur
        self.gauche = gauche
        self.droit  = droit

exercice


A = Noeud(   ,    ,   )

exercice


A = Noeud(11 ,
        Noeud(15, Noeud(29, None, None), Noeud(23, None, None)),

        )

exercice


A = Noeud(11 ,
        Noeud(15, Noeud(29, None, None), Noeud(23, None, None)),
        Noeud(12, None, Noeud(21, None, None))
        )

Taille

Implemente la fonction taille qui prend en parametre arb un arbre binaire implémenter à l'aide de la classe Noeud et qui renvoie la taille de cet arbre.

La taille d’un arbre binaire vide valent 0.

La taille d’un arbre binaire non vide vaut
La taille d’un arbre binaire non vide vaut
1 + taille(sous-arbre gauche) + taille(sous-arbre droit)

Hauteur

Implemente la fonction hauteur qui prend en parametre arb un arbre binaire implémenter à l'aide de la classe Noeud et qui renvoie la heuteur de cet arbre

La taille d’un arbre binaire vide valent 0.

La taille d’un arbre binaire non vide vaut
La taille d’un arbre binaire non vide vaut 1 + taille(sous-arbre gauche) + taille(sous-arbre droit)

Parcours sur les arbres

Parcours en profondeur

On peut aussi définir ces 3 modes de parcours de cette façon.

Préfixe : on lit d'abord la Racine (RGD) puis le sous arbre Gauche et ensuite le sous-arbre Droit
Suffixe ou postfixe : on lit la Racine à la fin (GDR)
Infixe : on lit la Racine au milieu de la séquence (GRD), infixe comme intérieur.