Arbre phylogenetique - python

Citation:

---

Envoyé par VinsS

Désolé Tryph, mais dans ton résultat ("A", 0) n'est pas le parent de ce qui suit, or c'est ce qui est exigé dans le schéma de base.

---

bah biensur que si ("A", 0) est le parent de ce qui suit...
la représentation ne te parait sans doute pas évidente, tu estimes probablement que ta représentation est plus claire (et je suis d'accord sur ce point), ça n'empèche que ce n'est qu'une question de représentation.
et le fait que la représentation ne soit pas la meilleure n'en fait pas quelque chose de faux.

pour preuve, en modifiant juste la représentation, sans rien changer dans l'algo, j'obtiens ça:

Code:

---

1 2 3 4 5 6 7

('A', 0) |-('B', 0.15) | |-('C', 0.22) | |-('D', 0.12) |-('E', 0.2) | |-('F', 0.18) | |-('G', 0.22)

---

ce qui est plus proche de ce que tu considères comme juste, la ligne vide entre un parent et ses enfant en moins.


les données de l'arbre sont aussi plus clairement organisées dans un dictionnaire, je suis d'accord aussi sur ce point.
mais le fait est que le format de l'arbre d'entré est donné et qu'il n'est fait qu'avec des tuples. il faut faire avec...


le format de sortie attendu est donné aussi dans le premier post, et il faut encore une fois faire avec.
pour rappel:
http://www.developpez.net/forums/att...-14.28.38.png/
c'est très exactement ce que j'obtiens avec les données fournies sous forme de tuple et on pourrait tout aussi bien avoir le même résultat avec des données sous forme de dictionnaire

Citation:

---

Envoyé par chlowecita

Je ne comprends pas trop la. Remplacer toute ma ligne par

Code:

---

profondeur(fg,i+1)

---

?

En testant j'obtiens

Code:

---

1 2 3 4

>>> profondeur(monarbre,0) + ('A', 0) + ('B', 0.15) + ('C', 0.22)

---

Alors je vois pas en quoi ca résout mon problème.

---

attention, je n'ai pas dit que ça resoudrait ton problème, j'ai dit que le code ne planterait plus (en admettant que tu as aussi remplacé "tree" par "monarbre") et que tu aurais une base propre pour continuer.
et je te rassure, en faisant juste cette modification, j'ai exactement la même chose que toi: toutes les entrées qui s'affichent dans le bon ordre mais sans la représentation de l'arborescence.

Citation:

---

Envoyé par chlowecita

C'est en effet la fonction des None selon mon cours. et c'est le code que je dois obtenir mais je ne vois pas comment en faisant la modif
sur

Code:

---

profondeur(fg,i+1)

---

tu as pu obtenir cela.

---

y a méprise, pour obtenir ce résultat je me suis pas contenté de simplifier la ligne dont je t'ai parlé, j'ai fait d'autres corrections/ajouts (mais vraiment pas grand chose).
mais je n'ai pas l'intention de fournir le code entierement corrigé.
ce que je veux bien faire, c'est te donner des indices et des indications pour que tu réussisses toi-même à trouver la solution.

Oui j'ai bien fait les modifications :

Code:

---

1 2 3 4 5 6 7 8

def profondeur(monarbre,i): if monarbre == None: return 0 else: (u,fg,fd) = monarbre print "+ " + str(u) print "| " *profondeur(fg,i+1) profondeur(fd,i+1)

---

ce que je ne comprends pas c'est pourquoi dans mon code cela s'arrete à ('C',0.22)

Code:

---

1 2 3 4

>>> profondeur(monarbre,0) + ('A', 0) + ('B', 0.15) + ('C', 0.22)

---

et pourquoi cette ligne n'est pas exécutée :

Code:

---

print "| " *profondeur(fg,i+1)

---

Peux tu expliquer ce que tu penses que doit faire cette ligne ?

Je dois me tromper mais pour moi elle affichait autant de "| " que de "niveau" que l'on descendait dans l'arbre pour le noeud correspondant.


J'ai essayé de mon coté de modifier un peu mon code.
La au moins j'ai tous les noeuds qui s'affiche et plus seulement les 3 premiers. Pour essayer d'y voir plus clair j'y ai rajouté des annotations mais je ne comprends pas le résultat obtenu.

Mon code :

Code:

---

1 2 3 4 5 6 7 8

def profondeur(monarbre,i): if monarbre == None: return 0 else: (u,fg,fd) = monarbre print "+ " + str(u) print "| FILS GAUCHE " + str(profondeur(fg,i+1)) print "| FILS DROIT " + str(profondeur(fd,i+1))

---

et mon résultat :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

>>> profondeur(monarbre,0) + ('A', 0) + ('B', 0.15) + ('C', 0.22) | FILS GAUCHE 0 | FILS DROIT 0 | FILS GAUCHE None + ('D', 0.12) | FILS GAUCHE 0 | FILS DROIT 0 | FILS DROIT None | FILS GAUCHE None + ('E', 0.2) + ('F', 0.18) | FILS GAUCHE 0 | FILS DROIT 0 | FILS GAUCHE None + ('G', 0.22) | FILS GAUCHE 0 | FILS DROIT 0 | FILS DROIT None | FILS DROIT None

---

ce que je ne comprends pas et que vous pourrez peut etre m'expliquer c'est pourquoi mes 3 premiers noeuds sont affiché comme des racines

Je comprends que pour cette partie on est
+ ('C', 0.22)
| FILS GAUCHE 0
| FILS DROIT 0
| FILS GAUCHE None

car ('C',0.22) n'a pas de fils gauche, pas de fils droit, mais pourquoi j'ai un fils gauche None ?
Cela viendrait de la facon de coder l'arbre ? Ou tous mon code de la fonction profondeur est pourri ?

Citation:

---

Envoyé par chlowecita

Je dois me tromper mais pour moi elle affichait autant de "| " que de "niveau" que l'on descendait dans l'arbre pour le noeud correspondant.

---

dans l'état actuel des choses, il est impossible que la ligne suivante t'affiche les différents niveaux

Code:

---

print "| " *profondeur(fg,i+1)

---

si tu regardes ta fonction profondeur, tu peux noter qu'elle ne ne peut renvoyer que 2 résultat différents:

• 0 si l'arbre qu'on lui a donné est égal à None
• rien si l'arbre qu'on lui a donné est différent de None. et en Python, "rien" se traduit par None (garde ça en tête ça va resservir plus tard)

donc ta ligne de code ci-dessus ne peut faire que 2 choses:

• afficher une chaine vide ("| " * 0) ç chaque niveau durant le parcours d'une branche
• provoquer une erreur ("| " * None) et faire planter le programme quand on arrive au bout de la branche

tu as déjà l'explication se rapportant au fait que seuls les 3 niveaux de la première branche étaient affichés.

Citation:

---

Envoyé par chlowecita

J'ai essayé de mon coté de modifier un peu mon code.
La au moins j'ai tous les noeuds qui s'affiche et plus seulement les 3 premiers. Pour essayer d'y voir plus clair j'y ai rajouté des annotations mais je ne comprends pas le résultat obtenu
....

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

>>> profondeur(monarbre,0) + ('A', 0) + ('B', 0.15) + ('C', 0.22) | FILS GAUCHE 0 | FILS DROIT 0 | FILS GAUCHE None + ('D', 0.12) | FILS GAUCHE 0 | FILS DROIT 0 | FILS DROIT None | FILS GAUCHE None + ('E', 0.2) + ('F', 0.18) | FILS GAUCHE 0 | FILS DROIT 0 | FILS GAUCHE None + ('G', 0.22) | FILS GAUCHE 0 | FILS DROIT 0 | FILS DROIT None | FILS DROIT None

---

ce que je ne comprends pas et que vous pourrez peut etre m'expliquer c'est pourquoi mes 3 premiers noeuds sont affiché comme des racines

---

pour les 3 niveaux qui sont affichés comme des racines, c'est tout à fait normal et faut suivre le déroulement du programme pour le comprendre.
voir les lignes en bleu ci dessous... et toutes les autres aussi en fait, il est important que tu comprennes comment se déroule ton programme.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

la fonction profondeur est appelée avec l'arbre entier en argument ("A", 0), ... (niveau 0) la racine ("A", 0) est récupérée dans une variable, ainsi que le fils gauche ('B', 0.15), ... et le fils droit ("E",0.2), ... la racine est affichée: "+ " + str(u) -> + ("A", 0) la fonction profondeur est appelée avec le fils gauche ('B', 0.15), ... (niveau 1) la racine ('B', 0.15) est récupérée dans une variable, ainsi que le fils gauche ("C",0.22), ... et le fils droit ("D",0.12), .... faut bien comprendre qu'ici, monarbre n'est plus l'arbre entier, uniquement la branche gauche du premier niveau la racine est affichée: "+ " + str(u) -> + ("B", 0.15) la fonction profondeur est appelée avec le fils gauche ("C",0.22), ... (niveau 2) la racine ("C",0.22) est récupérée dans une variable, ainsi que le fils gauche None et le fils droit None. ici, monarbre n'est plus que la branche gauche de la première branche gauche la racine est affichée: "+ " + str(u) -> + ("C",0.22) la fonction profondeur est appelée avec le fils gauche None (niveau 3) la fonction profondeur du niveau 3 renvoie 0 affichage de "| FILS GAUCHE " + 0 la fonction profondeur est appelée avec le fils droit None (niveau 3) la fonction profondeur du niveau 3 renvoie 0 affichage de "| FILS DROIT " + 0 on est arrivé à la fin de la fonction profondeur pour le niveau 2, on ne renvoie rien; en vrai, c'est None qui renvoyé. affichage de "| FILS GAUCHE " + None la fonction profondeur est appelée avec le fils droit ("D",0.12), ... (niveau 2) ... je te laisse poursuivre à partir d'ici ...

---

Citation:

---

Envoyé par chlowecita

mais pourquoi j'ai un fils gauche None ?

---

la réponse est dans la ligne rouge et les quelques ligne précédentes du déroulement ci-dessus.

Citation:

---

Envoyé par chlowecita

Cela viendrait de la facon de coder l'arbre ? Ou tous mon code de la fonction profondeur est pourri ?

---

ça vient pas de l'arbre mais de ton code.
je dirais pas qu'il est pourri, mais je pense que t'as pas bien compris ce qu'est la récursion encore (le fait qu'une fonction s'appelle elle même). et du coup tu t'y prends mal pour afficher tes niveaux.
selon moi, la bonne façon de faire, c'est de pas chercher à récupérer le résultat de la fonction profondeur pour afficher les niveaux. quand tu appelles la fonction profondeur sur le fils gauche puis le fils droit, tu ne dois rien faire avec le retour de la fonction. tout ce qui est affichage doit être fait avant que la fonction profondeur s'appelle elle même.
pour être plus clair, toutes les instructions en rapport avec l'affichage doivent se trouver avant ces lignes:

Code:

---

1 2	profondeur(fg,i+1) profondeur(fd,i+1)

---

Citation:

---

Envoyé par Tryph

pour les 3 niveaux qui sont affichés comme des racines, c'est tout à fait normal et faut suivre le déroulement du programme pour le comprendre.
voir les lignes en bleu ci dessous... et toutes les autres aussi en fait, il est important que tu comprennes comment se déroule ton programme.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

la fonction profondeur est appelée avec l'arbre entier en argument ("A", 0), ... (niveau 0) la racine ("A", 0) est récupérée dans une variable, ainsi que le fils gauche ('B', 0.15), ... et le fils droit ("E",0.2), ... la racine est affichée: "+ " + str(u) -> + ("A", 0) la fonction profondeur est appelée avec le fils gauche ('B', 0.15), ... (niveau 1) la racine ('B', 0.15) est récupérée dans une variable, ainsi que le fils gauche ("C",0.22), ... et le fils droit ("D",0.12), .... faut bien comprendre qu'ici, monarbre n'est plus l'arbre entier, uniquement la branche gauche du premier niveau la racine est affichée: "+ " + str(u) -> + ("B", 0.15) la fonction profondeur est appelée avec le fils gauche ("C",0.22), ... (niveau 2) la racine ("C",0.22) est récupérée dans une variable, ainsi que le fils gauche None et le fils droit None. ici, monarbre n'est plus que la branche gauche de la première branche gauche la racine est affichée: "+ " + str(u) -> + ("C",0.22) la fonction profondeur est appelée avec le fils gauche None (niveau 3) la fonction profondeur du niveau 3 renvoie 0 affichage de "| FILS GAUCHE " + 0 la fonction profondeur est appelée avec le fils droit None (niveau 3) la fonction profondeur du niveau 3 renvoie 0 affichage de "| FILS DROIT " + 0 on est arrivé à la fin de la fonction profondeur pour le niveau 2, on ne renvoie rien; en vrai, c'est None qui renvoyé. affichage de "| FILS GAUCHE " + None la fonction profondeur est appelée avec le fils droit ("D",0.12), ... (niveau 2) ... je te laisse poursuivre à partir d'ici ...

---

la réponse est dans la ligne rouge et les quelques ligne précédentes du déroulement ci-dessus.

---

Merci ! J'ai bidouillé mon code de pas grand chose

Code:

---

1 2 3 4 5 6 7 8 9 10

def profondeur(monarbre,i): if monarbre == None: return 0 else: (u,fg,fd) = monarbre print "+ " + str(u)   profondeur(fg,i+1)   profondeur(fd,i+1)

---

Je comprends pourquoi (cf vos explications en bleues) tous mes noeuds sont affichés comme des racines. En effet, avec mon code j'obtiens ceci

Code:

---

1 2 3 4 5 6 7 8

>>> profondeur(monarbre,0) + ('A', 0) + ('B', 0.15) + ('C', 0.22) + ('D', 0.12) + ('E', 0.2) + ('F', 0.18) + ('G', 0.22)

---

parcontre je comprends pas cette partie

Citation:

---

Envoyé par Tryph

ça vient pas de l'arbre mais de ton code.
je dirais pas qu'il est pourri, mais je pense que t'as pas bien compris ce qu'est la récursion encore (le fait qu'une fonction s'appelle elle même). et du coup tu t'y prends mal pour afficher tes niveaux.
selon moi, la bonne façon de faire, c'est de pas chercher à récupérer le résultat de la fonction profondeur pour afficher les niveaux. quand tu appelles la fonction profondeur sur le fils gauche puis le fils droit, tu ne dois rien faire avec le retour de la fonction. tout ce qui est affichage doit être fait avant que la fonction profondeur s'appelle elle même.
pour être plus clair, toutes les instructions en rapport avec l'affichage doivent se trouver avant ces lignes:

Code:

---

1 2	profondeur(fg,i+1) profondeur(fd,i+1)

---

---

Je vois pas. J'ai essayé en placant un retour à la ligne

Code:

---

print "\n" "| "

---

avant

Code:

---

1 2	profondeur(fg,i+1) profondeur(fd,i+1)

---

[/QUOTE] mais ce n'est pas ca. Je ne sais pas quoi ecrire pour decaler d'un espace à chaque fois que je descends d'un niveau enfaite

J'ai essayé ca aussi du coup :

Code:

---

1 2 3 4 5 6 7 8 9 10

def profondeur(monarbre,i): if monarbre == None: return 0 else: (u,fg,fd) = monarbre print "+ " + str(u) print "| " + "|-"*i profondeur(fg,i+1)   profondeur(fd,i+1)

---

Je pense pas être loin, enfin je l'espere vu le résultat que ca me donne

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

>>> profondeur(monarbre,0) + ('A', 0) | + ('B', 0.15) | |- + ('C', 0.22) | |-|- + ('D', 0.12) | |-|- + ('E', 0.2) | |- + ('F', 0.18) | |-|- + ('G', 0.22) | |-|-

---

Mais du coup mon problème ca serait la récursivité car les noeuds ne s'affichent pas la ou ils devraient à cause de

Code:

---

print "+ " + str(u)

---

je suis perdue.

Salut,

Je continue à chercher parce que ca m'embête vraiment et j'en suis venu à ca

Code:

---

1 2 3 4 5 6 7 8 9 10

def profondeur(monarbre,i): if monarbre == None: return 0 else: (u,fg,fd) = monarbre print "+ " + str(u) print "| " * i + str(fg) print "|--+ " *i + str(fd) profondeur(fg,i+1) profondeur(fd,i+1)

---

qui me renvoie ceci :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

>>> profondeur(monarbre,0) + ('A', 0) (('B', 0.15), (('C', 0.22), None, None), (('D', 0.12), None, None)) (('E', 0.2), (('F', 0.18), None, None), (('G', 0.22), None, None)) + ('B', 0.15) | (('C', 0.22), None, None) |--+ (('D', 0.12), None, None) + ('C', 0.22) | | None |--+ |--+ None + ('D', 0.12) | | None |--+ |--+ None + ('E', 0.2) | (('F', 0.18), None, None) |--+ (('G', 0.22), None, None) + ('F', 0.18) | | None |--+ |--+ None + ('G', 0.22) | | None |--+ |--+ None

---

C'est pas mieux j'ai l'impression et je pense que mon problème est sur la partie

Code:

---

1 2 3

print "+ " + str(u) print "| " * i + str(fg) print "|--+ " *i + str(fd)

---

au niveau du stockage des variables ? Mais malheureusement je ne vois pas comment faire. Si quelqu'un aurait une piste.. Merci !

Et je m'obstine et j'obtiens un résultat qui se rapproche de plus en plus à ce que je dois avoir normalement.

Mais PROBLEME je ne suis plus en récursif.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

def profondeur(monarbre,i): if monarbre == None: return 0 else: (u,fg,fd) = monarbre print "+ " + str(u) print "|--+" + str(fg[0]) print "| " *i + "|--+" + str(fg[i]) print "| " *i + "|--+" + str(fg[i+1]) print "|--+ " + str(fd[0]) print "| " *i + "|--+" + str(fd[i]) print "| " *i + "|--+" + str(fd[i+1])

---

qui me donne :

Code:

---

1 2 3 4 5 6 7 8

>>> profondeur(monarbre,1) + ('A', 0) |--+('B', 0.15) | |--+(('C', 0.22), None, None) | |--+(('D', 0.12), None, None) |--+ ('E', 0.2) | |--+(('F', 0.18), None, None) | |--+(('G', 0.22), None, None)

---

du coup je vois bien que j'aurai un problème lors de l'exécution de mon fichier test si j'ai un arbre qui va plus loin que i+2 mais je bute.. Help please

Salut,

bien tenté la méthode toute statique qui ne fonctionne que pour 2 niveaux mais c'est assez laid et comme tu le dis, c'est surtout pas très flexible. ;)

