Generalizing actions for a binary tree traversal?

Question

I'm trying to find a way that I could take a binary tree class and traverse through its nodes,
performing X amount of inline actions on each node without having to rewrite the same traversal code over and over again.
I'd imagine if Java allowed function pointers, this would be much simpler for me to figure out...

Basically, what I need is something like the following:

public class BinaryTreeNode {

    //...

    public void inOrderTraversalFrom(BinaryTreeNode node, /* ??? */ actions) {
        if(node.left != null)
            inOrderTraversalFrom(node.left);

        /* do something with "actions" here */

        if(node.right != null)
            inOrderTraversalFrom(node.right);
    }
}

... where actions could allow for different methods to be performed, taking in a different set of parameters depending on the type of action(s) to be performed on each node.

A good example of this would be a class which is meant to draw these nodes could be passed, accepting a Graphics object as one of it's parameters, versus a class which is meant to perform some other series of actions which wouldn't require a Graphics object as a parameter, but a completely different set of parameters instead.

How is this possible? What would be the most dynamic way to perform this?

Answer 1

One way to do it would be:

action could be an instance of a class that receives a Node and applies the Action to it:

public interface Action{
  public void apply(Node node){
  // To be done in the classes that will implement 
  // this interface. If it's a graphic-display of the nodes, the apply 
  // method will call draw(node.value), for example
  }
}

The line:

/* do something with "actions" here */

should be replaced with

action.apply(node);

The signature of the method should be changed to:

public void inOrderTraversalFrom(BinaryTreeNode node, Action action)

and the recursive call should be:

inOrderTraversalFrom(node.left, action);

Answer 2

I found a solution, though it might not be the best...

BinaryTreeNode.java:

public void inOrderTraversalFrom(BinaryTreeNode rootNode, BinaryTreeActions actions)
{
    if(rootNode.left != null)
        inOrderTraversalFrom(rootNode.left, actions);

    if(actions != null)
        actions.Perform(rootNode);

    if(rootNode.right != null)
        inOrderTraversalFrom(rootNode.right, actions);
}

BinaryTreeActions.java:

public interface BinaryTreeActions {
    public void Perform(BinaryTreeNode node);
}

BinaryTreeGraphicsActions.java:

public interface BinaryTreeGraphicsActions extends BinaryTreeActions {
    void DrawNode(BinaryTreeNode node, Graphics g);
}

BinaryTreeView.java:

private void DrawNodes(final Graphics graphics)
{
    BinaryTreeNode node = root;
    root.inOrderTraversalFrom(node, new BinaryTreeGraphicsActions() {
        @Override
        public void DrawNode(BinaryTreeNode node, Graphics g) {
            // draw the node
        }

        @Override
        public void Perform(BinaryTreeNode node) {
            DrawNode(node, graphics);
        }
    });
}

...and any time you need a new set of actions, you would create a new interface for it, following the same idea in BinaryTreeGraphicsActions and BinaryTreeView. This allows you to perform any set of actions, depending on the interface you have designed for them.

---

#EDIT : I accepted a similar answer after discovering there is no need for BinaryTreeGraphicsActions, since you can do the same inline code simply using BinaryTreeActions like so:

private void DrawNodes(final Graphics graphics)
{
    BinaryTreeNode node = root;
    root.inOrderTraversalFrom(node, new BinaryTreeActions() {
        @Override
        public void Perform(BinaryTreeNode node) {
            /* draw the node, using any local vars (providing they are final) */
        }
    });
}

Answer 3

Following solution is pretty similar to others suggested here. But with some design pattern icing if you are into these things.

The idea is to segregate not only actions but also traversal. This can be done with following 2 abstractions.

• BinaryTreeNodeTraversalStrategy
• BinaryTreeNodeVisitor

public interface Visitable<T extends Visitor> {

  public void accept(T visitor);
}

public interface Visitor<T extends Visitable> {

  public void visit(T visitable);
}

public interface BinaryTreeNode implements Visitable<BinaryTreeNodeVisitor> {

  public void accept(BinaryTreeNodeVisitor visitor);
}

public interface BinaryTreeNodeVisitor implements Visitor<BinaryTreeNode> {

  public void visit(BinaryTreeNode visitable);
}

public interface BinaryTreeNodeTraversalStrategy {

  public void traverse(BinaryTreeNode root);
}