arbre

ah-fsr-v2. O Cours Structures de données Arbres (Trees) Structures de données (2012-2013) Objectifs Etudier des structure Arbres binaires Arbres binaires de re Arbres maximiers ou Arbres équilibrés o or29 Sni* to View structures de données (2012-2013) 2 Contenu Introduction Terminologie Arbres binaires de recherche « parenté ») induisant une structure hiérarchique parmi ces nœuds. Un nœud, comme tout élément d’une liste, peut être de n’importe quel type. 4 Terminologie (1) (suite) D’une manière plus formelle, une structure d’arbre de type de base T est : oit la structure vide ; soit un noeud de type T, appelé racine, associé à un nombre fini de structures d’arbre disjointes du type de base T appelées sous arbres Cest une définition récursive ; la récursivité est une propriété des arbres et des algorithmes qui les manipulent Une liste est un cas particulier des arbres (arbre dégénéré), où tout noeud a au plus un sous arbre ah-fsr-vzo Illustration & Exemple Pour illustrer une structure d’arbre, on modélise le plus souvent un nœUd par une OF précédent, le nœud 5 a deux fils : 1 et 3, le nœud 1 a un fils : , et le nœud 3 a trois fils : 2, 6 et 7. père : Tous les nœuds d’un arbre, sauf un, ont un père et un seul. IJn nœud p est père du nœud n si et seulement si n est fils de p. Par exemple, le père de 2 est 3, celui de 3 et 5. Frères Deux nœuds ayant le même père. Les nœuds 2, 6 et 7 sont des frères.

Racine : Le seul nœud sans père. 5 est la racine de l’arbre précédent. 12 6 Terminologie (4) Feuilles (ou nœuds terminaux, ou nœuds externes) : Ce sont des noeuds sans fils. Par exemple, 4, 2, 6 et 7. Nœud interne : l_Jn noeud qui n’est pas terminal. Par exemple, 1,3 et 5. Degré d’un noeud : Le nombre de fils de ce noeud_ Sur l’exemple, 5 est de de PAGF t de deeré un, 3 est de 1,4), (5, 3, 2), (5, 3, 6) et (5, 3, 7). Ancêtre : un nœud A est un ancêtre d’un nœud B s’il existe un chemin de A vers B. par exemple, les ancêtres de 2 sont 2, 3 et 5 Descendant Un nœud A est un descendant d’un nœud B s’il existe un chemin de B vers A.

Sur l’exemple, 5 admet les 7 nœuds de l’arbre comme descendants. 14 7 Terminologie (6) Sous arbre Un sous arbre d’un arbre A est constitué de tous les descendants d’un nœud quelconque de A. Les ensembles de noeuds {3, 2, 6, 7} et {2} forment deux sous de l’exemple précédent. Hauteur (ou profondeur, ou niveau) d’un noeud : Longueur du chemin qui relie la racine à ce nœud. La racine est elle même de hauteur O, ses fils sont de hauteur 1, les autres noeuds de hauteur supérieure à 1 Hauteur d’un arbre : Plus grande profondeur d PAGF OF pg ‘arbre supposé non vide, comme de simples arbres. 17 ah-fsr-v2. o Terminologie (8) Arbre binaire : Un arbre où chaque noeud a au plus deux fils.

Quand un nœud de cet arbre a un seul fils, on précise s’il s’agit du lls gauche ou du fils droit. La figure qui suit montre un exemple d’arbre binaire dans lequel nœuds contiennent des caractères. 18 Terminologie (9) Arbre binaire complet : Arbre binaire dont chaque niveau est rempli. 19 Terminoloeie (10) PAGF s OF c-à-d composé : d’un nœud r appelé racine contenant un élément et de deux arbres binaires disjoints Al et A2, appelés respectivement sous arbre gauche (ou fils gauche) et sous arbre droit (ou fils droit). 23 Exemple d’arbre binaire 24 Représentation en arbre binaire d’un arbre général Un arbre binaire peut être utilisé pour représenter un arbre général où les nœuds peuvent avoir un nombre quelconque de fils.

Cette représentation, appelée ‘fils gauche-frère droit » (ou « fils ainé-frère droit »), utilise un arbre binaire dans lequel le fils gauche sera le fils aîné du noeud courant et le fils droit le frère cadet du noeud courant. Noter que la racine de l’arbre binaire n’a pas de fils droit. Structures de données (2012-2013 PAGF OF Arbre Binaire Noeud Elément Préconditions racine(A) est-défini-ssi est_vide(A) = faux auche(A) est-défini-ssi est_vide(A) = faux droite(A) est-défini-ssi est_vide(A) faux Axiomes Sot, r : Nœud, Al, racine() gauche() droite() A2 : Arbre Binaire 28 Opérations sur un Arbre Binaire (1) arbre_vide : Arbre_Binaire opération d’initialisation; crée un arbre binaire vide. st vide PAGF 7 OF taille : Arbre Binaire hauteur : Arbre Binaire feuille : Arbre Binaire Entier Booléen Soit, r : Noeud, Al , A2 : Arbre_Binaire taille(arbre_vide) O taille() = 1 + taille(A1) taille(A2) hauteur(arbre_vide) – si hauteur(A1 ) > hauteur(A2) alors hauteur() = 1+hauteur(A1 ) 1 hauteur(A2) sinon hauteur() si est_vide(A) = faux et est_vide(gauche(A)) = vrai et est_vide(droit(A)) = vrai alors feuille(A) = vrai sinon feuille(A) = faux 31 Parcours d’arbre binaire Un parcours d’arbre permet d’accéder à chaque nœud de l’arbre : Un traitement (test, affichage, comptage, etc. ), dépendant de l’application considérée, est effectué sur l’information portée par chaque nœud Chaque parcours de l’arbre définit un ordre sur les nœuds On distingue : 8 OF Le traitement de la racine r ; Le parcours préfixe du sous arbre gauche Al ; Le parcours préfixe du sous arbre droit A2. Liordre correspondant s’appelle l’ordre préfixe 34 Parcours en profondeur Parcours infixe ou symétrique En abrégé GRD (Gauche, Racine, Droit) Consiste à effectuer dans l’ordre : Le parcours infixe du sous arbre gauche Al ; Le parcours infixe du sous arbre droit A2. L’ordre correspondant s’appelle l’ordre infixe 35 ah-fsr-v2.

O parcours postfixe ou suffixe En abrégé GDR (Gauche, Droit, Racine) Consiste à effectuer dans l’ordre • Le parcours postfixe du sous arbre gauche Al ; Le parcours postfixe du sous arbre droit A2 ; Le traitement de la racine 5, 6, 7, 8, 9, 10, 11, 12, 13 38 Représentations d’un arbre binaire Représentation par tableau (par contiguïté) Représentation par pointeurs (par chainage) 39 Représentation contiguë d’un arbre binaire On caractérise un arbre binaire par : sa taille (nombre de nœuds) ; sa racine (indice de son emplacement dans le tableau de nœuds) ; un tableau de nœuds. Chaque nœud contient trois données : une information de type Elément ; deux entiers (indices dans le tableau désignant respectivement l’emplacement des fils gauche et droit du nœud).