Management

Qu’est-ce qu’un arbre ? Vocabulaire Les arbres sont composés de deux éléments de base . les nœuds (ou vertex), un nœud peut être étiqueté ou non : c’est à-dire porter une ou plusieurs valeurs, les arcs (ou arêtes) qui relient les nœuds (un arc relie deux nœuds différents), un arc peut être pondéré ou non : c’est-à-dire porter une ou plusieurs valeurs. De manière informell chemin entre deux n 2 p g un ensemble d’arcs permettant de relier ces deux nœuds. Par définition, un arc ne peut intervenir qu’une seule fois dans un chemin donné.

Définitions Dans la théorie des graphes, deux notions ifférentes sont considérées . la notion d’arbre dont les arcs ne sont pas orientés (ou bidirectionnels), et celle d’arborescence dont les arcs sont orientés. Un arbre un arbre est un graphe non orienté acyclique, les arbres ? Organisation de systèmes de fichiers. Organisations hiérarchiques. Ordonnancement de données. Recherche de données. Réalisation de programmes. Les arbres en Scheme ? Aparté : define-struct Il est possible en Scheme de définir des structures complexes via la fonction : define-struct Syntaxe . (define-struct nom (nom-eleml nom-elem2… ) Exemple : define-struct complexe (reel image)) Avec la création d’une structure, différentes fonctions sont automatiquement créées : un constructeur : make-nom des accesseurs : nom-nom-eleml, nom-nom-elem2, nom-… un test nom? et quelques autres.. 20F 12 arborescence est : un ensemble de nœuds où un nœud contient l’ensemble des arcs dont il est l’origine ? un nœud contenant l’ensemble de ses sousarborescences ? et comment allons-nous gérer les étiquettes ? Première arborescence en Scheme Premier cas : un ensemble de nœuds numérotés (ex : (1, 2, 3, 4, 5, un ensemble d’arcs (paire de nœuds) (ex : ((1. ), n ensemble d’étiquettes (paire de nœud et valeur) pour représenter les feuilles étiquetées (ex : ((3. a), (4. ‘Tl), (5. 3), (6. 3), (7. 9)) Premier cas en Scheme : L’arborescence : ; ANALYSE ET DEFINITION DES DONNEES (define-struct arborescence (node edge label)) ; une arborescence est une structure : node edge label) ; où node est une liste de noeuds, edge une liste ; d’arcs et label une liste d’étiquettes. (define arbol (make-arborescence (list 1 23 45 6 7) (list ‘(1 . 2) ‘(1 . 3) ‘(1 . 4) ‘(2 . 5) ‘(2 . 6) ‘(2 . 7)) (list ‘(3 . ‘a) ‘m) ‘(5 . ‘3) ‘(6 . ‘3) ; TEMPLATE ; (define (foo-arborescence arbo) (cond [(.. arborescence-node arbo ; .. (arborescence-edee arb 30F 12 (define-struct leaf (content)) ; une feuille est une structure : (make-leaf content) ; où content est l’étiquette de la feuille. (define leafl (make-leaf (define leaf2 (make-leaf ‘m)) (define leaf3 (make-leaf ‘3)) (define leaf4 (make-leaf ‘3)) (define leaf5 (make-leaf ‘9)) ; (define (foo-leaf l) ; (cond [(.. (leaf-content l) IJne autre arborescence en Second cas étudié en Scheme : Le nœud (define-struct node (sub-tree)) ; un noeud est une structure : (make-node sub-tree) ; où sub-tree est la liste des sous-arborescences du noeud. define nodel (make-node (list st 1 leafl leaf2))) ; (define (foo-node n) ; (cond [(.. (leaf-sub-tree n) Une autre arborescence en Second cas étudié en Scheme L’arborescence (ou sous-arborescence) . ; une arborescence (ou sous-arborescence) est ; soit un noeud soit une feuille (define stl (make-node (list leaf3 leaf4 leaf5))) 4 2 sous-arborescence) : ; une liste de sous-arborescences ou de feuilles (define arbol (list (list 3 ‘3 ‘9) ‘a ‘m)) ; (cond ((symbol? arbo) ) ((list? arbo) ) . Exemple pratique d’arborescence. un programme se représente sous forme Son interprétation ?quivaut à un parcours de cette arborescence. efine arbol (list (list 3 ‘3 ‘9) ‘a ‘m)) (list ‘3 ‘3 ‘9) 2 gauche ou la droite Avant d’explorer la branche suivante. Parcours en profondeur Ce parcours consiste ? descendre le plus profond possible par la gauche ou la droite Par la gauche ou la droite Parcours en profondeur en Choix du parcours : en profondeur par la gauc 6 2 (define (foret_profondeur LA) (cond ((empty? LA) ( ;; traitement du noeud courant (car LA) , • attention à l’appelle recursif (foret_profondeur (cdr LA)) (else (foret_profondeur (append (fils (car LA)) (Cdr LA)))) Parcours en largeur arcourir tous les fils d’un nœud avant de parcourir ses petits fils. un nœud avant de (define (arbre_largeur A) (cond ((empty? A) (else (foret_largeur (list (racine A)))) Parcours en largeur en Scheme : code (2/2) fonction de parcourt en largeur ;; d’une foret (liste de noeuds racines) foret_profondeur : liste -s . (define (foret_largeur LA) ; traitement du noeud courant (car LA) attention à l’appelle recursif ;; (foret_largeur (cdr LA)) (else (foret_largeur (append (cdr LA) (fils (car LA))))) Arbres n-aires Un arbre n-aire est un arbre, tel que chaque nœud ait n fils. Une feuille d’un tel arbre st un nœud dont les n fils sont nulles (ou vides). Les arbres binaires sont les plus utilisés.

Arbres binaires un arbre binaire est un nœud ait deux fils : B2 ANALYSE ET DEFINITION DES DONNEES ; un arbre binaire est représenté par ça racine ; qui est de type noeud. ; un noeud, pour un arbre binaire, est une structure ; qui contient : un sous arbre gauche, un sous arbre ; droit et une étiquette. (define-struct noeud (arbre_gauche arbre_droit etiquette)) ; (define (foo-noeud n) ; (cond ((noeud? n) TD arbres binaires : primitive racine: arbre — noeud leaf? : noeud boolean sous-arbre-gauche: noeud arbre ous-arbre-droit: noeud arbre etiquette: noeud Object empty? : arbre boolean fils: noeud TD arbres binaires : existe? ersion arbres binaires existe? retourne vraie si et seulement si l’objet , passé en paramètre est une étiquette de l’arbre binaire passé en paramètre. ;; existe? : objet x arbre boolean (define (existe? obj a) (cond ((empty? a) #f) ((equal? obj (etiquette (racine a))) #t) (else (or (existe? obj (sous-arbre-gauche a)) (existe? obj (sous-arbre-droit a)))) LA) ((equals? obj (etiquette (car LA))) #t) (else (foret_existe? obj (append (fils (car LA)) (cdr LA)))) TD arbres binaires : count ; count retourne le nombre d’occurrences de l’objet ;; passé en paramètre apparaissant comme ;; étiquette de l’arbre binaire passé en paramètre. ount : objet x arbre -> entier (define (count obj a) (cond ((empty? a) O) ((equal? obj (etiquette (racine a)) (+ 1 (count obj (sous-arbre-gauche a)) (count obj (sous-arbre-droit a)))) (else (+ (count obj (sous-arbre-gauche a)) (count Ob] (sous-arbre-drolt a)))) version générique (1/2) passé en paramètre apparaissant comme ;; étiquette de l’arbre passé en paramètre. count : objet x arbre entier (else (foret_count obj (list (racine a)))) 0 2