Algorithme Tree Traversal

Question

Mise à jour: J'ai trouvé plus d'un exemple de ce que je suis en train de retirer: Gestion hiérarchique Les données en MySQL . Je veux faire cela, mais en JavaScript parce que je construis une application qui prend dans les commentaires qui sont dans une structure hiérarchique, pour être plus précis reddit.com. Si vous avez l'extension Pretty JSON sur votre navigateur Web Chrome go to reddit et cliquez sur un commentaire de fils, puis ajouter .json à l'URL pour voir ce que je suis l'analyse syntaxique.
Je reçois les données JSON très bien, son analyse juste par les commentaires et en ajoutant le code HTML approprié pour montrer que sa nichée.
Des idées pour des solutions?

---

question VIEUX: Je travaille sur un programme et je suis venu à une partie que j'ai besoin de la logique avant d'écrire le code. Je prends des données qui est dans un format d'arbre, mais avec la possibilité de plusieurs enfants pour chaque nœud parent et le seul arbre est que je peux sembler trouver des données sur sont arbre de avec des poids ou de l'arbre où au plus chaque nœud a deux nœuds enfants. Donc, je suis en train de comprendre l'algorithme pour évaluer chaque nœud d'un arbre comme ceci:

startingParent[15] // [# of children]
    child1[0]
    child2[5]
       child2ch1[4]
       ...
       child2ch5[7]
    child3[32]
    ...
    child15[4]

Maintenant, quand j'essaie d'écrire comment mon algorithme fonctionnerait je finis par écrit imbriquée pour / while, mais je finis par écrire une boucle pour chaque niveau de la hauteur de l'arbre qui pour les données dynamiques et arbre de hauteur inconnue avec nombre inconnu d'enfants par nœud cela ne fonctionne pas. Je sais qu'à un moment donné j'ai appris à traverser un arbre comme celui-ci, mais son tout à fait me échapper en ce moment. Quelqu'un sait comment cela se fait en termes de boucles?

Answer 1

Si vous ne comptez pas utiliser la récursivité, vous avez besoin d'une structure de données auxiliaires. Une file d'attente vous donnera une parcours en largeur, alors qu'une pile vous donnera un parcours en profondeur d'abord. De toute façon, il semble à peu près comme ceci:

structure <- new stack (or queue)
push root onto structure
while structure is not empty
  node <- pop top off of structure
  visit(node)
  for each child of node
     push child onto structure
loop

Références Wikipédia

• Queue
• Stack

Answer 2

Utilisez récursion, pas de boucles.
recherche largeur d 'abord
profondeur d 'abord la recherche
Celles-ci devraient vous aider à démarrer avec ce que vous essayez d'accomplir

Answer 3

Just use recursion like

def travel(node):
    for child in node.childs:
        # Do something
        travel(child)

Answer 4

The simplest code for most tree traversal is usually recursive. For a multiway tree like yours, it's usually easiest to have a loop that looks at each pointer to a child, and calls itself with that node as the argument, for all the child nodes.