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.

/**
 *  Java Program to Implement Binomial Tree
 **/    
 
import java.util.*;        
 
/** Class BinoNode **/
class BinoNode    
{
    int data;
    int numNodes;
    BinoNode arr[];
    /** Constructor **/
    public BinoNode(int k)
    {
        data = -1;
        numNodes = k;
        arr = new BinoNode[numNodes];    
    }
}
 
/** Class BinomialTree **/
class BinomialTree
{
    private BinoNode root;
    private int order, size;
 
    /** Constructor **/
    public BinomialTree(int k)
    {
        size = 0;
        order = k;        
        root = new BinoNode(order);
        createTree(root);
    }
    /** Function to create a tree **/
    private void createTree(BinoNode r)
    {
        int n = r.numNodes;        
        if (n == 0)
            return;            
        for (int i = 0; i < n; i++)
        {
            r.arr[i] = new BinoNode(i);
            createTree(r.arr[i]);
        }  
    }
    /** Function to clear tree **/
    public void clear()
    {
        size = 0;
        root = new BinoNode(order);
        createTree(root);
    }
    /** Function to check if tree is empty **/
    public boolean isEmpty()
    {
        return size == 0;
    }
    /** Function to get size of tree **/
    public int getSize()
    {
        return size;
    }
    /** Function to insert a value **/
    public void insert(int val)
    {
        try
        {
            insert(root, val);
        }
        catch (Exception e)
        {
        }
    }
    /** Function to insert a value **/
    private void insert(BinoNode r, int val) throws Exception
    {
        if (r.data == -1)
        {
            r.data = val;
            size++;
            throw new Exception("inserted !");
        }
        int n = r.numNodes;        
        for (int i = 0; i < n; i++)
            insert(r.arr[i], val);
    }
    /** Function to print tree **/
    public void printTree()
    {
        System.out.print("\nBinomial Tree = ");
        printTree(root);
        System.out.println();
    }
    /** Function to print tree **/
    private void printTree(BinoNode r)
    {
        if (r.data != -1)
            System.out.print(r.data +" ");        
        int n = r.numNodes;
        if (n == 0)
            return;
        for (int i = 0; i < n; i++)
            printTree(r.arr[i]);
    }
}
 
public class BinomialTreeTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Binomial Tree Test\n");
        System.out.println("\nEnter order of binomial tree");
        /** Creating object of Binomial tree **/
        BinomialTree bt = new BinomialTree(scan.nextInt());           
        char ch;
        /**  Perform tree operations  **/
        do    
        {
            System.out.println("\nBinomial Tree Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. size");
            System.out.println("3. check empty"); 
            System.out.println("4. clear");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                bt.insert( scan.nextInt() );                     
                break;                          
            case 2 : 
                System.out.println("Nodes = "+ bt.getSize());
                break;     
            case 3 :  
                System.out.println("Empty status = "+ bt.isEmpty());
                break;   
            case 4 :  
                bt.clear();
                System.out.println("\nTree Cleared\n");
                break;            
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            /**  Display tree  **/ 
            bt.printTree();
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');               
    }
}

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