I'm doing an assignment for a Data Structures class, and I'm supposed to to implement a binary search tree with a client side method to create the tree. I've gotten most of it running I think, based on some debugging lines I added to track which part of the code has run. This is my class.
import java.io.*;
public class BinarySearch {
public static void main(String[] args) {
ArrayList<String> dict = new ArrayList<String>();
BSTree<String> searchTree = new BSTree<String>();
FileInputStream fstream = null;
BufferedInputStream bis = null;
DataInputStream dis = null;
BufferedReader br = null;
StopWatch time = new StopWatch();
long wordCount = 0;
long wordsInDict = 0;
try {
System.out.print("Enter the dictionary's name:");
br = new BufferedReader(new InputStreamReader(System.in));
String name = null;
name = br.readLine();
fstream = new FileInputStream(name);
bis = new BufferedInputStream(fstream);
dis = new DataInputStream(bis);
while (dis.available() != 0) {
dict.add(dis.readLine());
}
System.out.println("Dict size " + dict.getLength());
createTree(dict, searchTree);
System.out.println("List has been successfully built!\n");
System.out.print("Enter the file's name:");
br = new BufferedReader(new InputStreamReader(System.in));
name = br.readLine();
fstream = new FileInputStream(name);
bis = new BufferedInputStream(fstream);
dis = new DataInputStream(bis);
System.out.println("\nSearching for words in the file: " + name);
time.start();
while (dis.available() != 0) {
String line = dis.readLine();
String[] words = line.split(" ");
wordCount += words.length;
for (String w : words) {
w.toLowerCase();
if (searchTree.contains(w))
wordsInDict++;
}
}
time.stop();
} catch (FileNotFoundException e) {
System.out.println("File not found");
} catch (IllegalArgumentException e) {
System.out.println("Size is less than 0");
} catch (IOException e) {
System.out.println("Read error");
}
System.out.println("Number of tokens = " + wordCount);
System.out.println("Number of tokens in dictionary = " + wordsInDict);
System.out.println(time);
}
public static <T extends Comparable<? super T>>
void createTree(ArrayList<T> list, BSTree<T> tree) {
tree.add(list.getEntry(list.getLength()/2));
System.out.println("Element added");
int leftSize = list.getLength()/2;
int rightSize = leftSize;
if ((list.getLength() % 2) == 0)
rightSize -= 1;
System.out.println("Sizes determined");
ArrayList<T> leftSub = new ArrayList<T>();
ArrayList<T> rightSub = new ArrayList<T>();
System.out.println("Sublists defined");
for (int i = 0; i < leftSize; i++) {
leftSub.add(list.getEntry(i));
}
System.out.println("Left sub filled");
for (int i = leftSize + 1; i < list.getLength(); i++) {
rightSub.add(list.getEntry(i));
}
System.out.println("Right sub filled");
createTree(leftSub, rightSub, tree);
}
private static <T extends Comparable<? super T>>
void createTree(ArrayList<T> leftTree, ArrayList<T> rightTree, BSTree<T> tree) {
if ((leftTree.getLength() > 0) && (rightTree.getLength() > 0)) {
ArrayList<T> leftSub1 = new ArrayList<T>();
ArrayList<T> rightSub1 = new ArrayList<T>();
System.out.println("2L sublists defined");
ArrayList<T> leftSub2 = new ArrayList<T>();
ArrayList<T> rightSub2 = new ArrayList<T>();
System.out.println("2R sublists defined");
System.out.println("2L Element " + leftTree.getEntry(leftTree.getLength()/2));
tree.add(leftTree.getEntry(leftTree.getLength()/2));
int leftSize1 = leftTree.getLength()/2;
int rightSize1 = leftSize1;
if ((leftTree.getLength() % 2 == 0))
rightSize1 -= 1;
System.out.println("2L Sizes determined");
for (int i = 0; i < leftSize1; i++) {
leftSub1.add(leftTree.getEntry(i));
}
System.out.println("2L leftSub size " + leftSub1.getLength());
for (int i = leftSize1 + 1; i < leftTree.getLength(); i++) {
rightSub1.add(leftTree.getEntry(i));
}
System.out.println("2L rightSub size " + rightSub1.getLength());
System.out.println("2R Element " + rightTree.getEntry(rightTree.getLength()/2));
tree.add(rightTree.getEntry(rightTree.getLength()/2));
int leftSize2 = rightTree.getLength()/2;
int rightSize2 = leftSize2;
if ((rightTree.getLength() % 2 == 0))
rightSize2 -= 1;
System.out.println("2R Sizes determined");
for (int i = 0; i < leftSize2; i++) {
leftSub2.add(rightTree.getEntry(i));
}
System.out.println("2R leftSub size " + leftSub2.getLength());
for (int i = leftSize2 + 1; i < rightTree.getLength(); i++) {
rightSub2.add(rightTree.getEntry(i));
}
System.out.println("2R rightSub size " + rightSub2.getLength());
createTree(leftSub1, rightSub1, tree);
createTree(leftSub2, rightSub2, tree);
}
}
}
This is the output I get from the console.
Enter the dictionary's name:dict8.txt
Dict size 17272
Element added
Sizes determined
Sublists defined
Left sub filled
Right sub filled
2L sublists defined
2R sublists defined
2L Element descend
2L Sizes determined
2L leftSub size 4318
2L rightSub size 4317
2R Element roland
2R Sizes determined
2R leftSub size 4317
2R rightSub size 4317
2L sublists defined
2R sublists defined
2L Element brenda
It looks like it managed to complete the first run through the createTree method, but then it just stopped at the tree.add statement the second time through. The method has been defined by my instructor so I cannot change anything there. What may be the problem here?