announcements‎ > ‎

2016-04-20

posted Apr 20, 2016, 7:12 AM by Samuel Konstantinovich   [ updated Apr 20, 2016, 10:29 AM ]
Tomorrow After School is an AP review session!

HW1: Find AP multiple choice questions on the internet. Post on google classrooms. Decide with your classmates where the best sources are.  
HW2: Look at old AP free response questions... and their solutions.
2010 #1
2013 #2 
HW3: On Github, directory 12, you will have Thursday+Friday in class to work on this (+ some additions)

We want to make a Binary Search Tree:

BSTree<T extends Comparable<T>>


This means that the type parameter must support comparison with other instances of its own type, via the Comparable interface.

Like this:
public class Name implements Comparable<Name> {
   ...
   public int compareTo(Name n) { ... }
}

Start out with these operations: (ignore duplicates for now)

public void add(T value)
public String toString() ***
public boolean contains(T value)
public int getHeight()  //this can be linear for now.

toString can be really difficult, so we will stick with a pre-order traversal, that generates a tree as follows:
     a
   /   \   
   b     c
    \   /  
     f  e

a b _ f _ _ c e _ _ _   
This guarantees 2 children values per node, and _ represents null, so:

a b _ f _ _ c e _ _ _   
a is the root.
b is the first child of a
_ is the first child of b, since _ cannot have children the next character isn't part of _
f is the second child of b,
the next 2 _'s are part of f. now that F is complete and we know that b has 2 children, the next thing is the 2nd child of a.
etc.

Github directory 12:

public class BSTree<T extends comparable<T>>{
    private class Node{
T data;
Node left;
Node right;
// set/get: data/left/right


//real methods here
public int height(){ 
   return 0;
}
public void add(T value){
}
public String toString(){
   return "";
}
public boolean contains(T value){
   return false;
}
   
    }

    private Node root;

    //OUTER methods here are wrapper methods for the root
    public getHeight(){
//call the root's methods
//check for empty first!
return root.height();
    }

    public void add(T value){
//check for empty before you do things with root.
    }
    public String toString(){
//check for empty before you do things with root.
return "";
    }
    public boolean contains(T value){
//check for empty before you do things with root.
return false;
    }
}
Comments