Sign in to follow this  

Question for General Trees

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

I am trying to implement the iterator for a general tree but I am stuck on the concept for it. Its not a 1D transversal like a list. So can anyone suggest a method to create some type of iterator for a general trees. For example, I would use an iterator in general tree in this function :
boolean isRoot(TreeIterator pos);
boolean isLeaf(TreeIterator pos);
boolean hasParent(TreeIterator pos);	
boolean hasAnyChild(TreeIterator pos);
I am just looking to brainstorm first. Thanks

Share this post


Link to post
Share on other sites
Tree traversals.

Those functions likely don't actually require traversals though. isRoot and hasParent are basically the same thing and trivial to implement if your tree nodes have a parent pointer. Similarly isLeaf and hasAnyChild are trivial just by looking at the node directly.

Share this post


Link to post
Share on other sites
So usually we do not provide an iterator interface for general trees?

If not then can you suggest a way to give each node a relative position, so that the user can for example( a bad one) do something like this :


Position currPos = someNodeInMiddleOfTree();
while(!isRoot(currPos)){
currPos = currPos.parent();
}


Share this post


Link to post
Share on other sites
As Anon Mike's link pointed out, there are several ways to traverse a tree.

Tree traversal can be implemented as a 1D iterator.

You can go depth-first (top to bottom) in pre-fix, in-fix, or post-fix order, or you can go breadth-first (level 0, level 1, level 2...)


Consider that the C++ Standard Library's map and set families are designed and typically implemented as trees, and the iterators use in-order traversal. (They can also be implemented as heaps, which can help with some memory concerns but with a corresponding speed cost.)




The whole point of an iterator is that you don't care what operation is applied. You simply increment the iterator and you are at the next one, until you are done.

Tree navigation is better accomplished through an interface similar to what you are providing. I'd go more along the lines of:


template <typename value, typename compare = less<value> >
class TreeNode {

TreeNode* Parent();

size_t NumChildren();
TreeNode* GetChild(int n);

bool IsHeap(); // Does this satisfy the heap properties?
bool IsSorted(); // Are the children sorted?
bool SwapChild( int child, TreeNode* replacement); // For balancing and replacement

void* GetTreeData(); // Return arbitrary data maintained by the tree
void SetTreeData(void*); // Maintain arbitrary data maintained by the tree

/* ... lots more, including how to actually get and set the value,
the various constructors and destructors, const editions of the above,
and a bunch of typedefs exposed for your end user ... */



The root is a node with NULL parent.
A leaf will have zero children.

Boolean query functions ("Is this the root?") are not very useful from an interface perspective. It is best to provide access rather than an existential check, unless there is a significant performance cost difference.

There are a few other additions I would put on there to make it general purpose. I would give the tree a comparison function to help in sorting the tree. The other functions allow you to more easily use the nodes in sorted trees, balanced trees, and self-balancing trees.


Edit: Source tags are our friends.

Share this post


Link to post
Share on other sites
Oh I see. I'll give the in-order a try. One more question. For this function :

someReturnType root(); //returns the root of the tree


What do you think the someReturnType should be. It could be an iterator to the
root, I guess, or it could be some type of Position interface. What do you think?

Share this post


Link to post
Share on other sites
Quote:
Original post by Concentrate
someReturnType root(); //returns the root of the tree
Be careful when mixing the container with the contents.

A tree is composed of nodes, so the root node of a tree makes sense. The container can have a node that it considers the root.

A node, however, does not necessarily know about the tree that contains it. I don't see any requirement that a node be part of a tree. A node could be a stand-alone data object.


Making the contents know about the container is a significant design decision.



You could have the container point back to the tree, then you can query the tree and ask it for the root.

Choosing to make individual nodes point back to the tree that contains them is a design choice. There are pros and cons.

It introduces a cost in size, 4+ bytes per node. It is not much, but it is certainly something. It introduces a cost in performance: setting the pointers, validating that operations within a tree stay inside that tree, clearing the pointers when removing from the tree, and more. It may add some benefits in terms of validations of operations by ensuring you don't accidentally mix trees. It might complicate some later decisions, perhaps if you want to create a subtree or extract a subtree off to it's own separate tree, or merge an existing tree under a node on another.



You can keep the knowledge outside the node by keeping it as an outside function. A simple function can loop on the parent until the parent is NULL --- but that would fail if you have cycles. It would be up to the class user to make sure it is an acyclic tree. You could add a parameter to limit the tree depth to help detect the situation. This has nothing to do with nodes themselves.




Deciding if the benefit is worth the cost is a decision you get to make.

Share this post


Link to post
Share on other sites

This topic is 2845 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this