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!

Attachments
I8534534McKay                    0251CT  1
I8400342LaPorte                  0045JA  1
I8499120Black                    0341RST 1
I8400912Green                    0045RFM 1
I8422911Johnston                 0341RST 1
I8212399Schafer                  0251EST 1
I8367091White                    0341TXT 1
I8412094Phillips                 0251EST 1
I8400001Smith                    0251CT  2
I8255999Sykes                    0451WET 2
I8300000Walker                   0341TXT 1
I8488431Hall                     0341RST 1
I8306700Jones                    0251CT  2
I8301164Bannister                0251EST 1
I8388231Woods                    0251CT  1
I8503881Appleford                0251EST 1
I8322189Hopper                   0251CT  1
I8322889Morrison                 0045JA  3
I8422991Card                     0045JA  2
I8399129Jordan                   0334ENT 1
I8300500Last                     0251CT  1
I8500000West                     0334ENT 1
I8301234Weston                   0334ENT 2
I8508883Fisher                   0341TXT 1
I8400000Watson                   0334ENT 2
I8599999Zot                      0451WET 1

You forgot to describe the error. It seems that you expect great feats from this forum if you hope it can give you advice without first knowing your problem. Fortunately, your problem is quite straight-forward.

Perhaps you are not aware of this, but BufferedReader.readLine takes a line from the file and returns it, so if you call readLine twice you will get two separate lines from the file, not the same line twice. Knowing that, look at your loop in main and count how many times you call readLine for each time you do an insert into the tree. To determine the cause of the NullPointerException you must be getting, count how many times you test record for null each time around the loop compared to how many times you assign record to a new line from the file. If you read a line without testing it for null, you are asking for a NullPointerException. If you read a line without inserting it into the tree, you are asking for names to be missed from your tree.

Edited 3 Years Ago by bguild

This article has been dead for over six months. Start a new discussion instead.