Need help with the following assignment: Using binary tree search (BST), create
ID: 652799 • Letter: N
Question
Need help with the following assignment:
Using binary tree search (BST), create a Java program that will build an index, or a cross-reference listing, for a text document. The program will display the number of times each word appears in the document, the line numbers in which each word appears and the position of each word in the line. The program will also allow the user of the program to perform run-time queries and perform a word search. For each word searched, output the word, the number od times the word appears in the text, the line numbers and the position the word appears on each line.
Sample output:
WORDS FROM THE FILE:
WORD OCCURRENCES LINE POSITION
our 2 1 7
11 10
people 3 20 11
21 1
21 4
perish 1 21 7
SEARCHED WORDS FROM USER:
WORD OCCURRENCES LINE POSITION
dedicate 2 3 8
10 5
devotion 1 15 3
gave 1 20 2
Explanation / Answer
Complete Program:
// File: IndexedBST.java
import java.io.*;
import java.util.*;
public class IndexedBST
{
protected class Word
{
protected String str;
protected ArrayList<Integer> lines;
protected ArrayList<Integer> positions;
public Word(String newStr, int line, int pos)
{
lines = new ArrayList<Integer>();
positions = new ArrayList<Integer>();
str = newStr;
lines.add(line);
positions.add(pos);
}
public String toString()
{
String result = "";
result += String.format("%-10s%10d%10d%10d ", str, lines.size(), lines.get(0), positions.get(0));
for(int i = 1; i < lines.size(); i++)
result += String.format("%30d%10d ", lines.get(i), positions.get(i));
return result;
}
}
private final int capacity = 50;
private int maxIndex;
private Word[] tree;
private int count;
public IndexedBST()
{
count = 0;
tree = new Word[capacity];
maxIndex = -1;
}
public IndexedBST(String newStr, int line, int pos)
{
Word element = new Word(newStr, line, pos);
count = 1;
tree = new Word[capacity];
tree[0] = element;
maxIndex = 0;
}
public void addElement(String newStr, int line, int pos)
{
Word element = new Word(newStr, line, pos);
if(tree.length < maxIndex * 2 + 3)
expandCapacity();
if(isEmpty())
{
tree[0] = element;
maxIndex = 0;
}
else
{
boolean added = false;
int index = 0;
while(!added)
{
if((element.str).compareTo((tree[index].str)) < 0)
{
if(tree[index * 2 + 1] == null)
{
tree[index * 2 + 1] = element;
added = true;
if(index * 2 + 1 > maxIndex)
maxIndex = index * 2 + 1;
}
else
index = index * 2 + 1;
}
else if((element.str).compareTo((tree[index].str)) > 0)
{
if(tree[index * 2 + 2] == null)
{
tree[index * 2 + 2] = element;
added = true;
if(index * 2 + 2 > maxIndex)
maxIndex = index * 2 + 2;
}
else
index = index * 2 + 2;
}
else
{
tree[index].lines.add(line);
tree[index].positions.add(pos);
added = true;
}
}
}
count++;
}
public Word find(String str)
{
for(int ct = 0; ct < count; ct++)
{
if(str.compareTo(tree[ct].str) == 0)
{
return tree[ct];
}
}
return null;
}
public boolean isEmpty()
{
return (count == 0);
}
public String toString()
{
String result = "";
result += String.format("%-10s%10s%10s%10s ", "WORD", "OCCURRENCES", "LINE", "POSITION");
for(int i = 0; i <= maxIndex; i++)
{
if(tree[i] != null)
result += tree[i].toString();
}
return result;
}
public void expandCapacity()
{
Word[] temp = new Word[tree.length * 2];
for(int i = 0; i < tree.length; i++)
temp[i] = tree[i];
tree = temp;
}
public static void main(String[] args) throws FileNotFoundException
{
IndexedBST bst1 = new IndexedBST();
bst1.addElement("our", 1, 7);
bst1.addElement("people", 20, 11);
bst1.addElement("perish", 21, 7);
bst1.addElement("dedicate", 3, 8);
bst1.addElement("devotion", 15, 3);
bst1.addElement("gave", 20, 2);
bst1.addElement("our", 11, 10);
bst1.addElement("people", 21, 1);
bst1.addElement("devotion", 10, 5);
bst1.addElement("people", 21, 7);
System.out.println("BST #1");
System.out.println(bst1);
IndexedBST bst2 = new IndexedBST();
Scanner infile = new Scanner(new File("lines.txt"));
String line;
int lineNum = 0;
while(infile.hasNextLine())
{
line = infile.nextLine();
lineNum++;
String[] tokens = line.split(" ");
for(int i = 0; i < tokens.length; i++)
{
bst2.addElement(tokens[i], lineNum, i+1);
}
}
System.out.println(" BST #2");
System.out.println(bst2);
}
}
--------------------------------------------------------------
Input file: lines.txt
using binary tree search create a
java program that will build an index
or a cross reference listing
for a text document
the program will display the number
of times each word appears
in the document
the line numbers in which each
word appears and the position
of each word in the line
-----------------------------------------------------------
Sample Output:
BST #1
WORD OCCURRENCES LINE POSITION
our 2 1 7
11 10
dedicate 1 3 8
people 3 20 11
21 1
21 7
devotion 2 15 3
10 5
perish 1 21 7
gave 1 20 2
BST #2
WORD OCCURRENCES LINE POSITION
using 1 1 1
binary 1 1 2
will 2 2 4
5 3
a 3 1 6
3 2
4 2
tree 1 1 3
which 1 8 5
word 3 6 4
9 1
10 3
1 11 1
an 1 2 6
search 1 1 4
appears 2 6 5
9 2
create 1 1 5
that 1 2 3
and 1 9 3
build 1 2 5
java 1 2 1
text 1 4 3
the 6 5 1
5 5
7 2
8 1
9 4
10 5
index 1 2 7
program 2 2 2
5 2
times 1 6 2
cross 1 3 3
or 1 3 1
reference 1 3 4
for 1 4 1
listing 1 3 5
position 1 9 5
document 2 4 4
7 3
in 3 7 1
8 4
10 4
line 2 8 2
10 6
number 1 5 6
display 1 5 4
each 3 6 3
8 6
10 2
of 2 6 1
10 1
numbers 1 8 3
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.