J'ai un arbre quelconque  
 
1
 2
  3
   4
 5
  6
  7
   
À partir d'un élément (5), je veux retrouver le précédent (4) et le suivant (6).
J'ai trouvé  
http://www.codeguru.com/Cpp/contro [...] .php/c645/
http://www.codeguru.com/Cpp/contro [...] .php/c637/
mais le code 'précédent' ne marche pas.
 
Cette méthode a-t-elle un nom ?
Ou trouver du code qui marche ?
 
//
 
edit :

Une autre façon de voir le problème - la sélection est 'Shop', j'appuie sur la flèche du bas, je dois sélectionner l'élément suivant, 'Second floor'. C'est pas aussi simple que de chopper le frère suivant car ici il faut remonter dans la hiérarchie. Comme dit pains-aux-raisins, ça revient à chopper l'élément suivant dans une liste qui représente l'arbre linéarisé.

(on me l'a dit c pas de moi)
 
en chainant tes nombres, cas en faisant que chaque noeuds aie une liste de ses prédécesseurs directs, et une liste de ses successeurs directs...

tu veux une structure d'arbre en C++ ou faire un arbre ?  
- si 1, bibliolinks C++
- si 2, tu peux courrir

Les nombres sont là pour l'exemple, il me faut un algo.

Je veux savoir si la méthode mise en lien a un nom, et savoir où trouver du code qui marche.

t'es sur qu'il te faut un arbre ? sinon ben tu commences par l'arbre binaire, ensuite tu rajoutes une relation d'ordre, etc

J'ai déjà l'arbre, il me faut la méthode pour trouver les éléments suivant & précédent.

ben tu remontes tes pointeurs ... toute façons suivant/précédent ça veut rien dire

Suivants & précédents comme flèche bas & huat dans la vue hiérarchique de l'explorateur windows.  
 
Quant à remonter les pointeurs, c'est pas très clair.

et ce que je t'ai donné comme méthode ???

Impossible de modifier la structure de mon arbre.  
 
Ce qu'il me manque, c'est le nom de la méthode donnée en lien et surtout une version qui marche.

IWH \o/
 
ça c'est du topicalacon !

L'algo le plus simple est de regarder non pas un noeud après, mais deux noeuds après lorsque tu fais ton parcours (peu importe lequel).
 
exemple :
si le noeud d'apres = noeud recherché, alors
   1/ noeud courant = noeud prédecesseur et  
   2/ noeud apres celui d'apres = noeud successeur.
 
un dessin !

Je recherche l'élément C et mon noeud courant est B.
Comme B.suivant = C, on a trouvé, alors B prédécesseur de C et
B.suivant.suivant = successeur de C.
 
Voilà !
 
edit : en pratique, faut que tu modifie ton algo de parcours au niveau de la comparaison de l'élément courant avec la valeur recherchée.

Je te suis pas, c'est l'algo de parcours qu'il me faut. Eg pour obtenir la node suivante, on prend le premier fils s'il existe. Sinon, le frère. Sinon, on remonte le parent jusqu'à trouver un frère. Bref, le nom de cette méthode (breadth first & co sont bien nommées, pourquoi pas celle-la ?) et surtout savoir si l'algo est bon.

1/ Je suppose que tu veux parler de l'algo de parcours deep first search (en profondeur d'abord).
2/ Parcourir un arbre reviens à le linéariser. Il existe plusieurs méthodes de linéarisation donc celle en 1/
3/ Pour l'algo DFS cité en 1/, voici un lien qui peut t'aider à l'implémenter dans sa version simple :
http://www.toutenligne.com/index.p [...] &menu=algo
A toi ensuite de l'adapter pour qu'il récupère également le précédesseur comme indiqué dans mon précédent post.
 
Good luck !
 
Edit : en se basant juste sur l'exemple de ton 1er post, c'est effectivement l'algo DFS qu'il te faut

Oui. Il me faut une fonction de linéarisation non récursive, ce que je suis incapable de trouver avec google.

Edit premier post pour la clarté. En fait, il me faut une fonction de linéarisation ... linéaire.

Tu peux substituer la récursivité par une gestion de pile pour en faire un algo itératif.
 
http://cermics.enpc.fr/polys/oap/node68.html

Pas besoin de pile pour que ça marche, cf le code 'next' en lien du premier post.
 
Enfin, y'a pas de nom pour cette méthode ?! Personne ne connait ? Ça me dépasse ...

Ok, c'est pas un pb d'algo que tu as, tu veux juste debugger ton programme C++.

Si, je veux connaitre le nom de l'algo qui permet de parcourir un arbre linéairement, sans pile.  
 

Au vu des pavés de code c++ que j'ai postés, c'est effectivement évident. Si c'est pour répondre ça, efface ton drapeau.

