Aim: - Construction of Binary Search Tree for a given list
Binary Tree is a dynamic data structure, which means, that its size is only limited by amount of free memory. Binary search tree(BST) is also such type of data structure, which meets the following requirements:
· each node contains a value;
· a total order is defined on these values
· left subtree of a node contains only values lesser, than the node's value;
· right subtree of a node contains only values greater, than the node's value.
Binary search tree is used to construct map data structure. In practice, data can be often associated with some unique key. For instance, in the phone book such a key is a telephone number. Storing such a data in binary search tree allows to look up for the record by key faster, than if it was stored in unordered list. Also, BST can be utilized to construct set data structure, which allows storing an unordered collection of unique values and making operations with such collections.
Implementation:- BST can be implemented as a linked data structure in which each node is an object with three fields as represented below
Where the left-link and right-link are references to left and right sub-trees respectively otherwise NIL, signifies that there exists no corresponding child.
Example:- construction of BST for a List (6,3,2,9,1,5,4)
Summary:- Performance of a binary search tree depends on its height. In order to keep tree balanced and minimize its height, the idea of binary search trees was advanced in balanced search trees like AVL trees.
Java Program to Construct Binary Search Tree for a given list
import java.io.*;
class BinaryTree{
private Node root;
private static class Node {
Node left;
Node right;
int data;
public Node(int cdata) {
left=null;
right=null;
data=cdata;
}
}
public BinaryTree() throws Exception {
root=null;
}
public void insert(int data) {
root=insert(root,data);
}
public Node insert(Node node,int data){
if(node==null)
node=new Node(data);
else if(data<=node.data)
node.left=insert(node.left, data);
else
node.right=insert(node.right, data);
return(node);
}
public void Disp() {
if(root==null)
System.out.println(" No Elements in the Tree ") ;
else
{
inorder(root);
System.out.println("\n Height of the tree ===> "+height(root));
}
}
public int height(Node node){
if(node==null)
return(0);
return max( height(node.left)+1, height(node.right)+1);
}
int max(int a,int b)
{
return(a>b?a:b);
}
public void inorder(Node node){
if(node!=null)
{
inorder(node.left);
System.out.print(" "+node.data);
inorder(node.right);
}
}
public boolean lookup(int data) {
return(lookup(root,data));
}
public boolean lookup(Node node,int data){
if(node==null)
return false;
if(data==node.data)
return true;
if(data<node.data)
return(lookup(node.left,data));
return(lookup(node.right,data));
}
}
public class BST {
public static void main(String agrs[]) throws Exception {
BinaryTree B= new BinaryTree();
int n, item;
DataInputStream in= new DataInputStream(System.in);
System.out.print("Enter number of items to be inserted ");
n=Integer.parseInt(in.readLine());
System.out.println("Enter any "+n+" integers");
while(n>0)
{
item=Integer.parseInt(in.readLine());
B.insert(item);
n--;
}
System.out.print("Elements in the tree are ");
B.Disp();
System.out.print(" Enter item to be searched ");
item=Integer.parseInt(in.readLine());
if(B.lookup(item))
System.out.println("Sucessfull Search ");
Else
System.out.println("Unsucessfull Search ");
}
}
OUTPUT:
Enter number of items to be inserted7
Enter any 7 integers
6 3 2 9 8 5 4
Elements in the tree are 2 3 4 5 6 8 9
Height of the tree ===> 4
Enter item to be searched 5
Sucessfull Search
Enter item to be searched 1
UnSucessfull Search
No comments:
Post a Comment