Tree traversal without recursion?

[sbasak]

Is it possible to traverse (ie visiting every node) a tree without using recursion? If yes, could you please outline the algorithm?

[sorry I inadvertently posted it twice]

[galway]

Yes, depending on how you store your tree, and what it looks like. If your tree is trivial then you can simply loop through all the nodes simply moving to the next node at the end of the loop.

If your tree has parent pointers and some kind of variable to indicate if it has been visited then you can first go to the head node check it visited then set your current node variable to it's first child that isn't checked visited. Now loop and do the same again. If there is no unvisited child nodes set the current node to the parent node. If there is no parent node you are done.

If your storing your tree in some kind of array or predefined storage space you can simply loop through every memory block in that space.

If you have a node datastructure with simple pointers to all the children you can do it using a stack. This really isn't a lot different from recursion it is just that you are keeping your own stack. To do this where you would normally recurse simply push the old node onto the stack and set the current node to the first child node then loop. When you collapse pop the node of the stack and make it current then continue until you have visitted all it's nodes. You will actually need a second stack to keep track of the child node number, or a visited variable in your datastructure.

So short answer is yes, if you setup your tree right.

[MathImagics]

Yes, there is indeed a simple algorithm for traversing any tree without recursion.

     for i = 1 to TreeView.Nodes.Count
          Visit TreeView.Nodes(i)
          next

Of course that's hardly a generic solution! But seriously, there is a generic solution too. Let's say we have a tree with N nodes, and we know the Root node, R, and that given any node, we can iterate its children (a quite reasonable assumption!).

      Dim  NodeList(N), Children(N)

     NC = 1
     NodeList(1) = Root

     Do
         NV = NC
         NC = 0
         For i = 1 to NV
              Visit  NodeList(i)
              for each Child of NodeList(i)
                   NC = NC + 1
                   Children(NC) = Child of NodeList(i)
                   Next
              Next
         If NC = 0 Then Exit Do  ' we've finished
         '
         ' now just copy Children back to NodeList
         ' and keep going
        for j = 1 to NC
             Nodelist(j) = Children(j)
             Next
        Loop

This non-recursive loop "Visits" all children at level 1, then all children at level 2, etc....

You only need recursion if you need a formal "Pre-Order, PostOrder, or End-Order" traversal sequence...


Dr Memory


You start with a list of root nodes, and add all children to a list of "Nodes I should visit". Then you iterate through this list, adding all the child nodes to the list