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]
Printable View
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]
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.
Yes, there is indeed a simple algorithm for traversing any tree without recursion.
:DCode: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!).
This non-recursive loop "Visits" all children at level 1, then all children at level 2, etc....Code: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
You only need recursion if you need a formal "Pre-Order, PostOrder, or End-Order" traversal sequence...
Dr Memory :cool:
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