Java Program to Implement Tree Set

«
»
This is a Java program to Implement Tree Set. A set is an abstract data structure that can store certain values, without any particular order, and no repeated values. Here Tree set maintains sorted order.

Here is the source code of the Java program to Implement Tree Set. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  * Java program to implement Tree Set
  3.  */
  4.  
  5. import java.util.Scanner;    
  6.  
  7. /** class TreeSetNode **/
  8. class TreeSetNode
  9. {
  10.     String data;
  11.     TreeSetNode left, right;
  12.  
  13.     /** constructor **/
  14.     public TreeSetNode(String data, TreeSetNode left, TreeSetNode right)
  15.     {
  16.         this.data  = data;
  17.         this.left  = left;
  18.         this.right = right;
  19.     }    
  20. }
  21.  
  22. /** class TreeSet **/
  23. class TreeSet
  24. {
  25.     private TreeSetNode root;
  26.     private int size;
  27.  
  28.     /** constructor **/
  29.     public TreeSet()
  30.     {
  31.         root = null;
  32.         size = 0;
  33.     }
  34.  
  35.     /** function to check if empty **/
  36.     public boolean isEmpty()
  37.     {
  38.         return root == null;
  39.     }
  40.  
  41.     /** function to clear **/
  42.     public void clear()
  43.     {
  44.         root = null;
  45.         size = 0;
  46.     }
  47.  
  48.     /** function to insert an element **/
  49.     public void add(String ele)
  50.     {
  51.         root = insert(root, ele);
  52.     }
  53.  
  54.     /** function to insert an element **/
  55.     private TreeSetNode insert(TreeSetNode r, String ele)
  56.     {
  57.         if (r == null)
  58.             r = new TreeSetNode(ele, null, null);
  59.         else
  60.         {
  61.             if (ele.compareTo(r.data) < 0)
  62.                 r.left = insert(r.left, ele);
  63.             else if (ele.compareTo(r.data) > 0)
  64.                 r.right = insert(r.right, ele);
  65.         }
  66.         return r;
  67.     }
  68.  
  69.     /** Functions to count number of nodes **/
  70.     public int countNodes()
  71.     {
  72.         return countNodes(root);
  73.     }
  74.     /** Function to count number of nodes recursively **/
  75.     private int countNodes(TreeSetNode r)
  76.     {
  77.         if (r == null)
  78.             return 0;
  79.         else
  80.         {
  81.             int l = 1;
  82.             l += countNodes(r.left);
  83.             l += countNodes(r.right);
  84.             return l;
  85.         }
  86.     }
  87.  
  88.     /** Functions to search for an element **/
  89.     public boolean contains(String ele)
  90.     {
  91.         return contains(root, ele);
  92.     }
  93.     /** Function to search for an element recursively **/
  94.     private boolean contains(TreeSetNode r, String ele)
  95.     {
  96.         boolean found = false;
  97.         while ((r != null) && !found)
  98.         {
  99.             if (ele.compareTo(r.data) < 0)
  100.                 r = r.left;
  101.             else if (ele.compareTo(r.data) > 0)
  102.                 r = r.right;
  103.             else
  104.             {
  105.                 found = true;
  106.                 break;
  107.             }
  108.             found = contains(r, ele);
  109.         }
  110.         return found;
  111.     }
  112.  
  113.     /** Function to delete data **/
  114.     public void delete(String ele)
  115.     {
  116.         if (isEmpty())
  117.             System.out.println("Tree Empty");
  118.         else if (contains(ele) == false)
  119.             System.out.println("Error : "+ ele +" is not present");
  120.         else
  121.         {
  122.             root = delete(root, ele);
  123.             System.out.println(ele +" deleted from the tree set");
  124.         }
  125.     }
  126.     /** Function to delete element **/
  127.     private TreeSetNode delete(TreeSetNode r, String ele)
  128.     {
  129.         TreeSetNode p, p2, n;
  130.         if (r.data.equals(ele))
  131.         {
  132.             TreeSetNode lt, rt;
  133.             lt = r.left;
  134.             rt = r.right;
  135.             if (lt == null && rt == null)
  136.                 return null;
  137.             else if (lt == null)
  138.             {
  139.                 p = rt;
  140.                 return p;
  141.             }
  142.             else if (rt == null)
  143.             {
  144.                 p = lt;
  145.                 return p;
  146.             }
  147.             else
  148.             {
  149.                 p2 = rt;
  150.                 p = rt;
  151.                 while (p.left != null)
  152.                     p = p.left;
  153.                 p.left = lt;
  154.                 return p2;
  155.             }
  156.         }
  157.         if (ele.compareTo(r.data) < 0)
  158.         {
  159.             n = delete(r.left, ele);
  160.             r.left = n;
  161.         }
  162.         else
  163.         {
  164.             n = delete(r.right, ele);
  165.             r.right = n;             
  166.         }
  167.         return r;
  168.     }  
  169.  
  170.     /** function toString() **/
  171.     public String toString()
  172.     {
  173.         return "[ "+ inorder(root, "") +"]";        
  174.     }
  175.     private String inorder(TreeSetNode r, String str)
  176.     {
  177.         if (r != null)
  178.             return str + inorder(r.left, str) + r.data +" "+ inorder(r.right, str);
  179.         else
  180.             return "";
  181.     }    
  182. }
  183.  
  184. /** Class TreeSetTest **/
  185. public class TreeSetTest
  186. {
  187.     public static void main(String[] args)
  188.     {                 
  189.         Scanner scan = new Scanner(System.in);
  190.  
  191.         /** Creating object of TreeSetTest **/
  192.         TreeSet ts = new TreeSet(); 
  193.  
  194.         System.out.println("Tree Set Test\n");          
  195.         char ch;
  196.         /**  Perform set operations  **/
  197.         do    
  198.         {
  199.             System.out.println("\nTree Set Operations\n");
  200.             System.out.println("1. add ");
  201.             System.out.println("2. delete");
  202.             System.out.println("3. contains");
  203.             System.out.println("4. count ");
  204.             System.out.println("5. check empty"); 
  205.             System.out.println("6. clear"); 
  206.  
  207.             int choice = scan.nextInt();            
  208.             switch (choice)
  209.             {
  210.             case 1 : 
  211.                 System.out.println("Enter element to insert");
  212.                 ts.add( scan.next() );                     
  213.                 break;                          
  214.             case 2 : 
  215.                 System.out.println("Enter element to delete");
  216.                 ts.delete( scan.next() );                     
  217.                 break;                         
  218.             case 3 : 
  219.                 System.out.println("Enter integer element to search");
  220.                 System.out.println("Search result : "+ ts.contains( scan.next() ));
  221.                 System.out.println();
  222.                 break;                                          
  223.             case 4 : 
  224.                 System.out.println("Count = "+ ts.countNodes());
  225.                 break;     
  226.             case 5 :  
  227.                 System.out.println("Empty status = "+ ts.isEmpty());
  228.                 break;   
  229.             case 6 :  
  230.                 System.out.println("Tree set cleared");
  231.                 ts.clear();
  232.                 break;         
  233.             default : 
  234.                 System.out.println("Wrong Entry \n ");
  235.                 break;   
  236.             }
  237.             /**  Display tree set  **/ 
  238.             System.out.print("\nTree Set : "+ ts);
  239.             System.out.println();
  240.  
  241.             System.out.println("\nDo you want to continue (Type y or n) \n");
  242.             ch = scan.next().charAt(0);                        
  243.         } while (ch == 'Y'|| ch == 'y');               
  244.     }
  245. }

