Jump to content
  • Advertisement

Archived

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

GeekPlusPlus

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.

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

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 this post


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


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
eh, i was close!

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

Share this post


Link to post
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


[ CodeDread ]

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

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!