2

Assume you have a generic k-ary tree like this one or this one

Repeating the latter here:

template <typename T>
struct TreeNode
{
  T* DATA ; // data of type T to be stored at this TreeNode

  vector< TreeNode<T>* > children ;

  void insert( T* newData ) ;

  // runs f on this and all children of this
  void preorder( function<void (T*)> f )
  {
    f( this->DATA ) ; // exec f on this
    for( int i = 0 ; i < children.size(); i++ )
      children[i]->preorder( f ) ; // exec f on each child
  }

} ;

template <typename T>
struct Tree
{
  TreeNode<T>* root;

  // TREE LEVEL functions
  void clear() { delete root ; root=0; }

  void insert( T* data ) { if(root)root->insert(data); } 
} ;

Now normally, you have pre-order and post-order traversals as recursive member functions of TreeNode as shown above. But say you don't want to be passing functions around, you want to visit each node in the tree from outside the class (ie just given a Tree object).

How can you do it?

Community
  • 1
  • 1
bobobobo
  • 64,917
  • 62
  • 258
  • 363
  • Hi I am trying to implement k-array tree whose output is in the form of adjacent matrix using Java. Input parameters are k=number of child for each node and d= depth of tree. given this parameter I am to generate adjacent matrix of the tree. I saw github and was not able to follow.can you please guide me to implement this? – Learner Jul 24 '13 at 11:10

2 Answers2

3

I would approach this by defining a PreorderIterator class that maintained state about where it was in the traversal. It would have methods for returning the current node and for advancing one step in the traversal.

You would have to be careful if the tree structure could mutate during the life of the iterator. Perhaps the tree could maintain a modification count; the iterator could capture the count at the start and check for changes at each access (and throwing an exception if it found one).

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • I thought about that, but doesn't that mean I have to maintain a `parent` node for each `TreeNode`? – bobobobo Mar 05 '13 at 22:09
  • 2
    @bobobobo - The iterator could be implemented with a stack of the current path (and current index at each level of the path). That would dispense with having to keep parent pointers in the tree itself. – Ted Hopp Mar 05 '13 at 22:12
2

One easy approach is to load the tree into a list and then walk the list when you need. The list would only be a list of pointers and therefore not that expensive. To do that you would use a modified version of the trie traversal algorithm:

void traverse(Node n){
  if(null == n) return;

  for( Node c: n.children){
    visit( c );
    traverse( c );
  }
}

You would use the visit to actually load your list. So something like 

List<Node> getListToIterate(Node n){
   List<Node> result = new ArrayList<Node>();
   traverse(n,resutl);
   return result;
}

void traverse(Node n, List list){
  if(null == n) return;

  for( Node c: n.children){
    list.add( c );
    traverse( c );
  }

}

Also, if you decide, you can wrap this algorithm in a TreeIterator class that would track where you are in the list.

kasavbere
  • 5,873
  • 14
  • 49
  • 72
  • So you are suggesting __flatten__ the tree into a list, then traverse that. If the tree is small, then this _flattening_ operation isn't that expensive -- it is even cheaper if the tree doesn't change often – bobobobo Mar 06 '13 at 17:19
  • That is exactly correct. Another aspect of `iterators` that may or may not be important to your case, is immutability. So that during iteration, you don't allow the underlying structure to change. If immutability is important to you, there are many creative ways where the list is very handy. For example, you can allow insertion into the underlying tree after the `flattening` phase of your iterator function. These are of course design optimizations that you will have to creatively think through. Basically, the list gives you a great deal of power; how you use it is based on your specific needs. – kasavbere Mar 06 '13 at 17:52