Need Programming Assignment Help?

Get Help with Programming Assignment in Java, C/C++, Dot Net, PHP, Database and UML Diagrams

Java program to Implement Tree Set

Java program to Implement Tree Set

Java program to Implement Tree Set – This part of the Java Programming example explains how to implement Tree Set. TreeSet is a NavigableSet implementation based on a TreeMap.

import java.util.Scanner;

/** class TreeSetNode **/
 class TreeSetNode
 {
 String data;
 TreeSetNode left, right;

/** constructor **/
 public TreeSetNode(String data, TreeSetNode left, TreeSetNode right)
 {
 this.data = data;
 this.left = left;
 this.right = right;
 }
 }

/** class TreeSet **/
 class TreeSet
 {
 private TreeSetNode root;
 private int size;

/** constructor **/
 public TreeSet()
 {
 root = null;
 size = 0;
 }

/** function to check if empty **/
 public boolean isEmpty()
 {
 return root == null;
 }

/** function to clear **/
 public void clear()
 {
 root = null;
 size = 0;
 }

/** function to insert an element **/
 public void add(String ele)
 {
 root = insert(root, ele);
 }

/** function to insert an element **/
 private TreeSetNode insert(TreeSetNode r, String ele)
 {
 if (r == null)
 r = new TreeSetNode(ele, null, null);
 else
 {
 if (ele.compareTo(r.data) < 0)
 r.left = insert(r.left, ele);
 else if (ele.compareTo(r.data) > 0)
 r.right = insert(r.right, ele);
 }
 return r;
 }

/** Functions to count number of nodes **/
 public int countNodes()
 {
 return countNodes(root);
 }
 /** Function to count number of nodes recursively **/
 private int countNodes(TreeSetNode r)
 {
 if (r == null)
 return 0;
 else
 {
 int l = 1;
 l += countNodes(r.left);
 l += countNodes(r.right);
 return l;
 }
 }

/** Functions to search for an element **/
 public boolean contains(String ele)
 {
 return contains(root, ele);
 }
 /** Function to search for an element recursively **/
 private boolean contains(TreeSetNode r, String ele)
 {
 boolean found = false;
 while ((r != null) && !found)
 {
 if (ele.compareTo(r.data) < 0)
 r = r.left;
 else if (ele.compareTo(r.data) > 0)
 r = r.right;
 else
 {
 found = true;
 break;
 }
 found = contains(r, ele);
 }
 return found;
 }

/** Function to delete data **/
 public void delete(String ele)
 {
 if (isEmpty())
 System.out.println("Tree Empty");
 else if (contains(ele) == false)
 System.out.println("Error : "+ ele +" is not present");
 else
 {
 root = delete(root, ele);
 System.out.println(ele +" deleted from the tree set");
 }
 }
 /** Function to delete element **/
 private TreeSetNode delete(TreeSetNode r, String ele)
 {
 TreeSetNode p, p2, n;
 if (r.data.equals(ele))
 {
 TreeSetNode lt, rt;
 lt = r.left;
 rt = r.right;
 if (lt == null && rt == null)
 return null;
 else if (lt == null)
 {
 p = rt;
 return p;
 }
 else if (rt == null)
 {
 p = lt;
 return p;
 }
 else
 {
 p2 = rt;
 p = rt;
 while (p.left != null)
 p = p.left;
 p.left = lt;
 return p2;
 }
 }
 if (ele.compareTo(r.data) < 0)
 {
 n = delete(r.left, ele);
 r.left = n;
 }
 else
 {
 n = delete(r.right, ele);
 r.right = n;
 }
 return r;
 }

/** function toString() **/
 public String toString()
 {
 return "[ "+ inorder(root, "") +"]";
 }
 private String inorder(TreeSetNode r, String str)
 {
 if (r != null)
 return str + inorder(r.left, str) + r.data +" "+ inorder(r.right, str);
 else
 return "";
 }
 }

/** Class TreeSetTest **/
 public class TreeSetTest
 {
 public static void main(String[] args)
 {
 Scanner scan = new Scanner(System.in);

/** Creating object of TreeSetTest **/
 TreeSet ts = new TreeSet();

System.out.println("Tree Set Test\n");
 char ch;
 /** Perform set operations **/
 do
 {
 System.out.println("\nTree Set Operations\n");
 System.out.println("1. add ");
 System.out.println("2. delete");
 System.out.println("3. contains");
 System.out.println("4. count ");
 System.out.println("5. check empty");
 System.out.println("6. clear");

int choice = scan.nextInt();
 switch (choice)
 {
 case 1 :
 System.out.println("Enter element to insert");
 ts.add( scan.next() );
 break;
 case 2 :
 System.out.println("Enter element to delete");
 ts.delete( scan.next() );
 break;
 case 3 :
 System.out.println("Enter integer element to search");
 System.out.println("Search result : "+ ts.contains( scan.next() ));
 System.out.println();
 break;
 case 4 :
 System.out.println("Count = "+ ts.countNodes());
 break;
 case 5 :
 System.out.println("Empty status = "+ ts.isEmpty());
 break;
 case 6 :
 System.out.println("Tree set cleared");
 ts.clear();
 break;
 default :
 System.out.println("Wrong Entry \n ");
 break;
 }
 /** Display tree set **/
 System.out.print("\nTree Set : "+ ts);
 System.out.println();

System.out.println("\nDo you want to continue (Type y or n) \n");
 ch = scan.next().charAt(0);
 } while (ch == 'Y'|| ch == 'y');
 }
 }