Add a method levelorderElements() to the BST.java binary search tree dictionary implementation on Vocareum. In level order the root comes first, then all nodes of level 1, then all nodes of level 2, and so on. Within a level, the order is left to right; i.e., in ascending order. Model your method on inorderElements(). Test your method by changing the calls to inorderElements() in values() to levelorderElements(). This way, values() will return the values in the dictionary in level order. Test your class using the program PrintLevels.java. Hint: Preorder traversals make use of a stack through recursive calls. Consider making use of another data structure to help implement the lev- elorder traversal.

BST class:

import java.util.ArrayList;

/** BST implementation for Dictionary ADT */ class BST, E> implements Dictionary { private BSTNode root; // Root of BST private int nodecount; // Size of BST

/** Constructor */ BST() { root = null; nodecount = 0; }

/** Reinitialize tree */ public void clear() { root = null; nodecount = 0; }

/** * Insert a record into the tree. * * @param k * Key value of the record. * @param e * The record to insert. */ public void insert(K k, E e) { root = inserthelp(root, k, e); nodecount++; }

/** * Remove a record from the tree. * * @param k * Key value of record to remove. * @return Record removed, or null if there is none. */ public E remove(K k) { E temp = findhelp(root, k); // find it if (temp != null) { root = removehelp(root, k); // remove it // System.out.println("called removehelp"); nodecount--; } return temp; }

/** * Remove/return root node from dictionary. * * @return The record removed, null if empty. */ public E removeAny() { if (root == null) return null; E temp = root.element(); root = removehelp(root, root.key()); --nodecount; return temp; }

/** * @return Record with key k, null if none. * @param k * The key value to find. */ public E find(K k) { return findhelp(root, k); }

/** @return Number of records in dictionary. */ public int size() { return nodecount; }

private E findhelp(BSTNode rt, K k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) return findhelp(rt.left(), k); else if (rt.key().compareTo(k) == 0) return rt.element(); else return findhelp(rt.right(), k); }

private BSTNode inserthelp(BSTNode rt, K k, E e) { if (rt == null) return new BSTNode(k, e); if (rt.key().compareTo(k) > 0) rt.setLeft(inserthelp(rt.left(), k, e)); else rt.setRight(inserthelp(rt.right(), k, e)); return rt; }

private BSTNode getmin(BSTNode rt) { if (rt.left() == null) return rt; else return getmin(rt.left()); }

private BSTNode deletemin(BSTNode rt) { if (rt.left() == null) return rt.right();

else { rt.setLeft(deletemin(rt.left())); return rt; } }

/** * Remove a node with key value k * * @return The tree with the node removed */ private BSTNode removehelp(BSTNode rt, K k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) rt.setLeft(removehelp(rt.left(), k)); else if (rt.key().compareTo(k) < 0) rt.setRight(removehelp(rt.right(), k)); else { // Found it, remove it if (rt.left() == null) return rt.right(); else if (rt.right() == null) return rt.left(); else { // Two children BSTNode temp = getmin(rt.right()); rt.setElement(temp.element()); rt.setKey(temp.key()); rt.setRight(deletemin(rt.right())); } } return rt; }

/** * Creates a list storing the the nodes in the subtree of a node, ordered * according to the inorder traversal of the subtree. */

protected void inorderElements(BSTNode v, ArrayList elts) { // elts.add(v.element()); if (v.left() != null) inorderElements(v.left(), elts); // recurse on left child elts.add(v.element()); if (v.right() != null) inorderElements(v.right(), elts); // recurse on right child }

/** Returns an iterable collection of the tree nodes. */ public Iterable values() { ArrayList elements = new ArrayList(); if (size() != 0) inorderElements(root, elements); // assign positions in order return elements; }

public Iterable findAll(K k) { ArrayList al = new ArrayList(); findAllhelp(root, k, al); return al; }

protected void findAllhelp(BSTNode rt, K k, ArrayList a) { if (rt == null) return; if (rt.key().compareTo(k) > 0) findAllhelp(rt.left(), k, a); else if (rt.key().compareTo(k) == 0) { a.add(rt.element()); findAllhelp(rt.right(), k, a); } else findAllhelp(rt.right(), k, a); }

/* the following are for solving the exercises in Shaffer, ch. 5 */

public Iterable range(K a, K b) { ArrayList elements = new ArrayList(); rangehelp(root, elements, a, b); return elements; }

protected void rangehelp(BSTNode v, ArrayList elts, K a, K b) { if (v == null) { return; } if (v.key().compareTo(a) > 0) { rangehelp(v.left(), elts, a, b); } if (v.key().compareTo(a) >= 0 && v.key().compareTo(b) <= 0) { elts.add(v.element()); } if (v.key().compareTo(b) < 0) { rangehelp(v.right(), elts, a, b); } } }

PrintRange class:

import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; import java.util.ArrayList;

/* * Print out all dictionary records in a given range of keys. */ public class PrintRange {

public static void main(String[] args) { BST PDict = new BST(); File file = new File("shuffledDictionary.txt");

// Read in the (shuffled) cmu pronunciation dictionary. try { Scanner scanner = new Scanner(file); while (scanner.hasNextLine()) { String line = scanner.nextLine(); if (line.substring(0, 3).equals(";;;")) continue; // skip comment lines Pronunciation p = new Pronunciation(line); PDict.insert(p.getWord(), p); // key dictionary on word } scanner.close(); } catch (FileNotFoundException e) { e.printStackTrace(); }

Scanner input = new Scanner(System.in); String a = input.next(); // first word in range String b = input.next(); // last word in range for(Pronunciation p : PDict.range(a,b)) System.out.println(p.getWord()+" "+p.getPhonemes()); } }