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.
This is the output I get from the console.
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?
Code:
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);
}
}
}
Code:
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