non l'idéal c'est bien la récursion et, comme tu l'as deviné, ton problème avec la version récursive se trouve ici (plus particulièrement aux lignes 2 et 3):

Code:

---

1 2 3

print "+ " + str(u) print "| " * i + str(fg) print "|--+ " *i + str(fd)

---

tu cherches ici à afficher la racine et ses 2 enfants, alors que tu n'as aucun besoin d'afficher les enfants puisque ceux-ci seront affiché quand tu appelleras la fonction profondeur avec chacun d'eux.
concrètement, dans la fonction profondeur, tu n'a à te soucier que de l'affichage de racine de l'arbre, soit la variable "u" dans ton code. et les ligne 2 et 3 du code ci dessus sont clairement en trop.
après tu as besoin d'afficher cette racine avec le bon nombre de décalages et ça tombe bien parce que tu connais ce nombre de décalage par le paramètre "i" de ta fonction.

Citation:

---

Envoyé par Tryph

Salut,

bien tenté la méthode toute statique qui ne fonctionne que pour 2 niveaux mais c'est assez laid et comme tu le dis, c'est surtout pas très flexible. ;)

non l'idéal c'est bien la récursion et, comme tu l'as deviné, ton problème avec la version récursive se trouve ici (plus particulièrement aux lignes 2 et 3):