advertisement
Tree Set Test
 
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
5
Empty status = true
 
Tree Set : [ ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
1
Enter element to insert
mango
 
Tree Set : [ mango ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
1
Enter element to insert
strawberry
 
Tree Set : [ mango strawberry ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
1
Enter element to insert
apple
 
Tree Set : [ apple mango strawberry ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
1
Enter element to insert
pineapple
 
Tree Set : [ apple mango pineapple strawberry ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
1
Enter element to insert
orange
 
Tree Set : [ apple mango orange pineapple strawberry ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
1
Enter element to insert
jackfruit
 
Tree Set : [ apple jackfruit mango orange pineapple strawberry ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
4
Count = 6
 
Tree Set : [ apple jackfruit mango orange pineapple strawberry ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
2
Enter element to delete
jackfruit
jackfruit deleted from the tree set
 
Tree Set : [ apple mango orange pineapple strawberry ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
2
Enter element to delete
strawberry
strawberry deleted from the tree set
 
Tree Set : [ apple mango orange pineapple ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
3
Enter integer element to search
strawberry
Search result : false
 
 
Tree Set : [ apple mango orange pineapple ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
4
Count = 4
 
Tree Set : [ apple mango orange pineapple ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
5
Empty status = false
 
Tree Set : [ apple mango orange pineapple ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
6
Tree set cleared
 
Tree Set : [ ]
 
Do you want to continue (Type y or n)
 
y
 
Tree Set Operations
 
1. add
2. delete
3. contains
4. count
5. check empty
6. clear
5
Empty status = true
 
Tree Set : [ ]
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.