1/Le nom de l'algo est comme je l'ai plusieurs fois dis celui du parcours en profondeur d'abord (DFS en anglais)
2/D'un point de vue algorithmique, parcourir un arbre en profondeur sans récursivité et sans pile, ca n'existe pas.
3/De toute façon peu importe le nom de l'algo, tu as simplement un problème d'intégration de code. Des geeks en C++ (autres forums) seraient mieux placés que moi pour répondre.

Ce n'est pas ce que je veux. Des pages d'algos de parcours d'arbre, j'en ai bouffé un sacré paquet avant de poster ici. Si j'ai posé la question, c'est que je n'ai trouvé qu'une source incomplète sur ce qui m'intéresse précisément.
 

Cf le premier lien que j'ai filé, ça marche. Pas convaincu, essaye-le. Cf la façon de traiter les flèches haut/bas sur une représentation graphique d'un arbre, qui est exactement ce que je veux, qui s'apparente à un parcours linéaire de l'arbre, mais dont je n'arrive à trouver référence que sur un seul site.  
 

Le code que j'ai trouvé est en c++, il n'a rien de spécifique c++, mon projet n'est pas c++. Mon problème n'est pas c++, pas un problème de code, pas un problème de debug, juste un bête problème d'algo.

Reprenons calmement.
En examinant les bouts de code C++, on peut constater que les personnes font appel à des fonctions "magiques" qui doivent contenir de la récusivité ou gérer une pile --- eg GetParentItem().
En regardant le code pour le prédécesseur. Il aurait fallut écrire :
 

 

 
edit : ca marche ?

Non. Ces fonctions sont les bases de la manipulation d'un arbre, standardisées par le DOM http://www.w3.org/TR/1998/REC-DOM- [...] -core.html - pointeurs parentNode, firstChild, lastChild, previousSibling, nextSibling. Comme j'utilise le DOM pour mon projet, j'ai bêtement transcrit, ça marche.  
 
En fin de compte j'ai trouvé un truc suffisamment ressemblant dans la source mozilla http://lxr.mozilla.org/mozilla1.7/ [...] r.cpp#3368 , je vais me débrouiller avec ça.

Des fonctions de bases qui utilisent en interne de la récursivité ou de la gestion de pile.
 
edit:un habillage qui ne doit pas faire oublier que derrière, c'est pas linéaire (complexité algorithmique)

Non, ce sont les composants intrinsèques de la node. Si tu crois qu'il y a besoin de récursivité pour avoir un pointeur sur la node parent, les frères, les fils, tu n'as jamais implémenté d'arbre.  
 
(Oui, j'ai déjà implémenté un arbre, un DOM plus précisément, en c++, et aucun besoin de récursivité).

hmmm... et toi tu n'a jamais fait de parcours d'arbre...
 

?
 

L'implémentation est libre, tu peux donc ne pas garder de pointeurs sur les frères.  
 
Maintenant montre-moi du code qui choppe un frère, un parent, un fils avec de la récursivité ou gestion de pile. Je veux comprendre. Je n'ai jamais eu besoin de ça pour gérer mes arbres.

Si dans ton arbre tu n'a pas plein de pointeurs partout et que tu dois t'en contenter, tu fais comment ??
edit : sinon ton problème est résolu ?

Reprenons ton exemple avec juste parent et array fils, qui suffisent pour définir un arbre.  
 
node
{
 node parent;
 array fils;
}
 
(j'oublie la gestion d'erreur)
parentNode = node.parent
firstChild = node.fils[0];
lastChild = node.fils[node.fils.length-1]
nextSibling = trouver l'index idx de node dans node.parent.fils (simple boucle)
S'il est != de node.parent.fils.length-1, nextSibling = node.fils[idx+1], sinon nextSibling = null.
previousSibling = idem nextSibling, avec un -1.
 
Où est la récursivité, la gestion de pile ?

Mon code marche mais je n'ai toujours pas le nom de la méthode, donc non.

oui et maintenant tu dois faire un parcours en profondeur sur cet arbre... puisque c'est quand même de ca qu'on parle...

?

 
Pour définir un arbre seul les fils suffisent :
 
node
{
 array fils;
}
 

 
edit : définition d'un graphe par ses successeurs.

Non, juste trouver un index dans un tableau. Ce n'est ni récursif ni à pile.
 

Je n'ai pas le nom de la méthode, je sais pas si mon code est correct. Je considère pas ça comme résolu.
 

Effectivement. J'aurais du dire "arbre dans lequel tu peux te balader sans avoir une globale sur la racine". Dans ce cas-là tu auras effectivement un algo récursif pour chopper tes pointeurs. C'est aussi une implémentation complètement inefficace niveau temps parcours.