//Binary Search Tree Implementation
class Node<E extends comperable<E>>
{
private E data;
private Node<E> left;
private Node<E> right;
public Node(E data)//constructor to initialize the value of left,right and data initialy
{
this.data=data;
left=null;
right=null;
}
public E getData()//getter for data
{
return data;
}
public void setData()//setter for data
{
this.data=data;
}
public Node<E> getLeft()//getter for left node
{
return left;
}
public void setLeft(Node<E> left)//setter for left node
{
this.left=left;
}
public Node<E> getRight()//getter for right node
{
return right;
}
public void setRight(Node<E> right)//setter for right node
{
this.right=right;
}
}
class BinarySearchTree<E extends comperable<E>>
{
private Node<E> root;//head
public Node<E> getRoot()
{
return root;
}
//insertion
public void insert(E element)
{
Node<E> node=new Node<>(element);
//empty
if(isEmpty())
{
root=node;
}
else
{
Node<E> temp=root;
Node<E> parent=null;
while(temp!=null)
{
parent=temp;
if(element.compareTo(temp.getData())<=0)//element<=temp.getData()
{
//left subtree duplicate values are allowed that's why we are taking equal symbol
temp=temp.getLeft();
}
else
{
temp=temp.getRight();
}
}
//check whether new node will be left child or right child of parent node
if(element.compareTo(parent.getData())<=0)
{
//left child
parent.setLeft(node);
}
else
{
//right child
parent.setRight(node);
}
}
}
private boolean isEmpty()
{
if(root==null)
{
return true;
}
return false;
}
public boolean search(E searchElement)
{
boolean response=false;
Node<E> temp=root;
while(temp!=null)
{
if(searchElement.compareTo(temp.getData())==0)
{
response=true;
break;
}
else if(searchElement.compareTo(temp.getData())<0)
{
temp=temp.getLeft();
}
else
{
temp=temp.getRight();
}
}
return response;
}
//traversal
//Inorder(left, root,right)
//Preorder(root,left,right)
//Postorder(left,right,root)
public void inOrder(Node<E> node)
{
inOrder(node.getLeft());
System.out.println(node.getData()+", ");
inOrder(node.getRight());
}
public void preOrder(Node<E> node)
{
//step 1
System.out.println(node.getData()+", ");
//step 2 process left subtree in preorder
//recursion
preOrder(node.getLeft());
//step 3
preOrder(node.getRight());
}
public void postOrder(Node<E> node)
{
postOrder(node.getLeft());
postOrder(node.getRight());
System.out.println(node.getData()+", ");
}
}
//main class should be like this
class BinaryST
{
public static void main(String args[])
{
Student<Integer> obj=new Student<>();
}
}
Expected:
0 Comments