#### Archived

This topic is now archived and is closed to further replies.

# Looping throught a binary tree?

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

## Recommended Posts

Hey, I''ve got a binary tree all setup nice. And it''s great. Drops seach times enormously. But now i''d like to do something to ALL the data, so I want to loop through it... I''m wondering how you go about looping through a binary tree, or how you could set it up so it''d return each node one at a time. I don''t care about the order, just that it doesn''t repeat any, but hits them all. I thought of making an array to go along side it, and storing the key in the node. but then when I delete an entry from the tree i''d have to seach the array and delete that entry too and that ruins the whole point of the tree. =/ Hope someone can help - Newb Programmer: Geek++

##### Share on other sites
It''s called Binary Tree Traversal. The link is to a Google search that seems to have come up with quite a lot. Hopefully they''ll be helpful.

And no, you most certainly do not need an array that copies the data from the tree.

##### Share on other sites
Here are the three classical (recursive) tree traversal algorithms. Using a stack to keep track of the traversal state obviates the need for recursion (explicit stack vs. function call stack)

Preorder traversal algorithm
PREORDER(NODE):  VISIT(NODE)  if NODE.LEFT exists then PREORDER(NODE.LEFT)  if NODE.RIGHT exists then PREODER(NODE.RIGHT)

Inorder traversal algorithm
INORDER(NODE)  if NODE.LEFT exists then INORDER(NODE.LEFT)  VISIT(NODE)  if NODE.RIGHT exists then INORDER(NODE.RIGHT)

Postorder traversal algorithm
POSTORDER(NODE)  if NODE.LEFT exists then POSTORDER(NODE.LEFT)  if NODE.RIGHT exists then POSTORDER(NODE.RIGHT)  VISIT(NODE)

The VISIT function does whatever you want. If what you need is a (STL-compatible) tree iterator, I suggest you just go ahead and use the boost::graph library, it''s easier than writing your own.

“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.”
— Brian W. Kernighan

##### Share on other sites
Well I have it traversing like that using recursive functions. But now I need to get one thing at a time.

Something like a Tree.Begin() then Tree.Next() until it returns false.

My tree is auto balancing, I''d like not not give up on it too quickly. =)

- Newb Programmer: Geek++

##### Share on other sites
quote:
Original post by GeekPlusPlus
My tree is auto balancing, I''d like not not give up on it too quickly. =)

Look at the code for std::set (int the <set> header). Most implementations use a binary tree internally, and the set iterator, well, iterates in order over the set.

Of course, if what you need is an actual, working solution, you should just use one of std::set, std::map, std::multiset or std::multimap.

“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.”
— Brian W. Kernighan

##### Share on other sites
you could store a pointer to the current node in the tree class, and use that to return them one at a time.

for example (using the PREORDER method):
Node* Tree::Begin(void)  {  Node* tmp = RootNode;  if(tmp->Left)    CurrentNode = tmp->Left;  else if(tmp->Right)    CurrentNode = tmp->Right;  else    CurrentNode = 0;  return tmp;  };Node* Tree::Next(void)  {  Node* tmp = CurrentNode;  if(tmp->Left)    CurrentNode = tmp->Left;  else if(tmp->Right)    CurrentNode = tmp->Right;  else    CurrentNode = 0;  return tmp;  };

that might not be quite right (i just typed it now) but that''s the idea.

##### Share on other sites
Krez - if you don''t want to store the whole path from the root of the tree into the iterator, each node will need a pointer back to its parent (NULL for the root).

Here how I believe this will work.

Preorder
PreIter Tree::PreBegin(){   return PreIter(root);}PreIter Tree::PreEnd(){   return PreIter(NULL);}PreIter& PreIter::next(){   if(current->left)   {      current = current->left;      return *this;   }   // Look for a right branch, starting in the current node.   while(current && !current->right)       current = current->parent;   // If node is NULL, we''re done.   if(node)       current = current->right   return *this;}

Inorder
InIter Tree::InBegin(){   Node* node = root;   // start with the smallest node   while(node->left) node=node->left;   return InIter(node);}InIter Tree::InEnd(){   return InIt(NULL);}InItier& InIter::next(){   // If there is a right branch, the next node is the leftmost one it contains.   if(current->right)   {      current = current->right;      while(current->left) current = current->left;      return *this;   }   // If not, the next node is the closest one of which we are a left child.   Node* previous;   do   {      previous = current;      current = current->parent;      // Gone off the root. We''re done.      if(!current) return *this;    } while(previous == current->right);   return *this;}

Postorder
PostIter Tree::PostBegin(){   Node* node = root;   // Go as deep as possible, priority to the left.   while(node->left || node->right)   {     if(node->left) node = node->left;     else node = node->right;   }   return PostIter(node);}PostIter Tree::PostEnd(){   return PostIter(NULL);}PostIter& PostIter::next(){   Node* previous = current;   current = current->parent;   // Moving off the root, we would be done.   if(!current) return *this;   // Moving up, if there is no right branch, then we come from   // a left branch and have visited all children of this node   if(!current->right) return *this;   // Otherwise, check if we''re just back from visiting that branch   if(previous == current->right) return *this;   // If we haven''t, let''s explore it.   current = current->right;   // Go as deep as possible, priority to the left (same as begin)   while(node->left || node->right)   {     if(node->left) node = node->left;     else node = node->right;   }   return *this;}

Of course, there probably are errors, but I believe the algorithms to be going in the right direction.

##### Share on other sites
eh, i was close!

let''s pretend i said, "we leave that as an excercise to the reader"...

##### Share on other sites
Here's what I did for my binary sort tree. I created an iterator and reverse_iterator class within the tree class and provide functions:

begin() - returns an iterator pointing to the left-most item (i.e. since tree is sorted, it is the first in-order)
end() - special iterator signifying one past the right-most item
rbegin() - returns an iterator to the right-most item
rend() - special iterator signifying one past the left-most item

And of course iterators can be ++ and -- (PRE-increment ONLY! ). This requires that the iterator maintain a pointer to the tree object and hold its currently-pointed to element. Thus, the iterator is larger than a simple pointer, something I just couldn't seem to get around.

All in all it worked out nice though: I have the ability to go through all my elements in order (though it's not the fastest) or I can look-up an element using the standard binary search.

I think an empty tree object is the size of a pointer too...that was one of my goals.

Regards,
Jeff

[edited by - rypyr on June 4, 2004 3:19:23 PM]

##### Share on other sites
I decided to add my binary tree and documentation/tutorial to my website: http://www.codedread.com/code.php#BTree

Let me know what you think.

Regards,
Jeff

1. 1
2. 2
Rutin
20
3. 3
4. 4
frob
15
5. 5

• 10
• 9
• 14
• 9
• 33
• ### Forum Statistics

• Total Topics
632592
• Total Posts
3007295

×