C++ design question on traversing binary trees

Question

I have a binary tree T which I would like to copy to another tree.

Suppose I have a visit method that gets evaluated at every node:

struct visit 
{
 virtual void operator() (node* n)=0;

};

and I have a visitor algorithm

void visitor(node* t, visit& v)
{
//do a preorder traversal using stack or recursion
 if (!t) return;
 v(t);
 visitor(t->left, v);
 visitor(t->right, v);

}

I have 2 questions:

1. I settled on using the functor based approach because I see that boost graph does this (vertex visitors). Also I tend to repeat the same code to traverse the tree and do different things at each node. Is this a good design to get rid of duplicated code? What other alternative designs are there?
2. How do I use this to create a new binary tree from an existing one? I can keep a stack on the visit functor if I want, but it gets tied to the algorithm in visitor.
3. How would I incorporate postorder traversals here ? Another functor class?

Answer 1

1. Subclass the visitor and provide different visitors for each individual task, and merge like (or related) tasks into the same visitor. The best approach depends heavily on what you are attempting to do.
2. A visitor can construct a different tree. As it visits nodes, it builds the new node copies and links them in the "correct" order.
3. You rewrite the order in which the nodes are visited.

A visitor is a technique. It looks like you've confused the technique with a particular solution. Using a visitor means that some navigation services are provided by the data structure which will communicate with an external object (the visitor) by call-back.

Answer 2

3: Create an additional method for each type of traversal you want to do and rearrange the visitor calls:

void preorder_visitor(node* t, visit& v)
{
 if (!t) return;
 v(t);
 visitor(t->left, v);
 visitor(t->right, v);
}

void postorder_visitor(node* t, visit& v)
{
 if (!t) return;
 visitor(t->left, v);
 visitor(t->right, v);
 v(t);
}