Hi
I have written a program that will read a list of words from a file, insert these into a binary search tree, write words from the tree to another file, so that the resulting list contains words in ascending order. My input file Alpha1.txt contains the following contents in the order and format given (one word per line):
Dawn
Dave
Mike
Beth
David
Gina
Pat
Cindy
Sue
My program is supposed to be producing an alphabetical list of these words in another file "final.txt".
Instead it gives me the following list:
Dave Beth David Gina Cindy Sue Pat Mike Dawn
This is obviously wrong, right? My correct list in "final.txt" should be
Beth Cindy Dave David Dawn Gina Mike Pat Sue
I am not sure what is wrong with my code which I reproduce below:
-----
import java.io.*;
import java.util.*;
//read Java Developer's Almanac from exampledepot.com
//Read this: http://en.wikipedia.org/wiki/Tree_traversal
/**preorder(node)
print node.value
if node.left ? null then preorder(node.left)
if node.right ? null then preorder(node.right)
*/
public class AlphabeticBinarySortTree
{
private static TreeNode root;
private static TreeNode runner;
static String[] alphaArray;
static int alphaCounter;
private static TreeNode alphaRunner;
//Inner class
private static class TreeNode
{
String word;
TreeNode left;
TreeNode right;
int count;
public TreeNode(String word)
{
this.word = word;
left = null;
right = null;
}
public void insertAll(TreeNode newNode)
{
if(newNode.word.compareTo(runner.word) < 1)
{
System.out.println("newNode.word = " + newNode.word);
if(runner.left == null)
{
runner.left = newNode;
runner = runner.left;
}
else
{
insertAll(newNode);
}
}
else if(newNode.word.compareTo(runner.word) > 1)
{
System.out.println("newNode.word = " + newNode.word);
if(runner.right == null)
{
runner.right = newNode;
runner = runner.right;
}
else
{
insertAll(newNode);
}
}
else
{
count++;
}
}// end method insertAll
// Recursively print words (with counts) in sorted order
public static void printInPreOrder(TreeNode root)
{
System.out.println(root.word + " ");
if(root.left != null)
{
printInPreOrder(root.left);
}
if(root.right != null)
{
printInPreOrder(root.right);
}
} //end method printInPreOrder()
//called from inside main
public static void arrangeInAscendingOrder(TreeNode root, PrintWriter pWriter)
{
if(root.left != null)
{
arrangeInAscendingOrder(root.left, pWriter);
}
System.out.println();
System.out.println();
System.out.println(root.word + " ");
pWriter.write(root.word + " ");
if(root.right != null)
{
arrangeInAscendingOrder(root.right, pWriter);
}
}
}//end inner class TreeNode
public AlphabeticBinarySortTree()
{
root = null;
}
//belong to the outer class
public static void main(String[] args)
{
System.out.println("This program reads text from a file that it will parse. ");
System.out.println("In doing so, it will eliminate duplicate strings and ");
System.out.println("pick up only unique strings.These strings will be in a ");
System.out.println("stored in alphabetical order in a binary Search tree before they are ");
System.out.println("written out to another text file in alphabetic order");
//open the file for reading
try
{
BufferedReader bReader = new BufferedReader(new FileReader("Alpha1.txt"));
String words;
int count;
//System.out.println("A test to inspect the contents of words: " + words);
//System.out.println("Words =" + words);
count = 0;
//why is there an endless loop when
//I use "while(str != null)
StringTokenizer st;
st = null;
//based on http://www.exampledepot.com/egs/java.io/ReadLinesFromFile.html
while ((words = bReader.readLine()) != null)
{
st = new StringTokenizer(words);
while(st.hasMoreTokens())
{
//shiffman.net/teaching/a2z/concordance
String token = st.nextToken();
System.out.println("Token = " +token);
AlphabeticBinarySortTree.initiateInsert(token);
//count the number of tokens in the string
count++;
}//end inner while
}//end outer while
System.out.println("Here are the contents of your tree:");
//System.out.println("before the call to print()");
print();
System.out.println("the no of words in the file is: " + count);
bReader.close();
}//end of try
catch(IOException exception)
{
exception.printStackTrace();
}
/**try
{
FileWriter fWriter = new FileWriter("final.txt");
BufferedWriter bWriter = new BufferedWriter(fWriter);
PrintWriter pWriter = new PrintWriter(bWriter);
}
catch(IOExcepion exception)
{
exception.printStackTrace();
}*/
} // end main here
//this method belongs to the outer class
static void initiateInsert(String word)
{
//TreeNode is also static by the way
TreeNode newNode = new TreeNode(word);
if(root == null)
{
root = newNode;
System.out.println("root.word = " + root.word);
runner = root;
}
else
{
runner.insertAll(newNode);
}
}
// Start the recursive traversing of the tree
//without the access specifier 'static'
//I would get the following error message
//AlphabeticBinarySortTree.java:119: non-static method print() cannot be referenced from a static context
public static void print()
{
//System.out.println("**********AM I INSIDE THE PRINT() METHOD? ********");
if (root != null)
{
//System.out.println("++++++++ AM I INSIDE THE IF BLOCK OF THE PRINT() METHOD? +++++++");
//System.out.println("Inside THE IF BLOCK OF print() BUT BEFORE THE CALL TO printInPreOrder(),root.word = " + root.word);
AlphabeticBinarySortTree.TreeNode.printInPreOrder(root);
//open the file for writing
try
{
FileWriter fWriter = new FileWriter("final.txt");
BufferedWriter bWriter = new BufferedWriter(fWriter);
PrintWriter pWriter = new PrintWriter(bWriter);
AlphabeticBinarySortTree.TreeNode.arrangeInAscendingOrder(root, pWriter);
pWriter.close();
}
catch(IOException eException)
{
eException.printStackTrace();
}
}//end of if block
} // end of method print
}//end outer enclosing class here
--------
All help is highly appreciated. Thanks for your time and consideration.