leçon arbres binaires nsi terminale

« Arbres binaires 1 Les arbres 1.1 Introduction • Les listes, piles et files vues précédemment sont des structures de données linéaires. Malheureusement, ces structures ne sont plus adaptées dès que l’on souhaite décrire l’ensemble des fichiers d’un ordinateur ou bien tout ou partie des espèces vivantes sur Terre. • Nous allons donc décrire les arbres qui sont des structures de données hiérarchiques et qui vont permettre des recherches rapides dans de vastes ensembles. 1.2 Définitions • Un arbre est une structure de données constituée de nœuds, qui peuvent avoir ou non des enfants. ◦ Dans un système de fichiers, chaque nœud mémorise l’adresse sur le disque (pour un dossier comme pour un fichier), ainsi que les attributs (nom, poids, date, droits rwx ...) ◦ Le sommet de l’arbre est appelé racine (Website dans l’exemple ci-contre). ◦ Les enfants sont soit d’autres nœuds, soit des feuilles (Application2, PageA.htm, Picture1.gif ...) • Une branche est une suite finie de nœuds consécutifs de la racine vers une feuille (Website – Application1 – PageA.htm). S08 Arbres binaires Terminale NSI – BNS – Lycée Victor Duruy 1 / 10 • Un arbre peut être caractérisé par : ◦ Sa taille : le nombre de nœuds qui le compose. ◦ Son arité : le nombre maximal d’enfants qu’un nœud peut avoir. 2 Les arbres binaires 2.1 Définitions • Les arbres binaires sont constitués de nœuds ayant 0, 1 ou 2 enfants, soit une arité égale à 2. • Pour chaque nœud (donc autre qu’une feuille), on définit les enfants comme deux sous-arbres : le sous-arbre gauche (SAG), et le sous-arbre droit (SAD). ◦ L’arbre ci-contre représente l’opération arithmétique (a*b) + (c – (d+e)). ◦ SAG (*) = a, SAD(*) = b ◦ SAG(-) = c, SAD(-) = (+,d,e) 2.2 Cas particuliers • Un arbre est qualifié de dégénéré ou filiforme, lorsque ses nœuds ne possèdent aucun ou qu’un seul enfant. • Un arbre binaire est localement complet lorsque ses nœuds possèdent soit deux enfants, soit aucun. • Un arbre binaire est complet lorsque : R R R ◦ il est localement complet ; ◦ toutes ses feuilles sont au niveau hiérarchique le plus bas. S08 Arbres binaires Terminale NSI – BNS – Lycée Victor Duruy 2 / 10 2.3 Hauteur • On définit la hauteur d’un arbre comme le plus grand nombre de nœuds rencontrés en descendant de la racine jusqu’à une feuille.

Le long de cette descente, tous les nœuds sont comptés, y compris la racine et la feuille. Hauteur 1 R ◦ L’arbre ci-contre a une hauteur égale à 4. 2 ◦ Un arbre vide a pour hauteur 0. 3 4 • Si N désigne la taille d’un arbre (son nombre de nœuds), et si h désigne sa hauteur, on a alors : h h ⩽ N ⩽ 2 −1 ◦ L’inégalité de gauche vient du fait qu’un arbre de hauteur h possède au moins h nœuds (cas de l’arbre dégénéré, § Cas particuliers). ◦ L’inégalité de droite correspond au cas de l’arbre complet ci-contre.

Compléter la dernière ligne du tableau : h 1 2 3 4 2h 2 4 8 16 N • La hauteur est une notion importante : elle entre en ligne de compte lorsque la complexité des algorithmes dépend directement de la hauteur des arbres. S08 Arbres binaires Terminale NSI – BNS – Lycée Victor Duruy 3 / 10 3 Implémentation objet 3.1 La classe « Noeud » • Chaque nœud d’un arbre ressemble à la cellule d’une liste chaînée : en plus de l’information à mémoriser (nom du fichier, opérateur arithmétique …), on y stockera deux adresses au lieu d’une. Noeud valeur @ SAG class Noeud : def __init__(self, valeur, sag, sad) : self.valeur = valeur self.sag = sag self.sad = sad • @ SAD Remarques : ◦ Pour alléger l’écriture, nous ne protégeons par les trois attributs d’un nœud ; nous y accèderons donc par la syntaxe nœud.valeur, nœud.sag … ◦ L’implémentation objet ci-dessus paraît naturelle, mais il faut insister ici sur le fait que chaque sousarbre ne désigne en fait que d’autres nœuds, donc des objets de type Noeud. • Exercices : ◦ A partir de la classe Noeud, déclarer le premier arbre ci-contre et le stocker dans la variable arbre1.

Toutes les valeurs seront stockées sous forme de chaînes de caractères.

On rappelle que pour une feuille, les adresses sad et sag sont initialisées à None. ◦ Déclarer le second arbre ci-contre et le stocker dans la variable arbre2. Toutes les valeurs seront stockées sous forme de chaînes de caractères. 7 5 véhicule 2 roues vélo S08 Arbres binaires + Terminale NSI – BNS – Lycée Victor Duruy 4 roues moto auto 4 / 10 4 Mesures sur les arbres binaires 4.1 Taille d’un arbre binaire • La taille d’un arbre A correspond au nombre de ses nœuds.

Son calcul se fera de manière récursive selon la formule : T ( A)= 0 si A est vide 1+ T SAG( A) +T SAD (A ) • Nous définissons la fonction taille() en dehors de la classe Noeud : ( def taille(noeud) : if noeud is None : return 0 else : return 1 + taille(noeud.sag) + taille(noeud.sad) • Remarque : ◦ Le choix des noms de variables est ici capital.

Nous voulons bien calculer la taille de l’arbre complet, mais j’ai essayé d’éviter toute confusion en n’adoptant pas la notation suivante : def taille(arbre) : if noeud is None : return 0 else : return 1 + taille(noeud.sag) + taille(noeud.sad) ◦ Appeler cette fonction en lui fournissant l’adresse de la racine et non celle d’un nœud quelconque revient à calculer la taille de l’arbre complet. • Tester cette fonction sur les objets arbre1 et arbre2 de l’exercice précédent. 4.2 Hauteur • Définitions : ◦ Soit p le nœud parent d’un nœud n.

La hauteur ou profondeur d’un nœud n est définie par : H (n)= 0 sin est laracine 1+ H ( p) ( ◦ La hauteur ou profondeur d’un arbre A est la valeur maximale des hauteurs de tous les nœuds n : H ( A)=max (H (n)) • La fonction max() est intégrée dans Python.

Effectuer les tests suivants en console : >>> max(5, -2) >>> max(5, -2, 7.4) S08 Arbres binaires Terminale NSI – BNS – Lycée Victor Duruy 5 / 10 • Algorithme récursif : def hauteur(noeud) : """ Renvoie la hauteur d’un arbre dont on fournit la racine""" if noeud is None : return 0 else : return 1 + max(hauteur(noeud.sag), hauteur(noeud.sad)) • Exemple : ◦ Le seul moyen de connaître la hauteur d’un arbre est d’effectuer tous les chemins possibles, de la racine jusqu’aux feuilles. ◦ Parmi tous les chemins possibles, seul.... »