Java program to implement Binary Search Tree

A very generic Binary Search Tree implementation in Java


package lab.tree;

import lab.general.Processable;


public class Tree {

public TreeNode root;

public Tree()
{
root=null;
}

public void insert(Object info)
{

Comparable compdata;

compdata=(Comparable)info;

TreeNode newnode=new TreeNode();
newnode.data=info;



if(root==null)
{
root=newnode;
root.left=null;
root.right=null;
return;

}

TreeNode tmpnode;
tmpnode=root;
while(tmpnode!=null)
{
if((compdata.compareTo(tmpnode.data))<0 )
{
if(tmpnode.left==null)
{
tmpnode.left=newnode;
return;
}
else
{
tmpnode=tmpnode.left;
}

}
else
{
if(tmpnode.right==null)
{
tmpnode.right=newnode;
return;
}
else
{
tmpnode=tmpnode.right;
}
}
}
}




public void inorder(TreeNode rootnode)
{
  if(rootnode !=null)
  {
 Processable info;

 inorder(rootnode.left);
      info=(Processable)rootnode.data;
      info.process();
      inorder(rootnode.right);
 }

 
}

public void preorder(TreeNode rootnode)
{
  if(rootnode !=null)
  {
 Processable info;

 info=(Processable)rootnode.data;
      info.process();
 preorder(rootnode.left);
      preorder(rootnode.right);
 }

  
}


public void postorder(TreeNode rootnode)
{
  if(rootnode !=null)
  {
 Processable info;

 postorder(rootnode.left);
      postorder(rootnode.right);
      info=(Processable)rootnode.data;
      info.process();
 }

 
}







}

Stack Implementation - Java Program

A Java implementation of stack using Linked List. It uses Linked List which can be found here.




package lab.stack;

import lab.linkedlist.*;

public class Stack 
{

LinkedList stackList;

public Stack()
{
stackList=new LinkedList();
stackList.headnode=null;

}

public void push(Object data)
{

    stackList.insertBegining(data);

}

public Object pop()
{
return stackList.getFirstinList();
}

}

Queue implementation - Java program

A Java implementation of Queue is given below. The implementation uses LinkedList  which can be found here.


package lab.queue;

import lab.linkedlist.*;

public class Queue {

private LinkedList queuelist;

public Queue()
{
queuelist=null;
}


public void enqueue(Object info)
{

  if(queuelist==null)
   {
queuelist=new LinkedList();
queuelist.insertEnd(info);
   }
  else
  {
queuelist.insertEnd(info);
  }

}

public Object dequeue()
{

if(queuelist==null)
{
return null;
}
else
{
Object tmp=new Object();
tmp=queuelist.getFirstinList();
queuelist.deleteFirstInList();
return tmp;
}

}


}

Linked List implementation - Java program

Java implementation of the Linked List  is given below.





package lab.linkedlist;



public class LinkedList
{


public ListNode headnode;
public ListNode currentNode;
public ListNode lastnode;


public LinkedList()
{
headnode=null;  
currentNode=null;
lastnode=null;
}


public void insertBegining(Object info)
{
ListNode tmpnode=new ListNode();
tmpnode.data=info;
if(headnode==null)
{
tmpnode.nextnode=null;
lastnode=tmpnode;
}
else
{
tmpnode.nextnode=headnode;
}
headnode=tmpnode;
}






public Object getFirstinList()
{
if (headnode!=null)
{
return headnode.data;
}
else
{
return null;
}
}




public void deleteFirstInList()
{
if(headnode!=null)
{
headnode=headnode.nextnode;
}
else
{
return;
}

}


public Object getNextNode()
{
ListNode temp=currentNode;
if(currentNode==null)
{return null;}
else{
currentNode=currentNode.nextnode;
     return temp.data ;
   }
}

public void startIterator()
{
currentNode=headnode;
}


public void insertEnd(Object info)
{
ListNode tmpnode=new ListNode();
tmpnode.data=info;
if(headnode==null)
{
headnode=tmpnode;
}
else
{
lastnode.nextnode=tmpnode;
}
tmpnode.nextnode=null;
lastnode=tmpnode;
}


}





package lab.general;


public class Node {


public Object data;

public Node(Object dat){
data=dat;
               }


public Node()
{
data=null;
}
}

package lab.linkedlist;

import lab.general.Node;

public class ListNode extends Node {

ListNode nextnode;

}