Jump to content
  • Advertisement
Sign in to follow this  

Tree Traversing

This topic is 4314 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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).

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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().


void printBits(size_t val)
{
size_t numBits = sizeof(val) * 8;
size_t mask = 1u << (numBits-1);

for (size_t i = 0; i < numBits; i++)
{
printf((val & mask) ? "1" : "0");
mask >>= 1;
}
printf("\n");
}

//
// Solution 1: recursion
//
void printBitCombos(size_t initVal, size_t bitIndex)
{
size_t mask = 1u << bitIndex;

// set bit to '1' and print all values
initVal |= mask;
if (bitIndex > 0)
printBitCombos(initVal, bitIndex-1);
else if (bitIndex == 0)
printBits(initVal);

// set bit to '0' and print all values
initVal &= ~mask;
if (bitIndex > 0)
printBitCombos(initVal, bitIndex-1);
else if (bitIndex == 0)
printBits(initVal);
}


//
// Solution 2: simple and fast
//
void printBitCombos(size_t bitIndex)
{
size_t numCombos = 1u << (bitIndex+1);

for (size_t i = 0; i < numCombos; i++)
printBits(i);
}

int main(int argc, char **argv)
{
printBitCombos(0, 15)
printBitCombos(15);

return 0;
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!