7

I've been asked a theoretical design question with an eye upon the GoF patterns.:

"Given a design for a tree using a standard visitor pattern, how would your design look to allow a user to choose between om pre-order, in-order or post-order traversals?"

I'm thinkin of just letting the visitor be, but give the traversal over to an Iterator object following the Iterator Pattern.

The idea would be to implement 3 iterators that enable the desired traversal. They have an interface and the Visitor only needs to interact with this interface, giving itself as an argument to the iterator which provides traversal. The user can choose which iterator to use when giving one to the visitor.

Does this sound like an elegant solution? Any better ideas?

11

One thing about Visitor Patterns is misconception, that it is somehow tied to tree-like structure. Which is quite wrong. The question sounds as if it was doing just that. So first thing would be fixing this misconception. And then I would exactly like you said. Create 3 different iterators one for each type of traversal.

But this depends on complexity of the tree. If each node has same specified collection of children, then it is easy. The problems start when different types of nodes have different structure of children. Then visitor starts making sense. But the different types of traversal order stop making a sense, because they only work for n-arry trees, not for trees with arbitrary types of children in each node.

  • 3
    Pre-order and post-order work with any number of children. The problematic order is the in-order. When do you visit the current node if you have 3 children? – Olivier Jacot-Descombes Sep 23 '15 at 20:07
5

Maybe I'm missing something but don't you simply need different visitors for each of the traversal types, PreOrderTreeVisitor, InOrderTreeVisitor, PostOrderTreeVisitor with the visit method specific to the type of traversal. Probably you want them to take some action that could be applied to a node so that they, in effect, become the iterators over the tree.

interface ITreeVisitor {
   void visit(ITreeNode node);
}

interface ITreeNode {
   ITreeNode getLeft();
   ITreeNode getRight();
   int getValue();
   void accept(ITreeVisitor visitor);
}

interface IAction {
   void do(ITreeNode);
}

class TreeNode implements ITreeNode {
   ...
   public void accept(ITreeVisitor vistor) {
      visitor.visit(this);
   }
}

class PreOrderTreeVisitor implements ITreeVisitor {

   private IAction action;

   public PreOrderTreeVisitor(IAction action) {
        this.action = action;
   }

   public void visit(ITreeNode node) {

       action.do(node);

       ITreeNode left = node.getLeft();
       if (left != null) left.accept(this);

       ITreeNode right = node.getRight();
       if (right != null) right.accept(this);
   }
}
  • Isn't that visitor impl in-order? – TWiStErRob Jun 15 '16 at 8:33
  • @TWiStErRob nice catch, fixed. – tvanfosson Jun 15 '16 at 13:47
  • 1
    what's if traverse type depends on node kind? – Puchacz Dec 27 '16 at 14:53

protected by gnat Nov 30 '17 at 15:03

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.