How to input a binary tree in Java

Question

I need help implementing a Binary Tree in Java.

I don't mean like reading it from a text file. I mean the user inputs the tree using a Scanner, and then it creates and outputs the tree values. Also, a "-" sign means a null value in the tree.

So far, I have a Node Class working, but I need it to be able to make a tree out of the said nodes. It also needs to know when to stop accepting inputs.

Here's the start of my code. I need a way to be able to input a list of nodes and make it into a tree using these classes.

import java.util.Scanner;  
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.Queue;
import java.util.LinkedList;


/**
 *
 * @author phirstprince
 */

class TreeNode {
    int data;
    TreeNode LC, RC;

    public TreeNode(int x) {
        data = x;
        LC = null;
        RC = null;
    }

}

  public class TreeDeserialize {

      /**
       * @param args the command line arguments
       */
        public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
          int x = input.nextInt(); 
      }

  }

Like for instance, if a person were to input this (the - being null nodes)

1
2
3
-
4
5
6
-
-
-
-
-
-

It would organize it into a tree like this.

         1
       /   \
      2     3
       \   / \
        4 5   6

Anyone think they can help? I believe it would require a queue. Also how to make sure it knows when to stop accepting inputs?

Answer 1

Here is a function that attempts to insert the new node going level-by-level from left to right. It is basically just doing a breadth-first traversal until it finds a place where it can insert the node.

public static void insert(TreeNode root, int x) {
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.offer(root);

    while(!q.isEmpty()) {
        TreeNode u = q.poll();

        if(u.LC == null) {   
            u.LC = new TreeNode(x);
            break;
        }

        if(u.RC == null) {
            u.RC = new TreeNode(x);
            break;
        }

        if(!u.LC.isNull)
            q.offer(u.LC);

        if(!u.RC.isNull)
            q.offer(u.RC);
    }
}

Note that for this to work you need to insert a special "null" node whenever the user enters "-". You can use a boolean flag in your TreeNode class for this:

class TreeNode {
    int data;
    boolean isNull;
    TreeNode LC, RC;

    public TreeNode(int x) {
        data = x;
        LC = null;
        RC = null;
    }

    public TreeNode() {
        isNull = true;
    }
}

Finally, you can overload the insert method to insert Null nodes when asked by the user. The overloaded function is the same except that it creates new TreeNodes using the default constructor:

public static void insert(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.offer(root);

    while(!q.isEmpty()) {
        TreeNode u = q.poll();

        if(u.LC == null) {   
            u.LC = new TreeNode();
            break;
        }

        if(u.RC == null) {
            u.RC = new TreeNode();
            break;
        }

        if(!u.LC.isNull)
            q.offer(u.LC);

        if(!u.RC.isNull)
            q.offer(u.RC);
    }
}

Your main method would then look like this:

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    int x = input.nextInt(); 
    TreeNode root = new TreeNode(x);

    while(true) {
        String str = input.next();
        if(str.equals("-"))
            insert(root);
        else
            insert(root, Integer.parseInt(str));
    }    
}

Answer 2

You should develop a method which checks the numbers and adds it to the, for example if the number greater than the parent it should add it to the right, if it is less than the parent it should add it to the left. I think you can develop this function with the help of recursion.