This post is a part of my continuous effort to just implement few of the important data structures in Java. Please find my previous post on LinkedList and QuickSort. This post is regarding BST (Binary Search Tree).
Let’s first declare the structure of a BST Node
/**
* BST Node Structure
* @author prasanta
*/
public class BST_Node {
/**
* Left subtree pointer
*/
BST_Node left;
/**
* Right subtree pointer
*/
BST_Node right;
/**
* key which is used for comparison
*/
int value;
}
Add Node into BST
BST_Node root;
public void insert(int value){
root = add(root, value);
}
private BST_Node add(BST_Node node, int value){
if(node == null){
node = new BST_Node();
node.value = value;
return node;
}
if(value < node.value)
// Left Node (<)
node.left = add(node.left, value);
else
// Right Node (>=)
node.right = add(node.right, value);
return node;
}
So your Binary Search Tree is complete and you can refer it using root. There are multiple ways you can traverse a BST- Pre-Order, In-Order, Post-Order and Level-Order (get more details on WiKi- http://en.wikipedia.org/wiki/Tree_traversal). Here I’ll show implementation of Pre-Order and In-Order, as I’m facing some problem with my Post-Order implementation.
Pre-Order Traversal- (it’s simple; the recursive call is doing the trick). The below function will display BST node values in Pre-Order
public void preOrder(BST_Node node){
// root-left-right
if(node == null)
return;
System.out.print(node.value+" ");
preOrder(node.left);
preOrder(node.right);
}
In-Order Traversal- well this is really a smart traversal method. It will return you a sorted list. Again, recursion is doing the trick.
/**
* This will give you the sorted list. So to sort a list of random
* order element- Create a BST and do In-Order traversal,
* Bingo! It’s sorted
* @param node
*/
public void inOrder(BST_Node node){
// left-root-right
if(node == null)
return;
inOrder(node.left);
System.out.print(node.value+ " ");
inOrder(node.right);
}
public boolean search(int x){
round = 0;
return find(root, x);
}
private boolean find(BST_Node node, int x){
if(node == null){
return false;
}
// how many iteration required
round++;
if(x == node.value)
return true;
else if(x < node.value)
return find(node.left, x); // you'll get it on the left branch
else
return find(node.right, x); // you'll get it on right branch
}
0 comments:
Post a Comment