Category Archives: Data structure

Implementation of Data Structure in Java

Binary Tree Insertion, Deletion, Search, Traversal in Java

Basic traversal on tree is best explained on http://en.wikipedia.org/wiki/Tree_traversal .

In Order:


binary_tree_inorder

 

Pre Order:

binary_tree_preorder

 

 

Post Order:

binary_tree_postorder

 

If anything is missing in explanation, you can google it and I know you all are expert as me.
Now my part starts from here.
How to implement it in java.

Project Structure in Eclipse:

Tree_projectStructure

Node.java    (nodeInfo variable has no logical meaning, it is just for printing purpose)

package datastructure.tree;

public class Node {
	
	private Node leftNode;
	private Node rightNode;
	private int nodeValue;
	private String nodeInfo;
	
	public Node(String nodeInfo,int nodeValue){
		this.nodeInfo = nodeInfo;
		this.nodeValue = nodeValue;
	}
	
	public Node getLeftNode() {
		return leftNode;
	}
	public void setLeftNode(Node leftNode) {
		this.leftNode = leftNode;
	}
	public Node getRightNode() {
		return rightNode;
	}
	public void setRightNode(Node rightNode) {
		this.rightNode = rightNode;
	}
	public int getNodeValue() {
		return nodeValue;
	}
	public void setNodeValue(int nodeValue) {
		this.nodeValue = nodeValue;
	}
	public String getNodeInfo() {
		return nodeInfo;
	}
	public void setNodeInfo(String nodeInfo) {
		this.nodeInfo = nodeInfo;
	}
}

 

Tree.java

package datastructure.tree;

public interface Tree {

	void insertNode(Node node);
	void deleteNode(Node node);
	Node searchNode(Node node);
	
	void inOrderTraversal(Node node);
	void preOrderTraversal(Node node);
	void postOrderTraversal(Node node);
}

 

TreeImpl.java

 

package datastructure.tree;

public class TreeImpl implements Tree{

	int tree_node_count = 0;
	public Node rootNode = null;
	
	public Node getRootNode() {
		return rootNode;
	}

	public void setRootNode(Node rootNode) {
		this.rootNode = rootNode;
	}

	public TreeImpl(Node rootNode){
		this.rootNode = rootNode;
		tree_node_count = 1;
	}

	@Override
	public void insertNode(Node node){
		Node treeNode = rootNode;
		
		while(true){
			if(node.getNodeValue()<treeNode.getNodeValue()){
				if(treeNode.getLeftNode()!=null){
					treeNode = treeNode.getLeftNode();
				}else{
					treeNode.setLeftNode(node);
					System.out.println("Node "+node.getNodeValue()+" saved at left child of node :"+treeNode.getNodeValue());
					break;
				}
			}else if(node.getNodeValue()>treeNode.getNodeValue()){
				if(treeNode.getRightNode()!=null){
					treeNode = treeNode.getRightNode();
				}else{
					treeNode.setRightNode(node);
					System.out.println("Node "+node.getNodeValue()+" saved at Right child of node :"+treeNode.getNodeValue());
					break;
				}
			}else{
				System.out.println("Duplicate Node can not be saved");
				break;
			}
		}
	}
	
	@Override
	public Node searchNode(Node node){
		Node currentNode = rootNode;
		while(currentNode!=null){
			if(currentNode.getNodeValue()==node.getNodeValue()){
				System.out.println("Node "+node.getNodeValue()+" Found");
				return currentNode;
			}else{
				if(node.getNodeValue()<currentNode.getNodeValue()){
					currentNode = currentNode.getLeftNode();
				}else{
					currentNode = currentNode.getRightNode();
				}
			}
		}
		System.out.println("Node "+node.getNodeValue()+" Not Found");
		return null;
	}


