//CLASS BinarySearchTree public class BinarySearchTree> extends BinaryTree { /** * Finds the location of the target in the binary search tree, * and returns a reference to the data. Returns null if the target is * not in the tree. * * @param target The thing to search for, * @return A reference to the data in the tree if it is found, or null otherwise. */ public E find(E target) { // Implement this method. // Hint: Look at both the public and the private contains methods. // You'll need a private helper method version of find just like the // contains method. However, contains just determines if the target // is in the tree, returning a boolean. Your find method will instead // return the data that is found. return null; } /** * Searches tree for target. * @param target The element to look for. * @return true if in tree, and false otherwise */ public boolean contains(E target) { return contains(root, target); } /** * Adds target to tree if it doesn't already exist. * @param target The element to add. * @return true if target added and false otherwise. */ public boolean add(E target) { if (root==null) { root = new Node(target); return true; } return add(root, target); } /** * Output contents in order. */ public void printOrderedData() { inOrderTraversal(new ProcessData(){ @Override public void process(E data) { System.out.print(data + " "); }}); } private boolean contains(Node subtreeRoot, E target) { if (subtreeRoot==null) return false; if (target.compareTo(subtreeRoot.data)==0) return true; else if (target.compareTo(subtreeRoot.data) subtreeRoot, E target) { if (target.compareTo(subtreeRoot.data)==0) return false; else if (target.compareTo(subtreeRoot.data)(target); return true; } return add(subtreeRoot.left, target); } else { if (subtreeRoot.right==null) { subtreeRoot.right = new Node(target); return true; } return add(subtreeRoot.right, target); } } }

 // CLASS BinaryTree public class BinaryTree { protected Node root; /** * Constructs an empty binary tree. */ public BinaryTree() { } /** * Constructs a binary tree with given data in the root and the specified left and right * subtrees. * * @param data The data to store in root. * @param leftTree The left subtree. * @param rightTree The right subtree. */ public BinaryTree(E data, BinaryTree leftTree, BinaryTree rightTree) { root = new Node(data); if (leftTree!=null) { root.left = leftTree.root; } if (rightTree!=null) { root.right = rightTree.root; } } /** * Constructs a binary tree with a given node as its root. * @param root The root of the binary tree. */ protected BinaryTree(Node root) { this.root = root; } /** * Gets the left subtree of this tree. * @return The left subtree, or null if it doesn't exist. */ public BinaryTree getLeftSubtree() { if (root!=null && root.left!=null) return new BinaryTree(root.left); else return null; } /** * Gets the right subtree of this tree. * @return The right subtree, or null if it doesn't exist. */ public BinaryTree getRightSubtree() { if (root!=null && root.right!=null) return new BinaryTree(root.right); else return null; } /** * Gets the data from the root node. * @return The data from the root, or null if tree is empty. */ public E getData() { if (root!=null) return root.data; else return null; } /** * Checks if tree is empty * @return true if root is null, and false otherwise */ public boolean isEmpty() { return root == null; } /** * Checks if tree is a leaf. * @return true if this tree is a leaf, and false otherwise. */ public boolean isLeaf() { return root != null && root.left == null && root.right == null; } /** * Performs a preorder traversal, executing the specified operation * on the data in each node it visits. * * @param visitOperation An operation to apply to the data of each visited node. */ protected void preOrderTraversal(ProcessData visitOperation) { preOrderTraversal(root, visitOperation); } private void preOrderTraversal(Node node, ProcessData visitOperation) { if (node==null) return; visitOperation.process(node.data); preOrderTraversal(node.left, visitOperation); preOrderTraversal(node.right, visitOperation); } /** * Performs a postorder traversal, executing the specified operation * on the data in each node it visits. * * @param visitOperation An operation to apply to the data of each visited node. */ protected void postOrderTraversal(ProcessData visitOperation) { postOrderTraversal(root, visitOperation); } private void postOrderTraversal(Node node, ProcessData visitOperation) { if (node==null) return; postOrderTraversal(node.left, visitOperation); postOrderTraversal(node.right, visitOperation); visitOperation.process(node.data); } /** * Performs a inorder traversal, executing the specified operation * on the data in each node it visits. * * @param visitOperation An operation to apply to the data of each visited node. */ protected void inOrderTraversal(ProcessData visitOperation) { inOrderTraversal(root, visitOperation); } private void inOrderTraversal(Node node, ProcessData visitOperation) { if (node==null) return; if (node.left != null && visitOperation instanceof PrePostProcess) ((PrePostProcess)visitOperation).pre(); inOrderTraversal(node.left, visitOperation); visitOperation.process(node.data); inOrderTraversal(node.right, visitOperation); if (node.right != null && visitOperation instanceof PrePostProcess) ((PrePostProcess)visitOperation).post(); } protected interface ProcessData { void process(E data); } protected interface PrePostProcess extends ProcessData { void pre(); void post(); } protected static class Node { protected E data; protected Node left; protected Node right; /** * Constructs a Node containing the given data. * @param data Data to store in node */ public Node(E data) { this.data = data; } @Override public String toString() { return data.toString(); } } }

This assignment is end of chapter 6, Programming Project 7, from page 357 of the textbook. I am simply giving you more specific details Define an IndexTree class such that each node has data fields to store a word, the count of occurrences of that word in a document file, and the line number for each occurrence. Use an ArrayList to store the line numbers. Use an IndexTree object to store an index of words appearing in a text file, and then display the index by performing an inorder traversal of the tree BinarySearchTree E extends Comparable> IndexTree + E find(E target) +boolean contains(E target) + boolean add(E target) + void printOrderedData0 BinarySearchTree index +IndexTree(String filename) + void addRecord(String w, int line) + void printIndex0) Word Kinterface>> Comparable - String w -int count ArrayList Integer> lines int compareTo(Word o) + Word(String w, int line) + void addOccurrence(int line) + String toString) Consider the UML above. I left a few things out of the UML that you won't need to directly worry about (e.g the BinarySearchTree class extends the BinaryTree class, which I've provided you with) Do the following Implement the find method of the BinarySearchTree class. The rest of that class is already implemented (from an in-class example). Carefully read the javadoc comment that I provided in the source code to make sure you implement the correct thing Implement the IndexTree class, along with its inner class Word, as specified in the UML above. A reminder on some UML notation: means private, and+ means public. Here are details of what the various methods should do: Inner class, Word, represents one unique word, the count of the number of occurrences of that word, and a list of all of the line numbers from the file where it appeared. o Constructor initializes the Word for the first occurrence found, so should initialize the field w to whatever String the word is, count to 1, and the ArrayList to a single element consisting of whatever line number was specified addOccurrence should add the specified line number to the ArrayList only if it's not already in the list, and regardless should increase count by 1. We want to know total number of times the word was found, but the list of line numbers should only have unique line numbers (think of a book's index, where you wouldn't see the same page number listed multiple times for the same word)