• 12
• 12
• 9
• 10
• 13

# Iterating through a Tree Structure

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

## Recommended Posts

##### Share on other sites
Hi,

Well, to be honest you do have me a bit stumped on your explanation. What I think you're wanting to do is traverse a tree breadth-first?

I had to make use of trees the other day. I was required to traverse them breadth-first, and one method I thought of was using Queues.

//Ptr would be a pointer to the root node of the tree.void TraverseTreeBreadthFirst(Tree *ptr){  // Temp Queue  Queue queue;  // Temp Ptr holder for Tree  Tree *traverse;  if (ptr == NULL) //Check data exists in parent    return;    queue.create();  queue.push( tree );   //Push a tree pointer onto Queue  while ( !queue.IsEmpty() ) {    traverse = queue.front();   //Current node we're working with    //Visit the left node first if it exists    if (traverse->leftTree != NULL)      queue.push( traverse->leftTree );    //Now visit the right node if it exists    if (traverse->rightTree != NULL)      queue.push( traverse->rightTree );  }  //Empty the queue  queue.empty();}

I'm just thinking, you could easily do it using a stack; although, a queue would bit much easier. I hope I'm on the right track on what you're looking for.

Anyways...Later,

GCS584

##### Share on other sites
Yep, I suck at detailed explanations.. Anyway, here's how my AllocTree might look if it were charted on paper at some point:

Damned formatting...  Nothing works for me..  No ASCII art here, I fear.

Not an even tree, by any means.. What I'm wanting is a mtheod that would work something like an iterator, ie. you would call it, and it would return the next node, you would call it again, it would return the node after that, etc. I like your idea, to push every key onto a queue, and then just pop them off as necessary. But wouldn't this have a significant performance problem, were I to call this method quite often (as would be the case, since it's my memory allocator), seeing as it creates a queue, fills it, and destroyes it every call? Or perhaps I'll simply scrap the tree, and implement the memory management some other way.. Anyway, thanks!

##### Share on other sites
So you're asking about how to perform an in-order binary tree iteration non-recursively, right? This is far from impossible, although you'll need to keep track of the parent nodes but in return the iterator only needs to store the current node.

The algorithm then takes one node as input and tries to find the next one.
If the original node has a right child then either it or it's leftmost grandchild must be the node we seek. Otherwise we have to find the first grandparent of the original node which has the previous child on the left side.

Here's a sample implementation in C.
struct node { node *left, *right, *parent };node *iterate(node *p) { node *next, *prev; next = p->right; if(next) {  do {   p = next;   next = p->left;  } while(next); } else {  do {   prev = p;   p = p->parent;  } while(p->left != prev); } return p;}

##### Share on other sites
I propose 3 options.
Depth first traversal maintaining an explicit stack.
Parent pointers in your nodes and an algorithm for stepping through the nodes in order.

In many cases recursively traversing a tree is just fine though, and would be preferable when possible I think.

##### Share on other sites
Okay folks, thanks for the input, and sorry for the belated reply.. Anyway, I did some more thinking, and ended using this solution:

The AllocTree has a std::vector of AllocTree::Keys, the node registry. Every time a Key is split, it is removed from the node registry, and it's 2 children are added. Also, when a node is made valid, it is removed from the registry. This way nodes manage themselves, the AllocTree doesn't have to worry about what is valid and what isn't, whether it has children or not, etc.

Now, when you wish to iterate through the available open nodes, you can simply iterate through the node registry. Although you should never really be going manually through the registry, which is why I also made a spate of utility functions available such as SmallestLargerThen() and so on.

Again, thanks for the help people, I appreciate it!