implementing tree datastructure

Why do you want a tree? What special properties of trees do you intend to use? The answers will give you enough information about what you need to implement, and how.

How you determine your data structure is really only dependent on what you want to do with it. For example, if you always have the root pointer accessable and you only want to be able insert,remove and traverse in some standard order (preorder, postorder, inorder) then the parent pointer isn't really necessary.

We really need more info on what you are going to use your tree for and some more concrete questions to be able to give you some advice.

thanks first of all.

AP: the language will be both C++ and Lua. for starting i need to mirror it, maybe C++ will go away later.

im rendering a number of meshes which are hierarchically dependend, like a tree. each nodes provides parameters for its children. if i remove a node, all the subnodes should be removed as well.

what i thought of meanwhile:

every node has a pointer to the first and to the last child.
every node has also a pointer to its previous and next sibling.

will this work?

A solution for this is to determine a maximum number of children. You then can create an array of node pointers. Then you can easily add every child of the current node in this array. Eventually you can add another pointer to your node class (or struct :-)) to point to the parent of this node. that way you can travel in both directions.


When you implemented this tree class, you can easily export it to Lua using LuaBind if you where using classes. Otherwise you should write direct C functions for this implementation around a node structure which you then can use as a Lua tree library or so.

Quote:

Original post by ehmdjii thanks first of all. AP: the language will be both C++ and Lua. for starting i need to mirror it, maybe C++ will go away later. im rendering a number of meshes which are hierarchically dependend, like a tree. each nodes provides parameters for its children. if i remove a node, all the subnodes should be removed as well. what i thought of meanwhile: every node has a pointer to the first and to the last child. every node has also a pointer to its previous and next sibling. will this work?

Sure, it sounds like your making some kind of transform tree/scene graph?. I have a thew suggestions if your writing this in C++ then you don't need to bother with most of them links as you can use the standard library containers to store children (say e.g. std::vector of child pointers).

it will be handy to keep a parent pointer if you decide to have nested bounding volumes where a parent node bounds it's children and it's children bounds it children etc and the root of the tree bounds the entire scene. You generally need to update them via upward pass from leaf all the way to root so a parent pointer helps here.

This is useful to quickly cull out branches that aren't in view note how-ever this alone isn't enough for a good, efficient culling system.

I also suggest you use reference counted smart pointers for the child container boost libraries provides excellent package of smart pointers. Also use pooled allocator for the child container of node pointers and use one for actual node types themselfs, boost also provides allocators some of which are STL compliant. E.g.:

#include <vector> // standard library dynamic array aka vector#include <boost/shared_ptr.hpp>#include <boost/pool/pool_alloc.hpp>....struct scene_node : public IAlloctor { // IAllocator is some custom pooled allocator                                      // that overloads new/new[] and                                     // delete/delete[] operators    // reference counted smart pointer   typedef boost::shared_ptr<scene_node> sn_ptr;   // pooled allocator of smart pointers   typedef boost::pool_allocator<sn_ptr> sn_ptr_alloc;   // child list   typedef std::vector< sn_ptr, sn_ptr_alloc > child_list;private:   scene_node* parent; // this can't be shared_ptr!, needs to be a weak reference      child_list kiddies;   //.....public:   //.....   void add_child(const sn_ptr& p) {      p->parent = this;      kiddies.push_back(p);   } // ....};

Another library that is also useful is the loki library.

You could also apply the composite design pattern, where only internal node types do child containment and you would have something like a transform group be a sub-type of some base composite type (internal, non-terminal node). here is a good introductory article on subject of scene graphs.

[Edited by - snk_kid on April 11, 2005 4:54:04 AM]

why dont you look into scene graphe

it will give you the what you need plus the flexibility. this is a good introduction.

http://www.gamedev.net/reference/programming/features/scenegraph/

thanks a lot!

the problem is since, i will probably drop the C++ version later in the project only the LUA one will remain, so i cant use STL and any other libraries.

yeah, it sure would be comfortable to just do .push_back() but it has to be done without. ;-)