Binary Search Trees

In class we implemented a set using a binary search tree. Implement a map the same way by adding the following methods to TreeMap:

V add (K key, V value);

boolean containsKey (K key);

V get (K key);

Then compile and run TreeMaps.java. Your output should look like this:

Here's the group with each person's age

{Ben=21, Fred=21, George=25, Harold=16, James=28, Jan=25, Jeff=24, Ken=27, Paul=29, Sam=22, Tom=30}

Is George in the group? yes

Is Keith in the group? no

How old is Harold? 16

How old is Lily? null

//Driver Program

public class TreeMaps { public static void main (String [] args) { TreeMap ages = new TreeMap< >(); String [] names = {"Ken", "Fred", "Sam", "Ben", "Harold", "Tom", "James", "Paul", "Jeff", "George", "Jan"}; int [] numbers = {27, 21, 22, 21, 16, 30, 28, 29, 24, 25, 25}; for (int i = 0; i < names.length; i++) { ages.add(names[i], numbers[i]); } // add System.out.println(" Here's the group with each person's age " +ages); String result = ages.containsKey("George") ? "yes" : "no"; // contains System.out.println("Is George in the group? " + result); result = ages.containsKey("Keith") ? "yes" : "no"; System.out.println("Is Keith in the group? " + result); // get System.out.println("How old is Harold? " + ages.get("Harold")); System.out.println("How old is Lily? " + ages.get("Lily")); } } 

//Interface for Map

public interface Map { V add (K key, V value); V remove (K key); V get (K key); boolean containsKey (K key); int size(); String toString(); } 

public class TreeMap, V> implements Map { private class Node { private K key; private V value; private Node left; private Node right; public Node (K key, V value) { this.key = key; this.value = value; left = null; right = null; } public String toString() { return "" + key + "=" + value; } } private Node root; private int size; public TreeMap() { root = null; size = 0; } public V add (K key, V value) { // to be implemented return null; } public boolean containsKey (K key) { // to be implemented return false; } public V get(K key) { // to be implemented return null; } public V remove (K key) { return null; } public int size() { return size; } public String toString() { if (root == null) { return "{}"; } String s = "{" + inorder(root, new StringBuilder()); return s.substring(0, s.length()-2) + "}"; } private String inorder(Node n, StringBuilder s) { if (n.left != null) inorder (n.left, s); s.append(n + ", "); if (n.right != null) inorder(n.right, s); return s.toString(); } } 

public class TreeSet> implements Set { private class Node { private T data; private Node left; private Node right; public Node (T item) { data = item; left = null; right = null; } } private Node root; private int size; public TreeSet() { root = null; size = 0; } public boolean add (T item) { Node newest = new Node(item); if (root == null) { root = newest; size++; return true; } else { Node current = root; Node parent = null; boolean onLeft = false; while (current != null) { int result = item.compareTo(current.data); if (result == 0) { return false; } parent = current; if (result < 0) { current = current.left; onLeft = true; } else { current = current.right; onLeft = false; } } if (onLeft) parent.left = newest; else parent.right = newest; size++; return true; } } public boolean contains (T item) { Node current = root; while (current != null) { int result = item.compareTo(current.data); if (result == 0) return true; if (result < 0) current = current.left; else current = current.right; } return false; } public boolean remove (T item) { Node current = root; Node parent = null; boolean onLeft = true; // traverse tree until find item while (current != null) { int result = item.compareTo(current.data); // smaller -> go left if (result < 0) { parent = current; current = current.left; onLeft = true; } // larger -> go right else if (result > 0) { parent = current; current = current.right; onLeft = false; } // item found else { // no children -> delete node if (current.left == null && current.right == null) { if (size == 1) root = null; else if (onLeft) parent.left = null; else parent.right = null; } // right child only -> replace parent with it else if (current.left == null) { if (current == root) root = current.right; else if (onLeft) parent.left = current.right; else parent.right = current.right; } // left child only -> replace parent with it else if (current.right == null) { if (current == root) root = current.left; else if (onLeft) parent.left = current.left; else parent.right = current.left; } // two children -> replace with largest predecessor // if node has child -> replace with child else { // save pointer to node to be replaced Node replace = current; // find largest predecessor parent = current; current = current.left; while (current.right != null) { parent = current; current = current.right; } // replace item to remove with largest predecessor replace.data = current.data; // if it has child, replace with child if (current.left != null) parent.right = current.left; else parent.right = null; } size--; return true; } } return false; } public T get() { return null; } public T remove() { return null; } public int size() { return size; } public String toString() { if (root == null) { return "[]"; } String s = "[" + inorder(root, new StringBuilder()); return s.substring(0, s.length()-2) + "]"; } private String inorder(Node n, StringBuilder s) { if (n.left != null) inorder (n.left, s); s.append(n.data + ", "); if (n.right != null) inorder(n.right, s); return s.toString(); } } 

/* * interface for a set * * unordered collection, no duplicates allowed */ public interface Set { /* * adds item to set if not already present * * returns true if item successfully added, false if not * */ boolean add (T item); T remove(); boolean remove (T item); T get(); boolean contains (T item); int size(); String toString(); } 

Next, revise your Seuss.java and Seuss2.java programs (this code is below) so that they call upon TreeSet and TreeMap to produce an alphabetical list of words and word counts. The output for the revised programs (call them Seuss4 and Seuss5) should look like this:

//Seuss

import java.io.File;

import java.io.FileNotFoundException;

import java.io.PrintWriter;

import java.util.Scanner;

public class Seuss {

// returns a string retaining only characters and converting to lower case

// all punctuation are removed

public static String removePunc(String s) {

String result = "";

s = s.toLowerCase();

for (int i = 0; i < s.length(); i++) {

char ch = s.charAt(i);

if (isLetter(ch))

result += ch;

}

return result;

}

public static boolean isLetter(char ch) {

if (ch >= 'a' && ch <= 'z')

return true;

else if (ch >= 'A' && ch <= 'Z')

return true;

else

return false;

}

public static void main(String[] args) {

String filename = "greenEggs.txt";

try {

Scanner inFile = new Scanner(new File(filename));

String word;

LinkedSet set = new LinkedSet();

while (inFile.hasNext()) {

word = inFile.next();

word = removePunc(word);

set.add(word);

}

inFile.close();

// write the set contents to a file

PrintWriter pw = new PrintWriter(new File("words.txt"));

pw.write(set.toString());

pw.close();

System.out.println("Saved the words in set to file words.txt ");

System.out.println(set.toString());

} catch (FileNotFoundException e) {

System.out.println(e.getMessage());

}

}

}

//Seuss2

import java.io.File;

import java.io.FileNotFoundException;

import java.io.PrintWriter;

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

public class Suess2 {

// returns a string retaining only characters and converting to lower case

// all punctuation are removed

public static String removePunc(String s) {

String result = "";

s = s.toLowerCase();

for (int i = 0; i < s.length(); i++) {

char ch = s.charAt(i);

if (isLetter(ch))

result += ch;

}

return result;

}

public static boolean isLetter(char ch) {

if (ch >= 'a' && ch <= 'z')

return true;

else if (ch >= 'A' && ch <= 'Z')

return true;

else

return false;

}

public static void main(String[] args) {

String filename = "greenEggs.txt";

try {

Scanner inFile = new Scanner(new File(filename));

String word;

Map map = new HashMap();

while (inFile.hasNext()) {

word = inFile.next();

word = removePunc(word);

if (map.containsKey(word))

{

int value = map.get(word).intValue();

map.put(word, value + 1);

}

else

map.put(word, 1);

}

inFile.close();

// write the set contents to a file

PrintWriter pw = new PrintWriter(new File("words.txt"));

pw.write(map.toString());

pw.close();

System.out.println("Saved the words in map to file words.txt ");

System.out.println(map.toString());

} catch (FileNotFoundException e) {

System.out.println(e.getMessage());

}

}

}

a am and anywhere are be boat box car could dark do eat eggs fox goat good green ham here house i if in let like may me mouse not on or rain sam say see so thank that the them there they train tree try will with would you

a=59 am=16 and=25 anywhere=8 are=2 be=4 boat=3 box=7 car=7 could=14 dark=7 do=37 eat=25 eggs=11 fox=7 goat=4 good=2 green=11 ham=11 here=11 house=8 i=85 if=1 in=40 let=4 like=44 may=4 me=4 mouse=8 not=84 on=7 or=8 rain=4 sam=19 say=5 see=4 so=5 thank=2 that=3 the=11 them=61 there=9 they=2 train=9 tree=6 try=4 will=21 with=19 would=26 you=34