I need to implement a Binary search tree in Java (only insert and find) and then should be able to display the tree.
This is the code I've come up with so far. But I get the nullpointer exception. I am getting this because the two pointers in my node, leftChild and rightChild are set to null and don't point anywhere. But I don't know how to fix this. How do I make it so that they point to the correct nodes?
import java.util.*;
public class RBTTree
{
RBTNode root = null; //Root node of the tree
RBTNode currentNode = null;
//Checks to see if tree is empty. Prints out message if it is.
void IsEmpty()
{
if(root == null)
System.out.println("Tree is Empty");
}//End of IsEmpty
RBTNode create(int number)
{
RBTNode node = new RBTNode();
node.number = number;
node.parent = null;
node.leftChild = null;
node.rightChild = null;
//System.out.println("Node.data is: " +node.data);
return node;
}
//Method to insert a number into the tree.
public void insert(int number)
{
IsEmpty();
root = insert (root,number);
System.out.println("Node just inserted: " + root.number);
System.out.println("Node's left child: " + root.leftChild);
System.out.println("Node's right child: " + root.rightChild);
}
RBTNode insert(RBTNode node, int number)
{
if(node == null)// create a new node.
{
node = create(number);
}
else if(number < node.number)// if the number is less than the node, go to the left child.
{
node.leftChild = insert(node.leftChild,number);
}
else if(number > node.number)// if the number is greater than the node, go to the right child
{
node.rightChild = insert(node.rightChild,number);
}
else if(number == node.number) //if the number already exists in the the tree, place it in the right child.
{
node.rightChild = insert(node.rightChild, number);
}
return node;
}// end BSTNode insert
public void find(int number)
{
IsEmpty();
currentNode = find(root, number);
System.out.println("Search returned Node: " + currentNode.number);
System.out.println("Node's left child: " + currentNode.leftChild);
System.out.println("Node's right child: " + currentNode.rightChild);
}//End of find
RBTNode find(RBTNode currentNode, int number)
{
//currentNode = root; //sets the root node to the current node for searching purposes
while(currentNode.number != number && currentNode != null)
{
if(number < currentNode.number) //if number we are searching for is less than the node search left sub tree
{
currentNode = currentNode.leftChild;
}
else if(number > currentNode.number)//if number we are searching for is greater than the node search right sub tree
{
currentNode = currentNode.rightChild;
}
else //if number we are searching for is equal to the node search right sub tree
{
currentNode = currentNode.rightChild;
}
}
return currentNode;
}//End of RBTNode find
//Print all items.
public void printTree( )
{
display(root);
}
private void display(RBTNode currentNode)
{
if(root == null)
System.out.println("Empty Tree. Nothing to display");
else
{
display(currentNode.leftChild);
System.out.println(currentNode.number);
display(currentNode.rightChild);
}
}//End of display
public static void main(String[] args)
{
RBTTree RBT = new RBTTree();
Scanner console = new Scanner(System.in);
System.out.println("How many numbers would you like to enter into the Red Black Tree?");
int k = console.nextInt();
int inputarray[] = new int[k];
for(int i=0; i< k; i++)
{
System.out.println("Please enter the " + (i+1)+ " number: ");
inputarray[i]= console.nextInt();
}
for(int i=0; i<k; i++)
{
RBT.insert(inputarray[i]);
}
}
}//end of class RBTTreeMy RBTNode is here
class RBTNode
{
int number;
RBTNode parent;
RBTNode leftChild;
RBTNode rightChild;
}