Looping throught a binary tree?
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++
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.
And no, you most certainly do not need an array that copies the data from the tree.
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
Inorder traversal algorithm
Postorder traversal algorithm
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
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
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++
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++
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
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):
that might not be quite right (i just typed it now) but that''s the idea.
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.
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
Inorder
Postorder
Of course, there probably are errors, but I believe the algorithms to be going in the right direction.
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.
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]
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]
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
[ CodeDread ]
Let me know what you think.
Regards,
Jeff
[ CodeDread ]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement