Draw Expression Tree Assignment Assignment Three ����������� This assignment has two parts. The first part is to add code to the binary tree class BinaryTree.java �to draw the binary tree. The getDrawSize() method and the draw(Graphics g) methods must be implemented and �the InorderIterator class must be modified. The BinaryTreeNode class (an inner class of BinaryTree) has fields for the x and y coordinates of each node. The draw parameters and the coordinates are assigned as follows: � The diameter field is the diameter of the ovals that are drawn for each node. � The font size for drawing the name (number) of each node should be diameter also. � The x coordinate is the inorder sequence number of the node multiplied by a factor (for example 2*diameter works OK). � The y coordinate is the depth of the node multiplied by a factor (for example 4*diameter works OK). Draw the filled ovals at the (x, y) coordinates of each node. Lines from a node to each of its children must be drawn also. A way to do this is to do an inorder iteration of the tree to calculate the x and/or y values of each node and then do another iteration (possibly a preorder iteration) and draw the ovals and lines to the children. Lines must also be draw to null children. You can use BinaryTreeExample.java to test this part of the assignment. �������� For the second part of the assignment, you are to create an ExpressionTree class. The Expression Tree class extends the BinaryTree class.� See ExpressionTree.java for a guide. The class has a static method to construct an expression tree (see page 380-395 in the text) from an algebraic expression. The operators are the binary operators +, -, *, / and ^ (exponentiation) and the parenthesis operators, ( and ). The operands are non-negative integers and variables made up of single letters only. Methods to return the fully parenthesized infix notation of the expression, the prefix notation of the expression , the postfix notation of the expression and sample intermediate code of the expression as Strings are to be included in the ExpresstionTree class. The intermediate code statements are: Push operand { Push the operand on the Stack } Add { Pop the Stack into left, pop the Stack into right and push left + right } Sub { Pop the Stack into left, pop the Stack into right and push left - right } Mul { Pop the Stack into left, pop the Stack into right and push left * right } Div { Pop the Stack into left, pop the Stack into right and push left / right } Pow { Pop the Stack into left, pop the Stack into right and push left ^ right } Pop result { Pop the Stack into result } Operands can be a single letter variable or an integer. The algebraic expression to expression tree algorithm will be discussed in class. If there are errors in the expression then throw an exception. Use TestExpressionTree.java to test your implementations. Your output should be similar to: �
