Sunday, June 8, 2014
Today in this article I will tell you how to create a generic binary search tree (BST) in Java. A normal binary tree is any tree where each node can have a maximum of 2 nodes. But binary search tree is a special kind of binary tree which when traveresed using inorder traversal algorithm lists the nodes in ascending order. In this article we will not deal with traversal, and only concentrate on creating and generating the BST.
The code is written to support generics. This means that only one code has to be written for binary search tree(BST). You can insert anything in the tree but the objects must be comparable. Comparable objects here means that classes of those objects must extend java.lang.Comparable interface. The comments are also added to the code in Javadoc style
Here in our code we have a class called BinarySearchTree, a generic class with type parameter T; which contains an inner class Node. The node class is used to define each node of the tree  containing two pointers for left and right subtree and a value parameter to contain value of the node. Next is insert(T) method which is called by the user to insert new nodes. This function adds root if tree is empty, otherwise calls a private insert(Node,T) method with root node and vakue passed as parameter. The private inner(Node,T) is a recursive one which adds node recursively depending on the value  added to left subtree if less than parent else added to right subtree. The other two methods are very trivial isEmpty() to check if tree is empty and peek() to return the value of root.

The code is written to support generics. This means that only one code has to be written for binary search tree(BST). You can insert anything in the tree but the objects must be comparable. Comparable objects here means that classes of those objects must extend java.lang.Comparable interface. The comments are also added to the code in Javadoc style
Here in our code we have a class called BinarySearchTree, a generic class with type parameter T; which contains an inner class Node. The node class is used to define each node of the tree  containing two pointers for left and right subtree and a value parameter to contain value of the node. Next is insert(T) method which is called by the user to insert new nodes. This function adds root if tree is empty, otherwise calls a private insert(Node,T) method with root node and vakue passed as parameter. The private inner(Node,T) is a recursive one which adds node recursively depending on the value  added to left subtree if less than parent else added to right subtree. The other two methods are very trivial isEmpty() to check if tree is empty and peek() to return the value of root.

Java Source Code
public class BinarySearchTree<T extends Comparable<T>> { //T is the type parameter and comparable Node root; //root node of the tree //defines each node of tree class Node{ T value; //value of node Node right,left; //pointer to left and right subtree Node(T value){ this.value = value; } } /** * This method inserts new node in tree * @param value */ public void insert(T value){ if(isEmpty()) root = new Node(value); //root node added else insert(root, value); //if not empty then insert based on root } /** * Recursive method is called internally to insert nodes at proper places depending on their vakues. * @param node * @param value */ private void insert(Node node, T value){ if(value.compareTo(node.value) < 0){ //if new value less than parent node if(node.left == null) //if left null then add node.left = new Node(value); else insert(node.left,value); //if left not null then recursive call } else if(value.compareTo(node.value) >= 0){ //if new value same or greater than parent node if(node.right == null) //if right null then add node.right = new Node(value); else insert(node.right,value); //if right not null then recursive call } } /** * Returns the value of the root * @return */ public T peek(){ return root.value; } /** * Checks if tree is empty or not * @return */ public boolean isEmpty(){ return (root == null)? true : false; } }
Download Links
DOWNLOAD the source from Mediafire
DOWNLOAD the source from 4shared
Happy coding :)
Labels:Algorithms,Generics
Subscribe to:
Post Comments
(Atom)
Labels
 Algorithms (7)
 Annotation (3)
 Files (6)
 Generics (3)
 Graphics2D (5)
 Graphics2DImages (7)
 Inheritance (2)
 J2EE (9)
 Java 8 (4)
 Java FAQs (19)
 JDBC (3)
 Networking (2)
 Packages (1)
 Reflection (4)
 Security (7)
 Sorting (2)
 Swing (3)
 Threads (3)
 Utils (3)
Popular Posts

Today I will show you how you can implement Bankers algorithm in Java. The Banker's algorithm is a resource allocation and deadlock a...

 UPDATE  I have updated the code on request of some followers so that they can directly...

Today I am going to show how to convert a postfix expression to an infix expression using stack in Java. In an earlier post here we ...

Today in this article I will tell you how to convert an infix expression to postfix expression using stack. This is an important applicat...

UPDATE I have updated my post so that now it can detect IE 11. This modification was necessary as t...

Today I am going to show you how you can generate and validate captcha. A CAPTCHA (an acronym for "Completely Automated Public Turin...

Today I am going to post a program that will be able to produce all the mColorings of a given graph G. What is mColoring : The problem st...

Today I will show you how to do 256bits AES encryption and decryption of a file in Java. You can write codes for AES  128bits without d...
Links
About Me

Nirupam Das
 I am a student of BTech Computer Science Engineering from RCCIIT,Kolkata. I am a crazy lover of Java and wants to settle as a Java developer. I have a seven years Java experience with an application developer experience for 2 years. Recently from March 2012 I am a registered S40 app developer for Nokia and has corrected an app of them. I am currently writing blogs to encourage and grow interest in all those who don't know or learning Java.
0 comments:
Post a Comment