Discussion :

[momo199]

Bonjour, je dois implémenter en Python le parcours préfixe d'un arbre représenté avec des dictionnaires te il doit retourner une liste avec les sommets et j'ai créé deux fonctions qui permettent d'extraire la partie gauche et droite d'un arbre mais le problème qu'à chaque fois il ne retourne pas le résultat.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
36
37
38
39
40
41
42
43
 
def gauche(G,i):
    liste=[]
    for u in G:
        l=[]
        if i not in G:
            return 'None'
        else:
            for v in G[i]:
                l.append(v)
                liste=l[0]
    return liste
 
 
 
def droite(G, i):
    liste = []
    for u in G:
        l = []
        if i not in G:
            return 'None'
        else:
            for v in G[i]:
                liste = v[0]
 
    return liste
 
def parcours(G,i):
    s = premierliste(G)
    nb=[]
    pere={}
    pere[s]=None
    for u in G:
        for v in G[u]:
            pere[v]=u
        while u != 'None':
                nb.append(u) 
                u=gauche(G,u)
                print(u)
                if u == 'None':
                    v=droite(G,pere[u])
                    nb.append(v) 
return nb

[Aelurus_]

Salut,
pourquoi écrits tu

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for v in G[i]:
                l.append(v)
                liste=l[0]

Nous sommes d'accord que l comme liste sont deux listes, non?

[momo199]

Pour obtenir juste le sommet qu'il me faut car j'ai besoin du sommet mais pas de la liste contenant le sommet pour ensuite l'utiliser dans l'algorithme du parcours.

[Aelurus_]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

l[0]

est sensé ressembler à quoi ? Et je ne comprends pas la déclaration

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

liste=[]

pour avoir

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
liste=l[0]
et
return liste

et si à chacun de tes tests i n'est pas dans G ba que te dire, tu n'as pas un exemple complet avec G et i puis le résultat attendu ?

[momo199]

par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
G={'a':['b','c'], 'c':['f','e'], 'e':['d']}
 
gauche(G,'a')

gauche donnerait l'élément à gauche de la liste et pour ça, je retourne le sommet l[0], mais pour la fonction droite donnerait l' élément à droite de la liste si la longueur de la liste est supérieur à 1 et donc retourne le sommet l[1] mais je ne sais pas comment traiter la fonction si une clé a dans la liste plus de 2 éléments.

[wiztricks]

Salut,

Un parcours d'arbre en préfixe, c'est d'abord un algorithme, d'abord récursif (c'est plus simple). On pourrait écrire çà:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def p(g, n):
    L = [ n ]
    if n in g:
        for c in g[n]:
            L += p(g, c)
    return L
 
 
G={'a':['b','c'], 'c':['f','e'], 'e':['d']}
print(p(G, 'a'))

Après désolé mais je ne comprends pas pourquoi vous voulez avoir une gauche et une droite.

Ça pourrait être utile pour transformer l'arbre en arbre binaire mais si c'est ce que vous voulez faire autant l'énoncer clairement....

Et toujours pareil, c'est d'abord un algo. plutôt récursif qu'on peut coder avec Python (mais sans algo. vous pouvez toujours essayez ce que vous voulez, çà a peu de chance de marcher).
note: côté algo. un peu de recherche sur Internet devrait vous donner des idées.

- W

[Sve@r]

Bonjour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
G={'a':['b','c'], 'c':['f','e'], 'e':['d']}
 
gauche(G,'a')

gauche donnerait l'élément à gauche de la liste

Donc "b" ???

et j'ai créé deux fonctions qui permettent d'extraire la partie gauche et droite

mais je ne sais pas comment traiter la fonction si une clé a dans la liste plus de 2 éléments.

Ben si la clé a plus de 2 éléments, tu ne peux plus parler de partie gauche et droite !!!

[Beginner.]

Salut,

Je crois que par "élément à gauche" il veut dire le premier élément de la liste et par "élément à droite" le dernier élément de la liste...

..., mais pour la fonction droite donnerait l' élément à droite de la liste si la longueur de la liste est supérieur à 1 et donc retourne le sommet l[1] mais je ne sais pas comment traiter la fonction si une clé a dans la liste plus de 2 éléments.

Si par "élément à droite" tu veux dire le dernier élément de la liste alors tu peux y accéder en faisant : l[-1] quelque soit le nombre d'éléments de la liste l, ce qui est bien pratique...