• Object Oriented Programming is the typical programming paradigm for software d
ID: 3715710 • Letter: #
Question
• Object Oriented Programming is the typical programming paradigm for software development • Data is typically stored in Objects. • This is outside the scope of this class to discuss how to determine keys of objects, but we can find some way so that each object has a unique key o We use this key to store and look up the object, then query the object for the data we want o This data is typically called satellite data • Thus we will be creating a binary search tree that has <Key, Value> pairs • We will then be adding appropriate Junit tests to test the program.
Definition: A Binary Search Tree (BST) is a binary tree where each node has a Comparable key (and associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in the node’s right subtree. (Algorithms 4th edition, Sedgwick and Wayne)
Definition: A leaf node is a node at that lowest level of the tree and has no children. • That is, starting with the Root Node of the tree, any node’s key to the left of the root is smaller than the root’s key, and any node’s key to the right of the root is larger than the root’s key. • This property holds for each node in the tree
• We will be using Characters for values and their ASCII value as keys • We will not be implementing the full functionality of a typical Binary Search Tree • See the following BST API on next page: o Notice in the class definition we are defining our first class with generics o For the Key, we are putting the restriction on the Key that it must implement the Comparable interface o To be able to compare objects with each other in their natural ordering, we implement the Comparable interface ? See Java documentation on comparable interface https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html ? We can use the compareTo method to determine which the direction the object should move down the tree o An object can be typed as any interface it implements, thus we will have a compile time error if we try to instantiate a BST with a key that does not implement the Comparable interface o See the following tree traversal Wikipedia page for the walk method https://en.wikipedia.org/wiki/Tree_traversal ? To implement a walk, you recure on the left subtree until there are no children, then recure on the right subtree until no children ? Were to handle the current node in the two recursion branches determines the order of the traversal/walk • Note: Trees are almost always implemented with recursion because it is very natural to do
public class BST<Key, extends Comparable<Key>, Value> {
private Node root; // inner Node class // note: an outer class has direct access to values in an inner class private class Node { private Key key; private Value value; private Node lChild; // left child private Node rChild; // right child
// number of nodes at this subtree // the value of N for the root will be # of nodes in entire tree // the value of N for a leaf node would be 1 private int N; public Node (Key key, Value val, int N) { } } public int size() { } // returns # of nodes in the tree
// returns the value associated with they key // returns null if the key is not in the tree public Value get(Key key) { }
public void put(Value val, Key key) { } // inserts the key value pair into the tree
// performs an in order walk of the tree printing the values public void walk() { }
// Returns a pre-order, post-order, and in-order walk of the tree printing the values public String toString() { }
// returns true is this tree (using root node) is exactly same as another BST, return false otherwise. public boolean isEqual(BST another) { }
// here are some of the test cases I performed pubic static void main(String[] args) { Random rand = new Random(); BST<Integer, Character> tree = new BST<>(); for (int i = 0; i < 25; i++) { int key = rand.nextInt(26) + ‘a’; char val = (char)key; tree.put(key, val); }
// note: not all of these chars will end up being generated from the for loop // some of these return values will be null System.out.println(tree.get((int)’a’)); System.out.println(tree.get((int)’b’)); System.out.println(tree.get((int)’c’)); System.out.println(tree.get((int)’f’)); System.out.println(tree.get((int)’k’)); System.out.println(tree.get((int)’x’)); tree.walk(); //write code to test isEqual and toString methods! } }
Explanation / Answer
Please find the code below with detailed inline comments.
CODE
====================
import java.util.Random;
public class BST<Key extends Comparable<Key>, Value> {
private Node root; // inner Node class // note: an outer class has direct access to values in an inner class
public static int size = 0;
private class Node {
public Key key;
public Value value;
public Node lChild; // lChild child
public Node rChild; // rChild child
public Node (Key key, Value val) {
this.key = key;
this.value = val;
lChild = rChild = null;
}
}
public int size() {
return size;
} // returns # of nodes in the tree
// returns the value associated with they key // returns null if the key is not in the tree
public Value get(Key key) {
return search(root, key);
}
public Value search(Node root, Key key) {
if (root == null)
return null;
if(root.key == key)
return root.value;
// val is greater than root's key
if (root.key.compareTo(key) > 0)
return search(root.lChild, key);
// val is less than root's key
return search(root.rChild, key);
}
public void put(Value val, Key key) {
insertRec(root, key, val);
} // inserts the key value pair into the tree
Node insertRec(Node root, Key key, Value val) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key, val);
size ++;
return root;
}
/* Otherwise, recur down the tree */
if (key.compareTo(root.key) < 0)
root.lChild = insertRec(root.lChild, key, val);
else if (key.compareTo(root.key) > 0)
root.rChild = insertRec(root.rChild, key, val);
/* return the (unchanged) node pointer */
return root;
}
// performs an in order walk of the tree printing the values
public void walk() {
printInorder(root);
}
void printPostorder(Node node)
{
if (node == null)
return;
// first recur on lChild subtree
printPostorder(node.lChild);
// then recur on rChild subtree
printPostorder(node.rChild);
// now deal with the node
System.out.print(node.key + " ");
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(Node node)
{
if (node == null)
return;
/* first recur on lChild child */
printInorder(node.lChild);
/* then print the data of node */
System.out.print(node.key + " ");
/* now recur on rChild child */
printInorder(node.rChild);
}
/* Given a binary tree, print its nodes in preorder*/
void printPreorder(Node node)
{
if (node == null)
return;
/* first print data of node */
System.out.print(node.key + " ");
/* then recur on lChild sutree */
printPreorder(node.lChild);
/* now recur on rChild subtree */
printPreorder(node.rChild);
}
// returns true is this tree (using root node) is exactly same as another BST, return false otherwise.
public boolean isEqual(BST b) {
return identicalTrees(root, b.root);
}
public boolean identicalTrees(Node a, Node b) {
if (a == null && b == null)
return true;
/* 2. both non-empty -> compare them */
if (a != null && b != null)
return (a.value == b.value
&& identicalTrees(a.lChild, b.lChild)
&& identicalTrees(a.rChild, b.rChild));
/* 3. one empty, one not -> false */
return false;
}
// here are some of the test cases I performed
public static void main(String[] args) {
Random rand = new Random();
BST<Integer, Character> tree = new BST<>();
for (int i = 0; i < 25; i++) {
int key = rand.nextInt(26) + 'a';
char val = (char)key;
tree.put(val, key);
}
// note: not all of these chars will end up being generated from the for loop // some of these return values will be null
System.out.println(tree.get((int)'a'));
System.out.println(tree.get((int)'b'));
System.out.println(tree.get((int)'c'));
System.out.println(tree.get((int)'f'));
System.out.println(tree.get((int)'k'));
System.out.println(tree.get((int)'x'));
tree.walk(); //write code to test isEqual and toString methods!
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.