Java Program To Implement Binomial Tree

Chapter: Data Structures Last Updated: 12-07-2016 15:19:53 UTC

Program:

            /* ............... START ............... */
                
import java.util.*;

class BinoNode {
	int data;
	int numNodes;
	BinoNode arr[];

	public BinoNode(int k) {
		data = -1;
		numNodes = k;
		arr = new BinoNode[numNodes];
	}
}

class BinomialTree {
	private BinoNode root;
	private int order, size;

	public BinomialTree(int k) {
		size = 0;
		order = k;
		root = new BinoNode(order);
		createTree(root);
	}

	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]);
		}
	}

	public void clear() {
		size = 0;
		root = new BinoNode(order);
		createTree(root);
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public int getSize() {
		return size;
	}

	public void insert(int val) {
		try {
			insert(root, val);
		} catch (Exception e) {
		}
	}

	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);
	}

	public void printTree() {
		System.out.print("\nBinomial Tree = ");
		printTree(root);
		System.out.println();
	}

	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 JavaBinomialTree {

	public static void main(String[] args) {
		Scanner scanner = 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(scanner.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 = scanner.nextInt();
			switch (choice) {
			case 1:
				System.out.println("Enter integer element to insert");
				bt.insert(scanner.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 = scanner.next().charAt(0);
		} while (ch == 'Y' || ch == 'y');
	}
}
                /* ............... END ............... */
        

Output

Enter order of binomial tree

2

Binomial Tree Operations

1. insert 
2. size
3. check empty
4. clear
1
Enter integer element to insert
1

Binomial Tree = 1 

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
3

Binomial Tree = 1 3 

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
1

Binomial Tree = 1 3 1 

Do you want to continue (Type y or n) 

y

Binomial Tree Operations

1. insert 
2. size
3. check empty
4. clear
2
Nodes = 3

Binomial Tree = 1 3 1 

Tags

Implement Binomial Tree, Java, Data Structure

Similar Programs Chapter Last Updated
HashMap Implementation In Java Data Structures 07-07-2018
Linked List Implementation In Java Data Structures 09-03-2018
Queue Implementation In Java Data Structures 22-09-2018
Stack Implementation In Java Data Structures 22-09-2018
Binary Search Tree Java Data Structures 11-02-2018
Insertion Sort In Java Data Structures 10-02-2018
Java Stack Example Data Structures 16-10-2017
Java String Array Sort Data Structures 31-03-2017
Java Hashmap Add Key And Value Data Structures 25-03-2017
Java Binary Tree Vertical Sum Data Structures 11-11-2016
Java Binary Tree Boundary Traversal Data Structures 11-11-2016
Java Binary Tree Lowest Common Ancestor (LCA) Data Structures 11-11-2016
Java Binary Tree Maximum Element Data Structures 11-11-2016
Java Three Dimensional Array Data Structures 28-10-2016
Java Infix Expression To Postfix Expression Data Structures 25-10-2016
Java Linked List Add Element First And Last Data Structures 24-10-2016
Java Maximum Element From Vector Data Structures 24-10-2016
Java Binary Search On Vector Data Structures 24-10-2016
Java Get Elements Of LinkedList Data Structures 23-10-2016
Java Linked List Update Element Data Structures 23-10-2016
Java Delete Elements From LinkedList Data Structures 23-10-2016
Java Double Ended Queue Data Structures 09-10-2016
Java Dynamic Queue Using Array Data Structures 26-09-2018
Java Queue Array Based Implementation Data Structures 07-10-2016
Java Sort Short Array Data Structures 25-09-2016
Java Sort Long Array Data Structures 25-09-2016
Java Sort Int Array Data Structures 19-09-2016
Java Sort Float Array Data Structures 19-09-2016
Java Sort Double Array Data Structures 19-09-2016
Java Sort Char Array Data Structures 19-09-2016

1 2 3