Jump to content
  • Advertisement
Sign in to follow this  
HellRiZZer

Linear access of tree structure

This topic is 4766 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

Hi all, I've just wondering if there's a tree class that gives you an ability to access a tree in a linear manner. For example, I'd have a tree whose nodes can be accessed by indices like this:
        Root
          9   
   6      7      8 
 0   1  2   3  4   5

If there's no such a class, how it can be done for a tree structure? Thanks a lot.

Share this post


Link to post
Share on other sites
Advertisement
There's a data structure called a threaded binary tree, though it's usually used for infix traversals. Basically it's a binary tree that contains a linked list inside of it. So in addition to the left, right and parent pointers, each node has next and previous pointers. If you have a threaded binary tree when you add a new node, in addition to updating the left/right and parent nodes, you also insert the node into the linked list that threads the tree.

Share this post


Link to post
Share on other sites
HellRiZZer, if you are likely to have a very dense binary tree (ie leaf nodes are nearly always at only one or two depths), then you can implement the tree using at array. Let element 0 be root, and let the child of X be at indices (X*2)+1 and (X*2)+2, and the parent of X be at index (X-1)/2, rounded down.

Then, you can traverse the entire tree as you wondered like so...

1. Find the last element in the array which has data in it. This is the rightmost leaf in the deepest layer. Let a "row end" pointer and an "active" pointer refer to this element.
2. While this element is at an index which is NOT a power of two minus one (ie 1,3,7,15..), seek the "active" pointer to the previous element. Let a "row start" pointer point at this element as well.
3. If the "row start" pointer is at the root node, visit it and end.
4. While the "active" pointer is less than or equal to the "row end" pointer...
4a. Visit the node at the active pointer.
4b. Increment the active pointer.
5. Decrement the "row start" pointer, and let the "row end" pointer refer to this index.
6. While the the "row start" is not at either 0 or a power of two minus one (ie 1,3,7,15..), decrement it.
6. Let the "active" pointer point at the "row start" pointer, and go to (3).

It's obviously far more efficient to iterate in forward fashion; start at 0 and visit each element until you reach the last one.

Share this post


Link to post
Share on other sites
The problem is that I'm not using a binary tree, it's a tree of a structure:


class CTreeNode : public CDoubleList<CTreeNode>
{

public:
CTreeNode *m_pParent;
};



E.g a node can have as many children as it wants.

Thanks for the help all, but it seems I can't do it (or it's just too hard for me)

Share this post


Link to post
Share on other sites
std::set uses a red-black tree to store data;


std::set<Yourclass>::iterator i;
i++; <-- sequental tree access;

Share this post


Link to post
Share on other sites
A heap is ordered something like that (only the other way around, starting at the root, rather than the leaves), but you could access it either way. Of course, compared to "proper" tree structures, you lose a bit of flexibility.

Sounds a bit like a b+ tree to me, except they only have data in the leaves. But they do allow you to traverse the tree linearly.

Share this post


Link to post
Share on other sites
Finally, I've figured out how to do what I've asked you people for. I'll be posting a tutorial about it pretty soon relating to a custom PAK format. It's pretty tricky, but as soon as you understand the logic, you'd think "damn, how I couldn't think of it? It's so easy!" . :)

Thanks for you help and suggestions though everybody, I really appreciate it.

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.

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!