Code:

---

1 2 3

print "+ " + str(u) print "| " * i + str(fg) print "|--+ " *i + str(fd)

---

tu cherches ici à afficher la racine et ses 2 enfants, alors que tu n'as aucun besoin d'afficher les enfants puisque ceux-ci seront affiché quand tu appelleras la fonction profondeur avec chacun d'eux.
concrètement, dans la fonction profondeur, tu n'a à te soucier que de l'affichage de racine de l'arbre, soit la variable "u" dans ton code. et les ligne 2 et 3 du code ci dessus sont clairement en trop.
après tu as besoin d'afficher cette racine avec le bon nombre de décalages et ça tombe bien parce que tu connais ce nombre de décalage par le paramètre "i" de ta fonction.

---

Tout d'abord merci de prendre le temps de m'aider.
C'est sans doute une question con, mais si les lignes 2 et 3 sont en trop, je ne vais afficher que

Code:

---

1 2 3 4 5 6 7

+ ('A', 0) + ('B', 0.15) + ('C', 0.22) + ('D', 0.12) + ('E', 0.2) + ('F', 0.18) + ('G', 0.22)

---

parce que du coup mon parametre i n'apparait plus :(

Salut,

effectivement, si tu ne fais qu'enlever les 2 lignes que je t'ai indiqué, tout s'affiche au même niveau.

