Groupe : Interdiction d'écriture
|
Il faudrait préciser la partie sur le parcours profondeur : en effet, il s'agit d'un parcours profondeur préfixe main gauche dans ton exemple, il en existe plein d'autres variantes (infixe, postfixe en main gauche et en main droite). À part ça, pas grand chose d'autre à dire.
Ah si, une implémentation des arbres en Python :
Code : Python 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Arbre(object):
def __init__(self, val, children):
self.val = val
self.children = children[:]
def dfs(self, func):
func(self.val)
map(lambda t: t.dfs(func), self.children)
def bfs(self, func):
queue = [self]
while queue:
func(queue[0].val)
queue.extend(queue[0].children)
del queue[0]
|
Thus spake the Lord: Thou shalt indent with four spaces. No more, no less.
Four shall be the number of spaces thou shalt indent, and the number of thy
indenting shall be four. Eight shalt thou not indent, nor either indent thou
two, excepting that thou then proceed to four. Tabs are right out.
« C'est comme Perl6. Y'a ceux qui parlent (PHP6/Perl6 c'est super, ça tue tout, blablabla), et ceux qui codent (Python3 sorti fin 2008). » (V. Stinner)
|
dont ask to ask
Groupe : Anciens
|
Ppjet6 > je pense que ces notions ne servent à rien. Selon les cas (selon les algorithmes concrets qui utilisent un parcours) l'ordre de parcours s'imposera naturellement. J'ai d'ailleurs été volontairement flou sur ce que signifie vraiment "parcourir un noeud", pour justement laisser de la liberté à ce niveau : si tu regardes ma définition du DFS, avec le petit "on regroupe les résultats à la fin", couvre en fait toutes les possibilités, pour la bonne définition de "regrouper".
Ces notions, en plus d'être inutiles, ne sont même pas jolies (et n'ont de sens que dans un cadre impératif), je ne vois pas l'intérêt d'en parler. Tu t'en es déjà vraiment servies ou c'est juste ce qu'on t'apprend en cours ?
Pour ton implémentation, je serais plus intéressé par le code qui construit l'arbre donné en exemple, et éventuellement la fonction "taille". Tes bfs/dfs sont bien jolis (et encore, pourquoi tu utilises "map" pour effectuer un effet de bord dans le dfs ?), mais comme ils ne laissent aucune flexibilité sur l'opération faite pendant le parcours : c'est forcément un effet de bord produit à un moment précis.
Je suis prêt à donner des exemples d'implémentations de DFS et BFS dans des situations concrètes (pour le DFS c'est fait avec "taille", pour le BFS je pense attendre les parcours de graphes), mais je ne suis pas très convaincu par l'idée d'un "code générique", puis que justement il ne sera pas assez générique.
|
Groupe : Interdiction d'écriture
|
Je m'en suis bien entendu déjà servi, l'exemple le plus simple que je vois est la récupération des éléments d'un ABR dans l'ordre, où on doit faire un parcours infixe et pas préfixe (et main gauche ou main droite selon l'ordre qu'on veut). Si tu veux te convaincre que ça n'a pas seulement de sens dans un cadre impératif, le code est ici :
Code : OCaml1
2
3
4
5
6 | type 'a abr = Empty | Node of 'a abr * 'a * 'a abr
let rec get_elements = function
| Empty -> []
| Node (left, curr, right) ->
(get_elements left) @ curr :: (get_elements right)
|
Thus spake the Lord: Thou shalt indent with four spaces. No more, no less.
Four shall be the number of spaces thou shalt indent, and the number of thy
indenting shall be four. Eight shalt thou not indent, nor either indent thou
two, excepting that thou then proceed to four. Tabs are right out.
« C'est comme Perl6. Y'a ceux qui parlent (PHP6/Perl6 c'est super, ça tue tout, blablabla), et ceux qui codent (Python3 sorti fin 2008). » (V. Stinner)
|
dont ask to ask
Groupe : Anciens
|
Tu n'as pas compris ce que je veux dire. Je ne dis pas qu'on n'utilise jamais de parcours préfixes ou infixes, je dis que le concept n'est pas utile. Quand tu veux les éléments d'un ABR dans l'ordre, tu fais ce qu'il faut faire, et cet ordre parcours (infixe main gauche si ça t'amuse) s'impose naturellement. Ce que je conteste c'est que le fait de savoir "tiens, c'est un parcours infixe main gauche dis donc" serve à quoi que ce soit.
Un concept est intéressant à partir du moment où sa connaissance peut t'apporter de nouveaux éclairages sur un problème, et t'aider à trouver la solution (ou à la comprendre). Si le coût d'apprentissage (expliquer ce que c'est, avec illustrations etc.) est supérieur au gain à l'utilisation, je n'ai pas intérêt à le mettre dans mon tuto.
Par ailleurs, la définition de "parcours infixe main gauche" que tu utilises est clairement foireuse. La seule définition qui peut marcher c'est "on se rappelle récursivement d'abord sur l'enfant gauche, puis on agit sur la valeur du noeud, puis on se rappelle récursivement sur l'enfant droite". Le problème c'est que c'est une définition impérative (on parle de l'ordre d'une séquence d'instructions) qui n'a pas de sens dès qu'on change de paradigme. Ici par exemple, en l'appliquant à la lettre, et du fait du sens d'évalution de l'implémentation OCaml, c'est un parcours infixe main droite, puisque get_elements right sera appelé en premier. On peut même le considérer comme un parcours préfixe si c'est (fun v -> list left @ v :: list right) que tu appliques à la valeur du noeud. Bref, ces notions sont mal définies et n'apportent pas grand chose. En plus, elles sont moches : quand tu as 50 définitions différentes pour expliquer quelque chose de simple, c'est qu'il y a un problème; une définition c'est fait pour simplifier les choses, pas pour encombrer l'esprit de ton interlocuteur avec du vocabulaire spécialisé.
|
Groupe : Interdiction d'écriture
|
IMHO ça sert au moins à pouvoir formaliser facilement un algorithme qui se base sur un parcours. Mais effectivement, je vois ce que tu voulais dire au niveau de l'ordre d'évaluation et tout ça, et pour un tutoriel qui ne vise pas à être forcèment le plus complet mais plutôt à balayer une multitude de domaines, c'est un choix tout à fait compréhensible que de ne pas aborder cela.
Thus spake the Lord: Thou shalt indent with four spaces. No more, no less.
Four shall be the number of spaces thou shalt indent, and the number of thy
indenting shall be four. Eight shalt thou not indent, nor either indent thou
two, excepting that thou then proceed to four. Tabs are right out.
« C'est comme Perl6. Y'a ceux qui parlent (PHP6/Perl6 c'est super, ça tue tout, blablabla), et ceux qui codent (Python3 sorti fin 2008). » (V. Stinner)
|
dont ask to ask
Groupe : Anciens
|
Pour information, il y a une notion de parcours d'arbre utile que l'on peut définir précisément, c'est le concept de catamorphisme ou fold.
Pour des arbres généraux comme présentés ici, elle est plutôt simple puisqu'un catamorphisme est défini par une fonction agissant sur un élément et une liste (en notation OCaml : fold : ('a * 'b list -> 'b) -> 'a arbre -> 'b). Elle correspond effectivement au parcours en profondeur général que j'ai présenté (la fonction donnée en paramètre est la fonction utilisée pour "réunir les résultats après l'exploration").
Comme elle vient de la programmation fonctionnelle elle ne prend pas en compte l'ordre des effets sur l'arbre : elle se rappelle sur les enfants avant de réunir les résultats, mais il est possible d'effectuer les effets de bords sur les enfants après celui sur le noeud en changeant la fonction passée à fold, avec une forme d'évaluation paresseuse.
Je ne l'ai pas présentée ici parce qu'elle est une notion trop formelle pour le tuto, et qu'elle n'est pas agréable à utiliser dans les langages qui supportent mal le style fonctionnel, mais je pense que c'est une notion intrinsèquement plus universelle que les ordres infixes, postfixes etc.
D'ailleurs, tous les exemples donnés dans la partie DFS correspondent pile poil à des catamorphismes.
|
It's not a bug, it's a feature
Études : TELECOM SudParis
|
l'implémentation Java de l'arbre est incomplète
ton arbre(plutôt ton nœud) ne contient pas de valeur
Secret (cliquez pour afficher)Code : Java 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Tree<T> {
T valeur;
Tree<T>[] enfants;
Tree(T valeur) {
this.enfants = new Tree[0];
this.valeur=valeur;
}
Tree(Tree[] enfants,T valeur) {
this.enfants = enfants;
this.valeur=valeur;
}
public static void main(String[] args) {
Tree d = new Tree('D');
Tree e = new Tree('E');
Tree g = new Tree('G');
Tree h = new Tree('H');
Tree i = new Tree('I');
Tree[] enfants_de_f = { g, h, i };
Tree f = new Tree(enfants_de_f,'F');
Tree[] enfants_de_b = { d, e };
Tree b = new Tree(enfants_de_b,'B');
Tree[] enfants_de_c = { f };
Tree c = new Tree(enfants_de_c,'C');
Tree[] enfants_de_a = { b , c };
Tree a = new Tree(enfants_de_a,'A');
}
}
|
|
dont ask to ask
Groupe : Anciens
|
Merci pour ta remarque Einstein++. Je viens d'ajouter (oui, je suis un peu lent avec la rentrée) la gestion d'une valeur sur chaque noeud, mais ce n'est pas très agréable à faire en Java car les tableaux produisent des warnings quand ils sont utilisés avec des generics...
J'ai hésité à utiliser des Collection à la place, mais je pense que la légèreté syntaxique est importante ici, donc j'ai laissé tableaux et warnings.
|
Ox2A
Ville : St hilaire la treille
Pays : France métropolitaine
Études : IUT A Toulouse
|
Section Quelques algorithmes sur les arbres / Liste des éléments, petite coquille :
"Remarque : Il plusieurs manières de construire la li"
Il existe ? signalement via le formulaire approprié.
Sinon, excellent tutoriel en complément des cours d'algo dispensés à l'IUT, merci les gars 
|
|
|
Très bon tuto, je connaissais toutes ces structures de données (même si en général j'utilise un arbre binaire qui est un cas particulier d'arbre), mais les analyses de complexité et les liens entre eux (bien qu'implicites des fois) m'ont beaucoup aidé à appréhender la globalité.
Cependant, certaines parties de vos implémentations me laissent perplexe, j'irais donc poser mes questions sur le forum C histoire de le surcharger encore un peu.
Très bon boulot vous trois et merci 
Code : C | printf("Bon%s !",
(heure >= 8 && heure < 18) ? "jour" :
(heure >= 18 && heure < 24) ? "soir" : "ne nuit");
|
|
dont ask to ask
Groupe : Anciens
|
Merci pour vos encouragements, ça fait toujours plaisir d'avoir des retours.
quentin-fait-du-c, un esprit critique est évidemment bienvenu vis-à-vis de nos implémentations; ce n'est pas notre spécialité première et il arrive que les codes ne soient pas parfaits. De plus, nous avons des compromis à faire entre pédagogie et efficacité brute, donc le code n'est pas toujours le plus efficace possible.
Je suis ouvert aux précisions sur ce qui te pose problème; n'hésite pas par exemple à donner des liens vers les topics de discussion que tu crées sur le forum (bonne initiative). Si on nous donne des implémentations à la fois meilleures et aussi simples et faciles à expliquer aux débutants, comme jeça a été le cas sur le tri par insertion (grâce aux retours de candide entre autres), je suis preneur.
|
Ppjet6
Trouvez une formation
Suggestions
Twitter
Facebook
Google+