Tree Traversing

Quote:

Original post by TheShadow I have a tree that i need to traverse... in C. I am already traversing it in a depth search way. But this tree is not a binary tree, it is a combinatory tree. But i now have a problem i need to avoid branches of trees that are the same as one i have traversed before. It is quite important to note that i am using trees of more than 16 variables (bits). This is a depiction of the current configuration of a 3 variable(bit) tree. *011 *111 *101 *111 *001 *011 111*000 *010 *110 *111 *100 *101 111 *110 111 As you can see there are three transitions that would not be executed... the transitions that are executed are the ones noted with a * How in the world could i make a fast way of doing this with a 16 variable tree and having about 20MB of ram for the program (i mean not eating ram by saving everything to ram).

I don't understand your graph. I have a few thoughts, but I need a clearer idea of what's going on before I can figure out if they're viable or not. Perhaps describing how you chose which things to put asteriscs by would help?

CM

The key to the graph is incremental transitions, not straight combinations.

001 to 011 is different than 010 to 011.

If you dont want to use recursion to traverse the tree, then you will need a queue and a while loop to traverse all branches only once.

create a queue.

add root node to queue.

while queue not empty
temp = queue front
pop queue
process temp
if temp has children, add to queue (the order here depends on how you want to traverse)
loop

If you arent traversing in an ordered manner you might want to consider marking each node "visited" as you traverse the tree and reset it when you are done.

It is quite possible to traverse a tree structure without a queue and without recursion if you set the datastructure up so each node knows its own position in the list of nodes above. When moving down, take the leftmost node. When moving up, if coming from the rightmost node move up again. If not, go down the node to the right of the one you're coming from.

Quote:

Original post by Wiggin It is quite possible to traverse a tree structure without a queue and without recursion if you set the datastructure up so each node knows its own position in the list of nodes above. When moving down, take the leftmost node. When moving up, if coming from the rightmost node move up again. If not, go down the node to the right of the one you're coming from.

There are different methods of traversing a tree which depend on that task you are trying to accomplish by doing so. You can traverse in-order, post-order, or pre-order or some custom method if you want to access the nodes in a certain order, thus your method may or may not be a solution to the problem at hand.

That said, yes it is possible for nodes to keep track of their position (although sometimes its not necessary if you implemented the tree structure using an array as opposed to strictly pointers which *may*, depending on implementation, require a little more in terms of keeping track of position).

When you say you "need to avoid branches of trees that are the same as one i have traversed before" do you mean branches that start with an already performed transition or the entire branch needs to be a duplicate? If it's the former then simply storing the transitions you've already performed in a sorted dynamically sized array could be feasible if you don't have a ridiculously large tree.

If it's the later perhaps you could search for duplicate branches on insertion (although this will make insertions considerably more complicated, and slower) and make a reference from one branch to another instead of storing the duplicate (ie. use an acyclic graph instead of a tree). That way you could keep a flag on each node to indicate whether it's branch has been traversed.

I think I understand why you drew it the way you drew it. But I'm not certain I understand why each node is what it is. From what I'm gathering, no matter where it occurs in the three a certain node will always have the same children. 001 will always be followed by 011 and 101. Is this accurate? If so, then the most obvious solution to me is to only have one copy of each combination, and store references to it in all the necessary places. Then give the conbination a 'visited' flag that you set the first time you encounter it. If you encounter a node with its visited flag set, you know you can stop your travels and unwind a few levels.

CM

I could be over simplifying the solution, but if you simply need to run through all the permutations of 16 bits, then here are two solutions. Simply substitute your function in for where you see printBits().