Saturday, 30 July 2016

Binary Search Tree Implementation

/*
 Write a program to implement simple Binary Search tree Implementation and demonstrate.
1) Inorder traversal
2) Postorder traversal
3) Preorder traversal
 */
package binary_search_tree;

import java.util.Scanner;

/**
 *
 * @author shabhatn
 */

class Node
{
   Node Left;
   Node Right;
   int data;
 
   public Node()
   {
       Left = null;
       Right = null;
       data = 0;
   }
 
   public Node(int data)
   {
       Left = null;
       Right = null;
       this.data = data;
   }

    public Node getLeft() {
        return Left;
    }

    public void setLeft(Node Left) {
        this.Left = Left;
    }

    public Node getRight() {
        return Right;
    }

    public void setRight(Node Right) {
        this.Right = Right;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

}

class Binary
{
    Node root;
    Node parent;
 
    public Binary()
    {
        root = null;
    }
 
    public void insert(int data)
    {
        root = insert(root,data);
    }
 
    public Node insert(Node node,int data)
    {
        if(node==null)
        {
             parent = node;
             node = new Node(data);
           
        }
        else
        {
         
                    if(data>=node.getData())
                    {
//                        if(node.getRight()==null)
//                            {

                        node.Right = insert(node.Right,data);
//                            }
                    }
         
                     else if(data<=node.getData())
                     {
//                        if(node.getLeft()==null)
//                        {
                        node.Left = insert(node.Left,data);
//                        }
                     }
        }
        return node;
    }
 
    public void preorder()
    {
        preorder(root);
    }
 
    public void preorder(Node node)
    {
        if(node!=null)
        {
        System.out.print(node.getData() + " ");
        preorder(node.getLeft());
        preorder(node.getRight());
        }
    }
 
    public void inorder()
    {
       inorder(root);
    }
 
    public void inorder(Node node)
    {
        if(node!=null)
        {
            inorder(node.getLeft());
        System.out.print(node.getData() + " ");
     
        inorder(node.getRight());
        }
    }
 
    public void postorder()
    {
        postorder(root);
    }
 
    public void postorder(Node node)
    {
        if(node!=null)
        {
     
        postorder(node.getLeft());
        postorder(node.getRight());
        System.out.print(node.getData() + " ");
        }
    }
 
}
public class Binary_Search_Tree {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
     
        Binary bt = new Binary();
        char ch;
        Scanner sc = new Scanner(System.in);
        do
        {
            System.out.print("insert the values");
            int data = sc.nextInt();
            bt.insert(data);
            System.out.print(" Do you want to insert the values");
         ch = sc.next().charAt(0);
        }while(ch=='y' || ch== 'Y');
        System.out.print("preorder traversal--->");
        bt.preorder();
        System.out.print("Inorder traversal--->");
        bt.inorder();
        System.out.print("Postorder traversal--->");
        bt.postorder();
     
    }
 
}

No comments:

Post a Comment