mais si tu remplaces cette ligne:

Code:

---

print "+ " + str(u)

---

par celle-ci:

Code:

---

print "\t" * i + str(u)

---

ça donne quoi?

Citation:

---

Envoyé par Tryph

Salut,

effectivement, si tu ne fais qu'enlever les 2 lignes que je t'ai indiqué, tout s'affiche au même niveau.

mais si tu remplaces cette ligne:

Code:

---

print "+ " + str(u)

---

par celle-ci:

Code:

---

print "\t" * i + str(u)

---

ça donne quoi?

---

a oui du coup la j'ai les bons décalage il me reste juste à trouver un moyen d'afficher les " + " et les "| " *i + "|--+"
Merci beaucoup

Edit

Code:

---

1 2 3 4 5 6 7 8 9

def profondeur(monarbre,i): if monarbre == None: return 0 else: (u,fg,fd) = monarbre print "\t" *i + "| " *(i-1) + "|--+ " + str(u)   profondeur(fg,i+1) profondeur(fd,i+1)

---

Comment je peux isoler la racine " véritable " de l'arbre, à savoir ('A',0) de facon à avoir

Code:

---

+('A',0)

---

et non pas

Code:

---

1 2 3 4 5 6 7 8

profondeur(monarbre,0) |--+ ('A', 0) |--+ ('B', 0.15) | |--+ ('C', 0.22) | |--+ ('D', 0.12) |--+ ('E', 0.2) | |--+ ('F', 0.18) | |--+ ('G', 0.22)

