How to rotate Binary Tree recursion given a null stopper

258 views Asked by At

I'm reading Strings from a file and have recorded '~' whenever the child of a node is null. I am then taking those strings and adding them to a Binary Tree. BUT my code is simply adding all the Strings (inclusive of the '~') into left tree nodes.

How do i get the algorithm to stop adding left nodes when a '~' is reached and to insert a right node (unless of course the next String is also a '~') ?

Here's my code:

// Reads the elements in the tree in pre-order
public void fromFile()
{
   BufferedReader in;
   String s = null;
   try {
        in = new BufferedReader(new FileReader("animal_game.txt"));
        StringBuffer stringBuffer = new StringBuffer();
        while( (s=in.readLine()) != null )
        {

            stringBuffer.append(s);
            stringBuffer.append("\n");

        }

        fromFile(stringBuffer.toString());


        in.close();
   } 
   catch (IOException ex) 
   {
           Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
   } 

}

public void fromFile(String s)
{
    if (root == null)
    {
        root = new Node<>((T)s);
        size++;
    } 
    else 
    {
        fromFile(root, s);   
    }
}

// helper function
private void fromFile( Node<T> node, String s) 
{
        // if null tree node reached, 
        if(s==NULL_TREE_NODE)
        {
            fromFile(node, s);
        }

        // insert left node
        if (node.no == null) 
        {
            node.no = new Node<>((T)s);
        } 
        else 
        {
            fromFile(node.no, s);
        }

        // insert right node
        if (node.yes == null) 
        {
            node.yes = new Node<>((T)s);
        } 
        else{
            fromFile(node.yes, s);
        }
}

This is my code that saves the tree to a file:

// Writes the elements in the tree in pre-order
public void toFile()
{
    // Writes in preorder starting with the root node
    if (root != null) 
    {
        BufferedWriter out;
        try {
            out = new BufferedWriter(new FileWriter("animal_game.txt"));
            toFile(out, root);
            out.close();
        } 
        catch (IOException ex) 
        {
            Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
        } 
    }
}

// Helper function
private void toFile(BufferedWriter out, Node<T> node) 
{
    try {

        if (node == null) {
        out.write(NULL_TREE_NODE); // null
        out.newLine();
        return;
    }
    //assert !node.data.equals(NULL_TREE_NODE); // Reserver for us..
    out.write((String)node.data); // these nodes hold Strings
    out.newLine();
    toFile(out, node.no);
    toFile(out, node.yes);

    } 
    catch (IOException ex) 
    {
        Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
    }

}

and this is my file


Is it a mammal?

Is it a reptile?

Is it a fish?

Pelican

~

~

Shark

~

~

Is it extinct?

Turtle

~

~

Velociraptor

~

~

Does it have fur?

Elephant

~

~

Cat

1

There are 1 answers

0
Straw1239 On

You should change your fromFile() to match your toFile(): instead of accepting a Node and a String representing the whole file, take a BufferedReader, allowing it to easily read off individual lines. In addition, change the helper build function to return a Node so it can return null in case of a ~ node. Then, the whole tree can be build recursively, returning null back up the tree when ~ nodes are reached:

 private Node<T> fromFile(BufferedReader s) throws IOException
    {

            String line = s.readLine();
            if(line == null) throw new IllegalArgumentException("File does not specify complete tree");
            // if null tree node reached, 
            if(line.equals(NULL_TREE_NODE)) return null;
            Node<T> node = new Node<>();
            node.data = line;
            node.no = fromFile(s);
            node.yes = fromFile(s);
            return node;
    }

Then, slightly adjust your fromFile():

public void fromFile()
{
   try(BufferedReader in = new BufferedReader(new FileReader("animal_game.txt"))) 
   {
        root = fromFile(in);
   } 
   catch (IOException ex) 
   {
           Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
   } 

}

I have also modified it to use a try-with-resources statement for ease, and guarantee of proper resource release on exception. See http://docs.oracle.com/javase/tutorial/essential/exceptions/tryResourceClose.html

Hope this helps.