Discussion :

[@min@]

bonjour tout le monde quelqu'un aurait il une idée sur le parcours d'un arbre planaires juste une idée
merci

[millie]

Donc, je te redis ce que j'ai dis sur le chat :

Un arbre est un graphe acyclique et connexe. C'est forcement planaire (étant donné qu'il n'y a pas de cycle).
Mais il y a parfois une autre definition pour les arbres planaires qui n'a pas de rapport.



L'algorithme intuitif est le suivant (je considère un graphe non orienté) :

Code :

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

1
2
3
4
5
 
Visiter(Sommet S, Graphe G)
 traiter(S)
 Pour chaque successeur S' de S different de l'appelant faire
   visiter(S', G)

Il suffira d'appeler cette procédure avec un sommet quelconque de l'arbre.

Il te faudra changer la formulation : chaque successeur S' de S par l'implémentation que tu as effectivement retenue pour ton arbre.

Pour les curieux, c'est simplement un simple parcours de graphe sur lequel on a retiré tout ce qui était : coloration des sommets. Cette partie ne servant pas car un arbre est acyclique, et il n'y a aucun risque de retourner en arrière.

Il y a une autre possibilité :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
/*Version terminale récursive*/
Visiter(Ensemble E, Graphe G)
 Si E est vide
  Arreter
 Sinon
  S <- element(E) /*prend un élément de E quelconque*/
  traiter(S)
  E <- retirer(E, S) /*retire l'élément S de E*/
 /*Réunion des ensembles, aucun élément en double car c'est un arbre, il suffira de faire la concaténation des listes dans le cas où l'on représente
les successeurs par une liste*/
  E <- E union successeur(S) different de l'appelant faire
  visiter(E, G)

Si tu implémentes l'ensemble par une file, tu auras un parcours en largeur, si tu l'implémentes par une pile, tu auras un parcours en profondeur.
Cet algorithme a l'avantage d'être terminal récursif.

EDIT : J'avais oublie de preciser que les successeurs sont differents du pere, sinon on serait pas sorti de l'auberge. Pour voir les successeurs differents de l'appelant, il suffit de le passer en parametre en plus a la procedure (desole je suis sur un qwerty sans accents). Parfois, lorsque l'on parle de graphe planaire, les successeurs st implicitement differents du pere

[FrancisSourd]

Je confirme, les arbres sont bien planaires dans le sens habituel de planaire en théorie des graphes. Penses-tu à autre chose? Pourrais-tu nous montrer ce qu'est un arbre non planaire?

[millie]

Je confirme, les arbres sont bien planaires dans le sens habituel de planaire en théorie des graphes. Penses-tu à autre chose? Pourrais-tu nous montrer ce qu'est un arbre non planaire?

Tu parles a moi ? Dans le sens classique de planaire en théorie des graphes, tous les arbres sont planaires.

Mais en tappant "arbre planaire" dans google, on tombe sur une autre définition qui n'a pas trop de rapport. Cela correspond plutôt à la notion de structure arborescente. Chaque sommet a un unique père. Plusieurs ou pas de fils. Et il n'existe qu'un sommet n'ayant pas de père (la racine). Comme je le disais, il n'y a pas de rapport avec les graphes planaires.

Et si on déracine un arbre, on a une fôret

[FrancisSourd]

Tu parles a moi ?

Je posais plutôt la question @min@ pour savoir ce qu'elle (il?) entendait par "arbre planaire". En combinatoire, on parle aussi de "plane tree" qui sont plus ou moins des arbres ordonnés (chaque noeud a un numéro). Mais, de toute manière, cela ne change a priori pas les manières de parcourir ces arbres...

[@min@]

arbres qui n'est pas planaire et ben un arbre binaire .

ce qui est flous encore exemple dans un arbre binaire on passe de gauche (on parcours tout le sous arbres gauche) aprés tout le sous arbre droit avec une fonction RGD mais dans un arbre planaire supposant que c'est en largeur et niveau par niveau et de droite a gauche si je commence par la droite je met le noeud dans la téte de ma file aprés comment je passe au second noeud(frére) et le troisiéme et le quatriéme ainsi de suite apré je passe recursivement au second niveau et je refais le méme travail ??

[millie]

La notion que tu utilises pour parler de planairité est à mon avis équivalent à la notion d'arbre enraciné. Voir le cours de PRomu@ld : ici.

Un arbre binaire EST un arbre enraciné dont les sommets ont au maximum 2 fils.

aprés comment je passe au second noeud(frére)

Parce qu'il aura été mis dans la file par l'appel précédent lors de l'instruction :
E <- E UNION Successeurs(S)

[Patriarch24]

=> Un arbre planaire est un arbre sur lequel on a défini un ordre sur l'ensemble des fils de chaque noeud.
=> Un arbre enraciné est un arbre dans lequel l'un des sommets (appelé la racine) se distingue des autres.

Il n'y a pas de relation d'ordre de définie sur un arbre enraciné.