Expression Trees and Tree Traversals

Introduction

Any arithmetic expression can be represented as a tree structure where the internal nodes are operators and the leaf nodes are numbers. For example, the expression \(((7.0 \times 2.0) - (8.0 \div 2.0))\) can be represented with the following tree:

In this lab you will complete the implementation of a binary tree that represents mathematical expressions in this way. This implementation will provide functionality for evaluating expressions and formatting them in prefix, postfix or infix notation.

Starter Code

Before you start coding, carefully read each of the following files to make sure you understand their roles.

• Operator.java - Enumerated type representing the set of operators.
• ExpressionNode.java - Abstract superclass for expression nodes.
• OperandNode.java - Class representing operands (leaves) in an expression tree.
• OperatorNode.java - (8pts) Class representing operators (internal nodes) in an expression tree. UNFINISHED!
• ExpressionDriver.java - Simple test driver for executing expression tree methods.
• PrefixParser.java - (2pts) Class for converting postfix expressions into expression trees. UNFINISHED!

Object Oriented Traversals

Our textbook provides the following psuedocode for in-order traversal:

PrintInorder(node) {
  if (node is null)
      return

  PrintInorder(node⇢left)
  Print node
  PrintInorder(node⇢right)
}

In this code, the traversal is been implemented as a method in some separate class that is passed a reference to a root node. As an alternative, it is possible to implement a tree as a recursive data structure without a separate class to handle the traversals. In this approach the node is the tree, and all of the functionality is implemented through methods of the node class. Our ExpressionNode class will be organized in this way. Under this approach, a preorder traversal might look like the following:

class Leaf extends Node {

  public void inorder() {
    visit();
  }
  
}

class InternalNode extends Node {

  public void inorder() {
    left().inorder();    // Process all nodes in left
    visit();             // Process root node
    right().inorder();   // Process all nodes in right
  }
  
}

It may seem odd to see a recursive method with no (apparent) arguments. In this case the argument is implicit. Since the recursive calls are executed on different objects, it is the object this that changes from one call to the next.

Note that the methods above will only work for full binary trees: it assumes that every node is either a leaf, or contains two valid children. Our expression trees will necessarily be full because every operation must have exactly two operands.

Submission

Submit OperatorNode.java and PrefixParser.java through Gradescope.