This assignment is end of chapter 6, Programming Project 7, from page 357 of the
ID: 3702863 • Letter: T
Question
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) 'Explanation / Answer
//BinaryTree.java
package com.src;
//CLASS BinaryTree
public class BinaryTree<E> {
protected Node<E> 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<E> leftTree, BinaryTree<E> rightTree) {
root = new Node<E>(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<E> root) {
this.root = root;
}
/**
* Gets the left subtree of this tree.
*
* @return The left subtree, or null if it doesn't exist.
*/
public BinaryTree<E> getLeftSubtree() {
if (root != null && root.left != null)
return new BinaryTree<E>(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<E> getRightSubtree() {
if (root != null && root.right != null)
return new BinaryTree<E>(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<E> visitOperation) {
preOrderTraversal(root, visitOperation);
}
private void preOrderTraversal(Node<E> node, ProcessData<E> 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<E> visitOperation) {
postOrderTraversal(root, visitOperation);
}
private void postOrderTraversal(Node<E> node, ProcessData<E> 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<E> visitOperation) {
inOrderTraversal(root, visitOperation);
}
private void inOrderTraversal(Node<E> node, ProcessData<E> visitOperation) {
if (node == null)
return;
if (node.left != null && visitOperation instanceof PrePostProcess)
((PrePostProcess<E>) visitOperation).pre();
inOrderTraversal(node.left, visitOperation);
visitOperation.process(node.data);
inOrderTraversal(node.right, visitOperation);
if (node.right != null && visitOperation instanceof PrePostProcess)
((PrePostProcess<E>) visitOperation).post();
}
protected interface ProcessData<E> {
void process(E data);
}
protected interface PrePostProcess<E> extends ProcessData<E> {
void pre();
void post();
}
protected static class Node<E> {
protected E data;
protected Node<E> left;
protected Node<E> 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();
}
}
}
//BinarySearchTree.java
package com.src;
//CLASS BinarySearchTree
public class BinarySearchTree<E extends Comparable<E>> extends BinaryTree<E> {
/**
* 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 find(root,target);
}
private E find(Node<E> subtreeRoot, E target) {
if (subtreeRoot == null)
return null;
if (target.compareTo(subtreeRoot.data) == 0)
return subtreeRoot.data;
else if (target.compareTo(subtreeRoot.data) < 0)
return find(subtreeRoot.left, target);
else
return find(subtreeRoot.right, target);
}
/**
* 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<E>(target);
return true;
}
return add(root, target);
}
/**
* Output contents in order.
*/
public void printOrderedData() {
inOrderTraversal(new ProcessData<E>() {
@Override
public void process(E data) {
System.out.print(data + " ");
}
});
}
private boolean contains(Node<E> subtreeRoot, E target) {
if (subtreeRoot == null)
return false;
if (target.compareTo(subtreeRoot.data) == 0)
return true;
else if (target.compareTo(subtreeRoot.data) < 0)
return contains(subtreeRoot.left, target);
else
return contains(subtreeRoot.right, target);
}
private boolean add(Node<E> subtreeRoot, E target) {
if (target.compareTo(subtreeRoot.data) == 0)
return false;
else if (target.compareTo(subtreeRoot.data) < 0) {
if (subtreeRoot.left == null) {
subtreeRoot.left = new Node<E>(target);
return true;
}
return add(subtreeRoot.left, target);
} else {
if (subtreeRoot.right == null) {
subtreeRoot.right = new Node<E>(target);
return true;
}
return add(subtreeRoot.right, target);
}
}
}
//Word.java
package com.src;
import java.lang.reflect.Array;
import java.util.ArrayList;
public class Word implements Comparable<Word> {
private String w;
private int count;
private ArrayList<Integer> lines;
public Word(String w, int line) {
super();
this.w = w;
this.count = 1;
lines.add(line);
}
public void addOccurance(int line) {
if(!lines.contains(line))
lines.add(line);
count++;
}
@Override
public String toString() {
String s = w + "(" + count + "): ";
int i=0;
for(i=0;i<lines.size()-1;i++) {
s += lines.get(i) + ", ";
}
s += lines.get(i);
return s;
}
@Override
public int compareTo(Word o) {
// TODO Auto-generated method stub
return this.w.compareTo(o.w);
}
}
//IndexTree.java
package com.src;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.StringTokenizer;
public class IndexTree {
private BinarySearchTree<Word> index;
public IndexTree(String filename) throws FileNotFoundException {
super();
int count = 0;
Scanner sc = new Scanner(filename);
while (sc.hasNextLine()) {
String line = sc.nextLine();
count++;
StringTokenizer st = new StringTokenizer(line," ");
while (st.hasMoreTokens()) {
Word w = new Word(st.nextToken().toLowerCase(), count);
index.add(w);
}
}
sc.close();
}
public void addRecord(Word w, int line) {
if(index.contains(w)) {
Word wd = index.find(w);
wd.addOccurance(line);
}
else {
index.add(w);
}
}
public void printIndex() {
index.printOrderedData();
}
}