Hi guys,
I'm working on my homework: I have to use a data structure to store words read from input file, i chose AVL tree to be the data structure, i implemented the tree and tested it with hard coded words, it works fine. However, with words read from input file the problem is each time a word is added to the AVL tree it will be the main root and it keeps showing the hight is 0, also when removing some times it shows NullPointerException.
Here is what i've done so far:
public AVLNode search(String key)
{
// Tree is empty
if (root == null)
{
return null;
}
// Tree is not empty
AVLNode p = root;
try
{while (true)
{
if(p == null && p.getData().equals(key))
{
break;
}
else if (key.compareTo(p.getData()) < 0)
{
p = p.getLeftChild();
}
else
{
p = p.getRightChild();
}
}
}
catch(NullPointerException e)
{
System.out.println(e);
}
return p;
}
// INSERT A NODE INTO AVL TRRE
public void insert(String data)
{
// Case: tree is empty <------------------------------
if (root == null)
{
root = new AVLNode(data);
return;
}
// Case: tree is not empty
AVLNode p = root;
// move p down as far as we can
while(true)
{
if (data.equals(p.getData()) && p.getLeftChild() != null)
{
p = p.getLeftChild();
}
else if(data.compareTo(p.getData()) < 0 && p.getLeftChild() != null)
{
p = p.getLeftChild();
}
else if (data.compareTo(p.getData()) > 0 && p.getRightChild() != null)
{
p = p.getRightChild();
}
else
{
break;
}
}
// insert new node to the tree as a child of node p
AVLNode newNode= new AVLNode(data);
if(data.equals(p.getData()))
{
p.setLeftChild(newNode);
}
else if (data.compareTo(p.getData()) < 0)
{
p.setLeftChild(newNode);
}
else
{
p.setRightChild(newNode);
}
rebalanceInsertionPath(newNode);
}
I think the problem is where I put the arrow ( <---------------)
The tests i've done:
AVLTree tree = new AVLTree();
tree.insert("university");
tree.insert("holiday");
tree.insert("lecture");
tree.insert("library");
tree.insert("building");
tree.insert("new");
tree.insert("old");
//tree.displayElements();
//tree.displayStructure();
System.out.println( "=== Remove (This shows NullPointerException ====");
tree.remove("old"); // Requires rotations
tree.search("university");
tree.displayElements();
tree.displayStructure();
Any ideas why each time the words are added to the main root and the tree doesn't keep adding the nodes?
It works fine with the tests i've done but when reading a file:
System.out.println("Please enter file name to open: \n");
// Name of first file
String firstFileName;
// Initialising fileName to read first file
firstFileName = input.nextLine();
// variable to hold the one line data
//String line = null;
File file = new File(firstFileName);
Scanner inFile = new Scanner(file).useDelimiter(("\\s+(\\W*\\s)?"));
// While the file has more words to read, keep reading
while(inFile.hasNext())
{
// Keep reading next word of the file
String word = inFile.next();
AVLTree tree = new AVLTree();
tree.insert(word);
tree.displayStructure();
Here where the problem occurs.