---

?

EDIT 2
Il doit y avoir une plus belle façon de le faire mais j'ai pensé à ca et ca à l'air de fonctionner

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

def profondeur(monarbre,i): if monarbre == None: return 0 else: (u,fg,fd) = monarbre if i == 0 : print "+ " + str(u) else: print "\t" *i + "| " *(i-1) + "|--+ " + str(u)   profondeur(fg,i+1) profondeur(fd,i+1)

---

Merci beaucoup ! Vraiment !

essaye d'enlever les tabulations (les "\t"), ça sera encore mieux.
je les ai mises dans l'exemple de mon post précédent juste pour te mettre sur la voie, si tu les laisses ça fait moche.


sinon pour la belle façon de faire:
- tester i == 0 pour repérer le racine de l'arbe me parait la bonne façon de faire (c'est plus ou moins ce que j'ai fait)
- pour ce qui est de l'affichage, je préfère construire ma chaine dans une variable (line dans le code ci-dessous) puis avoir une seule instruction print ensuite:

Code:

---

1 2 3 4 5 6

line = "" if i: line += "| " * (i - 1) line += "|--" line += "+ " + str(u) print line

---

mais ça c'est surtout une question de gout, d'autres diront qu'ils préfèrent mettre plusieurs print.

EDIT:
si tu veux faire du code plus "beau", ou en tout cas plus en accord avec les conventions de codage Python, tu peux chercher pep8 et pylint qui sont 2 utilitaires qui te prendront la tête pour que tu mettes bien des espace là ou il en faudrait (par exemple) ou inversement et bien plus encore...