Package io.openml.gearbox.binarytree

Class TreeTraverser<T>

java.lang.Object
io.openml.gearbox.binarytree.TreeTraverser<T>
Type Parameters:
T - The type of value wrapped in the Visitable object to be visited by this visitor. For example, if the visitable class is ImmutableTreeNode, then the type of value is the return type of its ImmutableTreeNode.getValue() method
public class TreeTraverser<T> extends Object
A class responsible for the traversal logic, separated from the Visitor.

This class embodies the Gang of Four's original Visitor pattern, where the client is responsible for traversing the object structure.

This design cleanly separates the how (the traversal algorithm) from the what (the operation performed on a node). A user of the library can write a single Visitor implementation (the "what") and apply it to any traversal strategy provided by this class (the "how"), promoting maximum flexibility and code reuse.

For a detailed discussion of the architectural trade-offs of this approach compared to the combined visitor model, see the documentation for AbstractInOrderTraversalVisitor.

  • Constructor Details

    • TreeTraverser

      public TreeTraverser()

  • Method Details

    • traverseInOrder

      public void traverseInOrder(TreeNode<T> root, Visitor<T> visitor)
      Performs an iterative in-order traversal of the tree structure.

      At each node, it applies the given visitor by calling the node's Visitable.accept(Visitor) method.

      Compared with AbstractInOrderTraversalVisitor, this method assumes the visitor is visiting one node at a time which aligns strictly with the original Gang of Four's design pattern, according to which the Visitor pattern's primary responsibility is to define an operation for a set of classes without modifying them. The Visitor itself is "stateless" concerning the traversal.

      A client that uses the Visitor pattern with this method must create a concrete visitor object and then traverse the object structure, visiting each element with the visitor.

      This method separates the traversal algorithm from the visitor itself. The visitor's only job is to perform an operation on a single node, and a separate "traverser" or "iterator" class, i.e. TreeTraverser is responsible for navigating the tree and applying the visitor to each node. For example, we write our SummingVisitor just once. Then we can apply it using any traversal algorithm the TreeTraverser provides:

      1. traversePreOrder(TreeNode, Visitor)
      2. this method
      3. traversePostOrder(TreeNode, Visitor)
      The visitor (the what) and the traverser (the how) are independent and can be mixed and matched.

      Unlike AbstractInOrderTraversalVisitor, this method is highly flexible and promotes reuse. The user can, for example, write a single PrintingVisitor and apply it to any other traversal algorithms we provide (traversePreOrder(TreeNode, Visitor), traversePostOrder(TreeNode, Visitor), etc.). Conversely, they can write a new complex visitor (e.g., a SummingVisitor) and reuse all the existing traversal logic of this class. It allows the user to mix and match behaviors freely. In the end, having 2 visitors (PrintingVisitor, SummingVisitor) with pre-order, in-order, and post-order capabilities only requires client to maintain 2 classes of source code. It's a winner for flexibility.

      This method, however, requires slightly more setup from the client who must create two objects (the traverser and the visitor) and then orchestrate the call: traverser.traverseInOrder(root, visitor). It has more moving parts for the user to manage initially.

      Parameters:
      root - The root node of the tree to traverse
      visitor - The visitor to apply to each node in the structure

    • traversePreOrder

      public void traversePreOrder(TreeNode<T> root, Visitor<T> visitor)
      Performs an iterative pre-order traversal (Root, Left, Right).

      The algorithm uses a single stack. The core idea is to process the current node, then push its children onto the stack. To ensure the left child is processed before the right (since a stack is LIFO),the right child must be pushed onto the stack first.

      Parameters:
      root - The root node of the tree to traverse
      visitor - The visitor to apply to each node

    • traversePostOrder

      public void traversePostOrder(TreeNode<T> root, Visitor<T> visitor)
      Performs an iterative post-order traversal (Left, Right, Root).

      This algorithm cleverly uses two stacks to achieve the post-order sequence without recursion. The first loop produces an intermediate sequence of (Root, Right, Left) and pushes it onto a second stack. The second loop then pops from the second stack, which naturally reverses the intermediate sequence to produce the final desired order of (Left, Right, Root).

      Parameters:
      root - The root node of the tree to traverse.
      visitor - The visitor to apply to each node.