boolean isRoot(TreeIterator pos);
boolean isLeaf(TreeIterator pos);
boolean hasParent(TreeIterator pos);
boolean hasAnyChild(TreeIterator pos);
Question for General Trees
Author
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 :
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.
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.
Author
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 :
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();}
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:
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.
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.
Author
Oh I see. I'll give the in-order a try. One more question. For this function :
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?
someReturnType root(); //returns the root of the treeWhat 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?
Quote:Original post by ConcentrateBe careful when mixing the container with the contents.
someReturnType root(); //returns the root of the tree
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
