Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-04-08 ExpressionTreeLab

posted Apr 8, 2019, 5:53 AM by Konstantinovich Samuel   [ updated Apr 8, 2019, 5:58 AM ]

Don't Forget your Practice Exam on paper! (for tomorrow)


If you are not able to take the exam Friday, speak to me in person tomorrow.


General Trees:

The height of a tree is minimally log n. Ideally we can maintain the minmum height.

To add a node the the runtime is O(height) which is between O(log n) O(n).


How do we print these trees?  (Hint: your toStrings from earlier)


Traversals!



Tree Traversals:
Runtime Complexity : O(n)
V=RootValue 
CL=Left Child
CR=Right Child)

There are 3 ways to traverse a binary tree. Much like traversing 
a list, we only care that we are able to touch every value. 
It doesnt matter if we print the elements or do any other 
operation with them/on them.

VCLCR  (Pre-Order traversal)

CLCRV   (Post-Order traveersal)

CLVCR   (In-Order traversal)


a pre-order traversal, of the following tree:
     a
   /   \   
   b     c
    \   / \ 
     f  e  x

a b _ f c e x   
(where _ signifies no child when a node has only 1 child)
The 1st _ is the left child of b







Classwork/Homework:

MKS22X-ExpressionTree

If you are not able to take the exam Friday, speak to me in person tomorrow.



Expression Tree:

MKS22X-ExpressionTree/ExpressionTree.java


Here is the ExpressionTree class, just drop in your methods 
from the classwork/homework, compile and run. 
Except you need to write the apply method.. which you probably have from your stack calc!



public class ExpressionTree{
  

  
  /*return the expression as an infix notation string with parenthesis*/
  /* The sample tree would be: "(3 + (2 * 10))"     */
  public String toString(){
    /*you are to write this method*/
    return "";
  }
  
  /*return the expression as a postfix notation string without parenthesis*/
  /* The sample tree would be: "3 2 10 * +"     */
  public String toStringPostfix(){
    /*you are to write this method*/
    return "";
  }
  
  /*return the expression as a prefix notation string without parenthesis*/
  /* The sample tree would be: "+ 3 * 2 10"     */
  
  public String toStringPrefix(){
    /*you are to write this method*/
    return "";
  }
    
  /*return the value of the specified expression tree*/
  public double evaluate(){
    /*you are to write this method*/
    return 0.0;
    }

  /*use the correct operator on both a and b, and return that value*/
  private double apply(char op, double a, double b){
    /*you are to write this method*/
    return 0.0;
}



  //If you are not able to take the exam Friday, speak to me in person tomorrow.
////////////////////ONLY EDIT ABOVE THIS LINE////////////////////


  
  private char op;
  private double value;
  private ExpressionTree left,right;
  
  /*TreeNodes are immutable, so no issues with linking them across multiple
  *  expressions. The can be constructed with a value, or operator and 2
  * sub-ExpressionTrees*/
  public ExpressionTree(double value){
    this.value = value;
    op = '~';
  }
  public ExpressionTree(char op,ExpressionTree l, ExpressionTree r){
    this.op = op;
    left = l;
    right = r;
  }
  
  public char getOp(){
    return op;
  }
  
  /* accessor method for Value, precondition is that isValue() is true.*/
  private double getValue(){
    return value;
  }
  /* accessor method for left, precondition is that isOp() is true.*/
  private ExpressionTree getLeft(){
    return left;
  }
  /* accessor method for right, precondition is that isOp() is true.*/
  private ExpressionTree getRight(){
    return right;
  }
  
  private boolean isOp(){
    return hasChildren();
  }
  private boolean isValue(){
    return !hasChildren();
  }
  
  private boolean hasChildren(){
    return left != null && right != null;
  }
  
  
  public static void main(String[] args){
    //ugly main sorry!
    ExpressionTree a = new ExpressionTree(4.0);
    ExpressionTree b = new ExpressionTree(2.0);

    ExpressionTree c = new ExpressionTree('+',a,b);
    System.out.println(c);
    System.out.println(c.toStringPostfix());
    System.out.println(c.toStringPrefix());
    System.out.println(c.evaluate());//6.0

    ExpressionTree d = new ExpressionTree('*',c,new ExpressionTree(3.5));
    System.out.println(d);
    System.out.println(d.toStringPostfix());
    System.out.println(d.toStringPrefix());
    System.out.println(d.evaluate());//21

    ExpressionTree ex = new ExpressionTree('-',d,new ExpressionTree(1.0));
    System.out.println(ex);
    System.out.println(ex.toStringPostfix());
    System.out.println(ex.toStringPrefix());
    System.out.println(ex.evaluate());//20

    ex = new ExpressionTree('+',new ExpressionTree(1.0),ex);
    System.out.println(ex);
    System.out.println(ex.toStringPostfix());
    System.out.println(ex.toStringPrefix());
    System.out.println(ex.evaluate());//21

    ex = new ExpressionTree('/',ex,new ExpressionTree(2.0));
    System.out.println(ex);
    System.out.println(ex.toStringPostfix());
    System.out.println(ex.toStringPrefix());
    System.out.println(ex.evaluate());//10.5   
  }
}
Comments