	@Override
	public void deleteNode(Node node) {
		Node previousNode =  null;
		Node currentNode = rootNode;
		
		if(node.getNodeValue()==currentNode.getNodeValue()){
			System.out.println("Your Tree is Vanished");			
		}else if(node.getNodeValue()<currentNode.getNodeValue()){
			previousNode = currentNode;
			currentNode = currentNode.getLeftNode();
		}else{
			previousNode = currentNode;
			currentNode = currentNode.getRightNode();
		}
		
		while(true){
			if(node.getNodeValue()==currentNode.getNodeValue()){
				
				
				if(currentNode.getRightNode()!=null){
					Node tempPreviousNode = currentNode;
					Node tempNode = currentNode.getRightNode();
					
					if(tempNode.getLeftNode()!=null){
						while(tempNode.getLeftNode()!=null){
							tempPreviousNode = tempNode;
							tempNode = tempNode.getLeftNode();
						}
						
						if(tempNode.getRightNode()!=null){
							tempPreviousNode.setLeftNode(tempNode.getRightNode());
							previousNode.setRightNode(tempNode);
							tempNode.setLeftNode(currentNode.getLeftNode());
							break;
						}else{
							tempNode.setLeftNode(currentNode.getLeftNode());
							tempNode.setRightNode(currentNode.getRightNode());
							previousNode.setRightNode(tempNode);
							tempPreviousNode.setLeftNode(null);
							break;
						}
					}else{
						tempNode.setLeftNode(currentNode.getLeftNode());
						previousNode.setRightNode(tempNode);
						break;
					}					
				}else if(currentNode.getLeftNode()!=null){
					previousNode.setLeftNode(currentNode.getLeftNode());
					currentNode = null;
					break;
				}else{
					currentNode = null;
					break;
				}				
			}else if(node.getNodeValue()<currentNode.getNodeValue()){
				previousNode = currentNode;
				currentNode = currentNode.getLeftNode();
			}else{
				previousNode = currentNode;
				currentNode = currentNode.getRightNode();
			}
		}
	}

	@Override
	public void inOrderTraversal(Node node) {
	
		if(node!=null){
			inOrderTraversal(node.getLeftNode());
			System.out.println("Node Value:"+node.getNodeValue());
			inOrderTraversal(node.getRightNode());
		}
	}

	@Override
	public void preOrderTraversal(Node node) {
		// TODO Auto-generated method stub
		if(node!=null){
			System.out.println("Node Value:"+node.getNodeValue());
			preOrderTraversal(node.getLeftNode());
			
			preOrderTraversal(node.getRightNode());
		}
	}

	@Override
	public void postOrderTraversal(Node node) {
		// TODO Auto-generated method stub
		if(node!=null){
			postOrderTraversal(node.getLeftNode());
			
			postOrderTraversal(node.getRightNode());
			System.out.println("Node Value:"+node.getNodeValue());
		}
	}
}

MainPractise,java

import datastructure.tree.Node;
import datastructure.tree.TreeImpl;



public class MainPractise implements Cloneable{	
	
	public static void main(String[] args) {
		
		Node node = new Node("Root Node",12);
		
		TreeImpl ti = new TreeImpl(node);
		
		Node leafNode = new Node("Leaf Node",5);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",16);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",2);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",1);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",3);
		ti.insertNode(leafNode);
		
		leafNode = new Node("Leaf Node",15);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",19);
		ti.insertNode(leafNode);

		leafNode = new Node("Leaf Node",18);
		ti.insertNode(leafNode);
		
		Node deleteNode = new Node("Leaf Node",16);
		ti.deleteNode(deleteNode);
		
		System.out.println("==============In Order Traversal===================");
		ti.inOrderTraversal(ti.getRootNode());
		System.out.println("==============Pre Order Traversal==================");
		ti.preOrderTraversal(ti.getRootNode());
		System.out.println("==============Post Order Traversal=================");
		ti.postOrderTraversal(ti.getRootNode());
		
		
		System.out.println("===================================================");
		Node searchNode = new Node("Leaf Node", 17);
		ti.searchNode(searchNode);
		
		searchNode = new Node("Leaf Node", 3);
		ti.searchNode(searchNode);
       }
}

 

 

Output:

Node 5 saved at left child of node :12
Node 16 saved at Right child of node :12
Node 2 saved at left child of node :5
Node 1 saved at left child of node :2
Node 3 saved at Right child of node :2
Node 15 saved at left child of node :16
Node 19 saved at Right child of node :16
Node 18 saved at left child of node :19
==============In Order Traversal===================
Node Value:1
Node Value:2
Node Value:3
Node Value:5
Node Value:12
Node Value:15
Node Value:18
Node Value:19
==============Pre Order Traversal==================
Node Value:12
Node Value:5
Node Value:2
Node Value:1
Node Value:3
Node Value:18
Node Value:15
Node Value:19
==============Post Order Traversal=================
Node Value:1
Node Value:3
Node Value:2
Node Value:5
Node Value:15
Node Value:19
Node Value:18
Node Value:12
===================================================
Node 17 Not Found
Node 3 Found

 

I haven’t defined any methods of isEmpty() and as such methods. So if you need one let me know.

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

Stack implementation using Array

Stack is an abstract data type.
Basic operation of stack can be:

1. Push :
Push object on top of stack.
Throw exception if stack is full.

2. Pop :
Take out(remove) object that is on top of stack .
Throw exception if stack is empty.

3. Top:
Read the object that is on top of stack.
Throw exception if stack is empty.

Now we need to implement these all operation in Java using Object Array.

Below is my eclipse folder structure. You may find this common but keeping all beginners in mind so please bare with me.

ArrayStack

Lets define an interface for a stack:

package datastructure.stack;

public interface Stack {

	//accessor method stack
	public int size();
	public boolean isEmpty();
	public Object top() throws Exception;
	
	//update method stack
	public void push(Object element) throws Exception;
	public Object pop() throws Exception;
}

 

 

 

Now we need to implement these functionality. So will be implementing this interface by our class called ArrayStack.java.

package datastructure.stack;

public class ArrayStack implements Stack {
	
	private Object stack[];
	private int capacity;
	private int currentPos=-1;
	
	public ArrayStack(int capacity){
		this.capacity = capacity;
		stack = new Object[capacity];
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return this.capacity;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		if(currentPos<0){
			return true;
		}
		return false;
	}

	@Override
	public Object top() throws Exception {
		// TODO Auto-generated method stub	
		if(currentPos<0){
			throw new Exception(" Stack is Empty");
		}
		return stack[currentPos];
	}

	@Override
	public void push(Object element) throws Exception {
		// TODO Auto-generated method stub
		if(currentPos==capacity){
			throw new Exception();
		}
		stack[++currentPos] = element;
	}

	@Override
	public Object pop() throws Exception {
		// TODO Auto-generated method stub
		if(currentPos<0){
			throw new Exception();
		}
		return stack[currentPos--] = null;
	}

}

 

 

As you can see in the ArrayStack.java,
we define constructor to initialize the size of our stack. This size will set the limit on number of element in stack.
So let me just briefly explain about class variable and methods.

Object stack[] : An array which is going to be our stack(element holder)
int capacity : Max size of Stack
int currentPos : It is pointer of top element of stack. We will need to increment it when any element is pushed, decrement it when we do the pop operation. Initially we kept it -1 as first element will have index 0. So if there is no element it should be -1.

public int size()                                 : Gives you the capacity of Stack, which was set at the time of initialization.
public boolean isEmpty()                : Gives you true/false based on currentPos pointer.
public Object top()                            : Return the object that is there on top of stack. It does not remove it. And if there is no element that it will                                                                        throw exception.
public void push(Object element) :  Push the object specified as the parameter. If stack is full than it will throw exception.
public Object pop()                           :  Remove the element that is there on top of stack. If stack is empty it will throw the exception.

So thats all everyone. Below is some basic operation that I ran and the output of it.

import datastructure.stack.ArrayStack;

public class MainPractise {

	public static void main(String[] args) {		
		
		ArrayStack as = new ArrayStack(10);  // Stack can have at max 10 element
		try{
			System.out.println("Stack size:"+as.size());
			as.push("Nirav"); // push String object in stack
			as.pop(); // pop Nirav out of stack 🙁
			as.push("Nihar");
			String topString = (String)as.top(); // chek out nihar 😛
			System.out.println(topString); /* U will see stubborn nihar string object 
			                                print out bt the object will still be there */
			
			as.pop(); // Now There is no element in stack
			as.pop(); // it will throw exception as stack is empty
		}catch(Exception e){
			System.out.println("Exception message:"+e.getMessage());
		}
		
	}
}

The output of above code is:

Stack size:10
Nihar
Exception message:Stack is Empty

This is it.

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

If you have any question mail us on
snippetexample@gmail.com or Post comments or join us on facebook.