12.9.1. Composite-based Expression Tree¶

There is another approach that we can take to represent separate leaf and internal nodes, also using a virtual base class and separate node classes for the two types. This is to implement nodes using the Composite design pattern. This approach is noticeably different from the procedural approach in that the node classes themselves implement the functionality of traverse. Here is the implementation. Base class VarBinNode declares a member function traverse that each subclass must implement. Each subclass then implements its own appropriate behavior for its role in a traversal. The whole traversal process is called by invoking traverse on the root node, which in turn invokes traverse on its children.

   /** Base class: Composite */
   public interface VarBinNode {
     public boolean isLeaf();
     public void traverse();
   }

   /** Leaf node: Composite */
   public class VarLeafNode implements VarBinNode {
     private String operand;                 // Operand value

     VarLeafNode(String val) { operand = val; }
     public boolean isLeaf() { return true; }
     public String value() { return operand; }

     public void traverse() {
       Visit.VisitLeafNode(operand);
     }
   }

   /** Internal node: Composite */
   public class VarIntlNode implements VarBinNode { // Internal node
     private VarBinNode left;                // Left child
     private VarBinNode right;               // Right child
     private Character operator;             // Operator value

     VarIntlNode(Character op,
                        VarBinNode l, VarBinNode r)
       { operator = op; left = l; right = r; }
     public boolean isLeaf() { return false; }
     public VarBinNode leftchild() { return left; }
     public VarBinNode rightchild() { return right; }
     public Character value() { return operator; }

     public void traverse() {
       Visit.VisitInternalNode(operator);
       if (left != null) { left.traverse(); }
       if (right != null) { right.traverse(); }
     }
   }

   /** Preorder traversal */
   public static void traverse(VarBinNode rt) {
     if (rt != null) { rt.traverse(); }
   }

When comparing the composite implementation to the procedural approach, each has advantages and disadvantages. The non-composite approach does not require that the node classes know about the traverse function. With this approach, it is easy to add new methods to the tree class that do other traversals or other operations on nodes of the tree. However, we see that traverse in the non-composite approach does need to be familiar with each node subclass. Adding a new node subclass would therefore require modifications to the traverse function. In contrast, the composite approach requires that any new operation on the tree that requires a traversal also be implemented in the node subclasses. On the other hand, the composite approach avoids the need for the traverse function to know anything about the distinct abilities of the node subclasses. Those subclasses handle the responsibility of performing a traversal on themselves. A secondary benefit is that there is no need for traverse to explicitly enumerate all of the different node subclasses, directing appropriate action for each. With only two node classes this is a minor point. But if there were many such subclasses, this could become a bigger problem. A disadvantage is that the traversal operation must not be called on a NULL pointer, because there is no object to catch the call. This problem could be avoided by using a Flyweight to implement empty nodes. If the composite implementation is for a full tree, then it is unnecesary to explicitly check if the children are null.

Typically, the non-composite version would be preferred in this example if traverse is a member function of the tree class, and if the node subclasses are hidden from users of that tree class. On the other hand, if the nodes are objects that have meaning to users of the tree separate from their existence as nodes in the tree, then the composite version might be preferred because hiding the internal behavior of the nodes becomes more important.

Another advantage of the composite design is that implementing each node type’s functionality might be easier. This is because you can focus solely on the information passing and other behavior needed by this node type to do its job. This breaks down the complexity that many programmers feel overwhelmed by when dealing with complex information flows related to recursive processing.