Index Tree

Overview You are going to write a Java application to implement a document index using the data structure Binary Search Tree. First define a java class named IndexTree, where each tree node has data fields to store a word, the count of occurrence of that word in a document file, and the line number for each occurrence. The line numbers of a word are stored using an array or an ArrayList. Next define a java application class named IndexTreeTest. In this class, you will do the following

Create an empty IndexTree object

Populate the nodes of the IndexTree object using index entries entered by the user or stored in a text file. These input entries must be at random order.

o Note that you are NOT required to have your program parse document files and generate index entries. The user of your program enters each index entry: a word, the occurrence count, and line numbers of occurrences.

Display all index entries in the IndexTree object in the increasing alphabetical order by performing an inorder traversal of this tree

Allow the user to search the line numbers of a given word in the IndexTree object. You must implement this IndexTree as a Binary Search Tree data structure. Otherwise, you will not get any credit.

Hints

You can solve the problem using either of the following solutions

i. Create a non-generic class named IndexTree whose tree node class contains these data fields: word, wordOccurenceCount, lineNumbersOfOccurences, leftChild, rightChild.

ii. Or create an IndexEntry class that implements the interface Comparable and use the generic BinarySearchTree class to create the index tree

You also need to add necessary constructors, accessors and/or mutators, methods for in-order traversal, search and add a given word entry.

The IndexTreeTest class is similar to BinarySearchTreeTest class given in class.