Hi Guys,
I am working on a binary search tree and I've been stuck on some code for the last couple of days. There are 2 issues that I can't seem to figure out how to fix.
1) I have a file that has a list of names and ID's and that needs to be inputted into a BST. The odd thing is when the file has an odd number of names, I get an error and when it' even it doesn't give an error.
2) I also need to use depth-first and in-order tree traversal to print to a file the result. For now, I just print to the screen and for some reason, I only get about half the entries back and I am not sure where I have gone wrong. Any help would be appreciated. Thanks in advanced.
Here is the code I have so far:
Main:
import java.io.*;
import java.util.Arrays;
public class Assign3 {
public static void main(String[]args) throws IOException
{
//Checks if there is arguments passed through the command line.
if (args.length != 1)
{
quitError("Invalid arguments.");
}
String inputFile = args[0];
String record;
BST btree = new BST();
try
{
BufferedReader input = new BufferedReader(new FileReader(inputFile));
//Scans each word from the input and prints it out
record = input.readLine();
while (record != null)
{
String[] data = new String[5];
String[] fields = new String[1];
record = input.readLine();
char opCode = record.charAt(0);
String studentID = record.substring(1,8);
String lastName = record.substring(8,32);
String home = record.substring(33,37);
String program = record.substring(37,41);
String year = record.substring(41,42);
data[0]=studentID;
data[1]=lastName;
data[2]=home;
data[3]=program;
data[4]=year;
fields[0] = lastName;
String storeData = Arrays.toString(data);
if (opCode == 'I')
{
btree.insert(fields[0], storeData);
}
else
{
btree.delete(fields[0]);
}
record = input.readLine();
//btree.inorder();
}
btree.inorder();
//btree.breadthFirst();
input.close();
//print(btree.root);
return;
}
catch(FileNotFoundException filenotfoundexception) //Catches file not found exception
{
System.out.println("File not found.");
}
catch(IOException ioexception) //Catches io exception
{
System.out.println("File input error occured!");
}
}
public static void print(BSTNode root) {
print(root.left);
System.out.println(root.key+" -> "+root.getValue(root.key));
print(root.right);
}
//Displays an error message, program exits
public static void quitError(String msg)
{
System.out.println(msg);
System.out.println("Program will now quit.");
System.exit(0);
}
}
Tree Class:
public class BST {
BSTNode root = null;
public BST(){}
public void clear()
{
root = null;
}
public boolean isEmpty()
{
return root == null;
}
@SuppressWarnings("unchecked")
public void insert(Comparable key, String value) {
BSTNode current = root;
BSTNode prev = null;
while (current != null) { // find a place for inserting new node;
prev = current;
if (key.compareTo(current.key) < 0)
{
current = current.right;
//System.out.println("Set Right");
}
else
{
current = current.left;
//System.out.println("Set Left");
}
}
if (root == null) // tree is empty;
{
root = new BSTNode(key, value);
//System.out.println("New Node Created");
}
else if (key.compareTo(prev.key) < 0)
{
prev.right = new BSTNode(key, value);
//System.out.println("Set Right1");
}
else
{
prev.left = new BSTNode(key, value);
//System.out.println("Set Left1");
}
}
private void inorder(BSTNode current)
{
if (current != null)
{
inorder(current.left);
System.out.print(current.data + "\n");
inorder(current.right);
System.out.print(current.data + " " + "\n");
}
}
public void inorder()
{
inorder(root);
}
public void breadthFirst()
{
BSTNode current = root;
Queue queue = new Queue();
if (current != null)
{
queue.enqueue(current);
while (!queue.isEmpty())
{
current = (BSTNode) queue.dequeue();
System.out.print(current.data + "\n");
if (current.left != null)
queue.enqueue(current.left);
if (current.right != null)
queue.enqueue(current.right);
}
}
}
public void delete(Comparable key) {
BSTNode node, current = root, prev = null;
while (current != null && !current.key.equals(key)) { // find the node current
prev = current; // with element data;
if (current.key.compareTo(current.key) < 0)
current = current.right;
else current = current.left;
}
node = current;
if (current != null && current.key.equals(key)) {
if (node.right == null)
node = node.left;
else if (node.left == null)
node = node.right;
else {
BSTNode temp = node.left;
BSTNode previous = node;
while (temp.right != null) {
previous = temp;
temp = temp.right;
}
node.data = temp.data;
if (previous == node)
previous.left = temp.left;
else previous.right = temp.left;
}
if (current == root)
root = node;
else if (prev.left == current)
prev.left = node;
else prev.right = node;
}
else if (root != null)
System.out.println("Student " + key + " is not in the tree");
else System.out.println("the tree is empty");
}
}
Node:
public class BSTNode {
String data;
BSTNode left, right, root;
private String value ;
public Comparable key;
public BSTNode()
{
left = null;
right = null;
}
public BSTNode(Comparable key, String value)
{
this(key,value,null,null);
}
public BSTNode(Comparable key, String value, BSTNode lt, BSTNode rt)
{
setKey(key);
setValue(value);
left = lt;
right = rt;
}
public Object getValue(Comparable key) {
return value;
}
public void setValue(String value) {
data=value;
}
public void setKey(Comparable key) {
this.key = key;
}
}
Queue:
public class Queue {
private java.util.LinkedList list = new java.util.LinkedList();
public Queue() {
}
public void clear() {
list.clear();
}
public boolean isEmpty() {
return list.isEmpty();
}
public Object firstEl() {
return list.getFirst();
}
public Object dequeue() {
return list.removeFirst();
}
public void enqueue(Object el) {
list.add(el);
}
public String toString() {
return list.toString();
}
}
And the input file I am using is attached. Thanks again!