[PDF] Algo Prog Objet Python Parcours en profondeur d'abord (

View - Download Algo Prog Objet Python

Previous PDF

Next PDF

Andrea G. B. Tettamanzi, 20121AlgorithmiqueAlgorithmique Programmation ObjetProgrammation ObjetPythonPython

Andrea G. B. Tettamanzi

Université de Nice Sophia Antipolis

Département Informatique

andrea.tettamanzi@unice.fr

Andrea G. B. Tettamanzi, 20122CM - Séance 9

Arbres

et

Graphes

Andrea G. B. Tettamanzi, 20123Plan

•Arbres -Définitions -Parcours -Réalisation •Graphes

Andrea G. B. Tettamanzi, 20124Arbre

•Structure de données récursive •Un arbre est formé par -Un noeud (dit " racine »), contenant •Des données ou une référence à des données •Des références (ou pointeurs) à des (sous-)arbres -Zéro ou plus sous-arbres •Un noeud n'ayant pas des sous-arbres est dit " feuille » •Les autres noeuds sont dits " noeuds internes » •Nous avons déjà rencontré ce type de structure quand on a

étudié les tas

Andrea G. B. Tettamanzi, 20125Arbre

Andrea G. B. Tettamanzi, 20126Arbre

•La racine r de l'arbre est l'unique noeud ne possédant pas de parent •Tout noeud x qui n'est pas la racine a -un unique parent, noté x.parent ou parent(x) (appelé " père » parfois) -0 ou plusieurs fils ; x.fils ou fils(x) désigne l'ensemble des fils de x •Si x et y sont des noeuds tels que x soit sur le chemin de r à y, -x est un ancêtre de y -y est un descendant de x •Les fuilles n'ont pas de fils

Andrea G. B. Tettamanzi, 20127Arbre

1 e s t l a r a c i n e 9 1 0 6 3 1 1 1 2 8 s o n t l e s f e u il l e s 1 1 e s t u n d e s c e n d a n t d e 4 m a i s p a s d e 2 2 e s t u n a n c t r e d e 1 0

Andrea G. B. Tettamanzi, 20128Arbre

•Quand il n'y a pas d'ambiguïté, on regarde les arêtes d'un arbre comme étant orienté de la racine vers les feuilles •La profondeur d'un noeud (depth) est définie récursivement par -prof(v) = 0, si v est la racine -prof(v) = prof(parent(v)) + 1 •La hauteur d'un noeud (height) est la plus grande profondeur d'une feuille du sous-arbre dont il est la racine

Andrea G. B. Tettamanzi, 20129Arbre

1 e s t l a r a c i n e 2 3 4 s o n t l a p r o f o n d e u r 1 5 6 7 8 l a p r o f o n d e u r 2 L a h a u t e u r d e 2 e s t 2 c e ll e d e 9 e s t 0 c e ll e d e 3 e s t 0 c e ll e d e 1 e s t 4 Andrea G. B. Tettamanzi, 201210Arbre : Utilisation •Les arbres sont un peu partout en Informatique •Représenter la structure syntaxique d'espressions (parsing) -Mathématiques ou logiques -De langages de programmations -Du langage naturel •Gérer des bases de données •Indexation de fichiers. •Tri par tas •Ils permettent des recherches rapides et efficaces.

Andrea G. B. Tettamanzi, 201211Arbre : Parcours

•Parcours (tree traversal) : -on traverse l'ensemble des noeuds de l'arbre •Parcours en largeur d'abord (breadth first) •Parcours en profondeur d'abord (depth first) -Préfixé -Infixé -Postfixé Andrea G. B. Tettamanzi, 201212Parcours en largeur d'abord •On visite la racine •Puis on répète le processus suivant jusqu'à avoir visité tous les sommets : -visiter un fils non visité du sommet le moins récemment visité qui a au moins un fils non visité •On visite tous les sommets à la profondeur 1, •puis tous ceux à la profondeur 2, •puis tous ceux à la profondeur 3 •etc... Andrea G. B. Tettamanzi, 201213Parcours en largeur d'abord L a r g eu r d a b o r d o r d r e d e v i s it e 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 Andrea G. B. Tettamanzi, 201214Parcours en largeur d'abord

Liste ParcoursEnLargeur()

F ← File()

F.enfiler(racine())

L ← Liste()

tant que non F.estVide() x ← F.premier() ; F.défiler()

L.ajouter(x)

pour chaque fils y de x

F.enfiler(y)

renvoyer L Andrea G. B. Tettamanzi, 201215Parcours en largeur d'abord avec passes

Liste ParcoursEnLargeurAvecPasses()

F1 ← File() ; F2 ← File()

F1.enfiler(racine())

L ← Liste()

répéter : tant que non F1.estVide() x ← F1.premier() ; F1.défiler()

L.ajouter(x)

pour chaque fils y de x

F2.enfiler(y)

échanger(F1, F2) # Fin d'une passe, début de la suivante tant que non F1.estVide() renvoyer L Andrea G. B. Tettamanzi, 201216Parcours en largeur d'abord avec passes L a r g e u r d a b o r d a v e c p a s s e s O r d r e d e v i s it e P a s s e 1 1 P a s s e 2 2 3 4 P a s s e 3 5 6 7 8 P a s s e 4 9 1 0 1 1 1 2 Andrea G. B. Tettamanzi, 201217Parcours en profondeur d'abord •Défini de façon récursive •visit(noeud x) previsit(x) pour chaque fils y de x visit(y) postvisit(x) •Premier appel : visit(T.racine()) Andrea G. B. Tettamanzi, 201218Parcours en profondeur d'abord •Ordre préfixé ou postfixé dépend des fonctions previsit et postvisit •Si previsit(x) : met x dans liste -alors liste contient l'ordre préfixé •Si c'est postvisit qui le fait -alors liste contiendra l'ordre postfixé Andrea G. B. Tettamanzi, 201219Parcours en profondeur d'abord O r d r e de v i s it e p r fi x O n m a r q u e q u a n d oquotesdbs_dbs16.pdfusesText_22

[PDF] parcours en largeur graphe java

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne

[PDF] livret militaire en ligne

[PDF] la coexistence pacifique de 1953 ? 1962 pdf

[PDF] cornière catnic

[PDF] corniere galva pour brique

[PDF] corniere pour linteau brique

[PDF] cornière support briques