Define an IndexTree class such that each node has data fields to store a word, the count of occurances of that word in a document file, and the line number for each occurance. Use an ArrayList to store the line numbers. Use an IndexTree object to store an index of words appearing in the text file, and then display the index by performing an inorder traversal of the tree.

 // 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(); } } }

//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); } } }

BinarySearch Tree> Index Tree - BinarySearchTree index + E find(E target) + boolean contains E target) + boolean add(E target) + void printOrderedData() + Index Tree(String filename) + void addRecord(String w, int line) + void printIndex() Word > Comparable - String w - int count - ArrayList lines + int compareTo(Word o) + Word(String w, int line) + void addOccurrence(int line) + String toString()