Java Program to Implement Binomial Tree

«
»
This is a Java Program to implement Binomial Tree.

Here is the source code of the Java program to implement Binomial Tree. 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 Binomial Tree
  3.  **/    
  4.  
  5. import java.util.*;        
  6.  
  7. /** Class BinoNode **/
  8. class BinoNode    
  9. {
  10.     int data;
  11.     int numNodes;
  12.     BinoNode arr[];
  13.     /** Constructor **/
  14.     public BinoNode(int k)
  15.     {
  16.         data = -1;
  17.         numNodes = k;
  18.         arr = new BinoNode[numNodes];    
  19.     }
  20. }
  21.  
  22. /** Class BinomialTree **/
  23. class BinomialTree
  24. {
  25.     private BinoNode root;
  26.     private int order, size;
  27.  
  28.     /** Constructor **/
  29.     public BinomialTree(int k)
  30.     {
  31.         size = 0;
  32.         order = k;        
  33.         root = new BinoNode(order);
  34.         createTree(root);
  35.     }
  36.     /** Function to create a tree **/
  37.     private void createTree(BinoNode r)
  38.     {
  39.         int n = r.numNodes;        
  40.         if (n == 0)
  41.             return;            
  42.         for (int i = 0; i < n; i++)
  43.         {
  44.             r.arr[i] = new BinoNode(i);
  45.             createTree(r.arr[i]);
  46.         }  
  47.     }
  48.     /** Function to clear tree **/
  49.     public void clear()
  50.     {
  51.         size = 0;
  52.         root = new BinoNode(order);
  53.         createTree(root);
  54.     }
  55.     /** Function to check if tree is empty **/
  56.     public boolean isEmpty()
  57.     {
  58.         return size == 0;
  59.     }
  60.     /** Function to get size of tree **/
  61.     public int getSize()
  62.     {
  63.         return size;
  64.     }
  65.     /** Function to insert a value **/
  66.     public void insert(int val)
  67.     {
  68.         try
  69.         {
  70.             insert(root, val);
  71.         }
  72.         catch (Exception e)
  73.         {
  74.         }
  75.     }
  76.     /** Function to insert a value **/
  77.     private void insert(BinoNode r, int val) throws Exception
  78.     {
  79.         if (r.data == -1)
  80.         {
  81.             r.data = val;
  82.             size++;
  83.             throw new Exception("inserted !");
  84.         }
  85.         int n = r.numNodes;        
  86.         for (int i = 0; i < n; i++)
  87.             insert(r.arr[i], val);
  88.     }
  89.     /** Function to print tree **/
  90.     public void printTree()
  91.     {
  92.         System.out.print("\nBinomial Tree = ");
  93.         printTree(root);
  94.         System.out.println();
  95.     }
  96.     /** Function to print tree **/
  97.     private void printTree(BinoNode r)
  98.     {
  99.         if (r.data != -1)
  100.             System.out.print(r.data +" ");        
  101.         int n = r.numNodes;
  102.         if (n == 0)
  103.             return;
  104.         for (int i = 0; i < n; i++)
  105.             printTree(r.arr[i]);
  106.     }
  107. }
  108.  
  109. public class BinomialTreeTest
  110. {
  111.     public static void main(String[] args)
  112.     {
  113.         Scanner scan = new Scanner(System.in);
  114.         System.out.println("Binomial Tree Test\n");
  115.         System.out.println("\nEnter order of binomial tree");
  116.         /** Creating object of Binomial tree **/
  117.         BinomialTree bt = new BinomialTree(scan.nextInt());           
  118.         char ch;
  119.         /**  Perform tree operations  **/
  120.         do    
  121.         {
  122.             System.out.println("\nBinomial Tree Operations\n");
  123.             System.out.println("1. insert ");
  124.             System.out.println("2. size");
  125.             System.out.println("3. check empty"); 
  126.             System.out.println("4. clear");
  127.  
  128.             int choice = scan.nextInt();            
  129.             switch (choice)
  130.             {
  131.             case 1 : 
  132.                 System.out.println("Enter integer element to insert");
  133.                 bt.insert( scan.nextInt() );                     
  134.                 break;                          
  135.             case 2 : 
  136.                 System.out.println("Nodes = "+ bt.getSize());
  137.                 break;     
  138.             case 3 :  
  139.                 System.out.println("Empty status = "+ bt.isEmpty());
  140.                 break;   
  141.             case 4 :  
  142.                 bt.clear();
  143.                 System.out.println("\nTree Cleared\n");
  144.                 break;            
  145.             default : 
  146.                 System.out.println("Wrong Entry \n ");
  147.                 break;   
  148.             }
  149.             /**  Display tree  **/ 
  150.             bt.printTree();
  151.  
  152.             System.out.println("\nDo you want to continue (Type y or n) \n");
  153.             ch = scan.next().charAt(0);                        
  154.         } while (ch == 'Y'|| ch == 'y');               
  155.     }
  156. }

advertisement
Binomial Tree Test
 
 
Enter order of binomial tree
3
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
24
 
Binomial Tree = 24
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
6
 
Binomial Tree = 24 6
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
19
 
Binomial Tree = 24 6 19
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
94
 
Binomial Tree = 24 6 19 94
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
28
 
Binomial Tree = 24 6 19 94 28
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
5
 
Binomial Tree = 24 6 19 94 28 5
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
16
 
Binomial Tree = 24 6 19 94 28 5 16
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
63
 
Binomial Tree = 24 6 19 94 28 5 16 63
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
1
Enter integer element to insert
17
 
Binomial Tree = 24 6 19 94 28 5 16 63
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
2
Nodes = 8
 
Binomial Tree = 24 6 19 94 28 5 16 63
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
3
Empty status = false
 
Binomial Tree = 24 6 19 94 28 5 16 63
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
4
 
Tree Cleared
 
 
Binomial Tree =
 
Do you want to continue (Type y or n)
 
y
 
Binomial Tree Operations
 
1. insert
2. size
3. check empty
4. clear
3
Empty status = true
 
Binomial Tree =
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

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.