Hamming decoding example

/*
    Java Program 
    Hamming decoding example
*/
import java.util.HashMap;
import java.util.Map;
class TreeNode
{
	public int first;
	public char second;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int first, char second)
	{
		this.first = first;
		this.second = second;
		this.left = null;
		this.right = null;
	}
}
class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode prev;
	public QNode(TreeNode n)
	{
		this.n = n;
		this.prev = null;
		this.next = null;
	}
}
class PriorityQueue
{
	public QNode front;
	public QNode rear;
	public int size;
	public PriorityQueue()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a node into queue Priority queue
	public void enQueue(TreeNode auxiliary)
	{
		//Create a dynamic node
		QNode node = new QNode(auxiliary);
		node.n = auxiliary;
		if (this.front == null)
		{
			// When adding a first node of queue
			this.front = node;
			this.rear = node;
		}
		else if (this.front.n.first >= auxiliary.first)
		{
			// Add node at beginning position
			node.next = this.front;
			this.front.prev = node;
			this.front = node;
		}
		else if (this.rear.n.first <= auxiliary.first)
		{
			// Add node at last position
			node.prev = this.rear;
			this.rear.next = node;
			this.rear = node;
		}
		else
		{
			QNode temp = this.front;
			// Find the location of inserting priority node
			while (temp.n.first < auxiliary.first)
			{
				temp = temp.next;
			}
			// Add node
			node.next = temp;
			node.prev = temp.prev;
			temp.prev = node;
			if (node.prev != null)
			{
				node.prev.next = node;
			}
		}
		this.size = this.size + 1;
	}
	public boolean isEmpty()
	{
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	public TreeNode peek()
	{
		if (this.isEmpty() == true)
		{
			System.out.print("\n Empty Queue \n");
			// When Queue is empty
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
	public int isSize()
	{
		return this.size;
	}
	// Remove a front node of a queue
	public void deQueue()
	{
		if (this.isEmpty() == false)
		{
			QNode temp = this.front;
			if (this.front == this.rear)
			{
				// When queue contains only one node
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
				this.front.prev = null;
			}
			// Change queue size
			this.size--;
		}
	}
	// Print elements of queue
	public void printQdata()
	{
		QNode node = this.front;
		System.out.print("\n Queue Element ");
		while (node != null)
		{
			System.out.print("\n " + node.n.first + " " + node.n.second);
			node = node.next;
		}
		System.out.print("\n");
	}
}
public class HuffmanCodes
{
	// Display Huffman code
	public void printTree(TreeNode node, String result)
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			System.out.print("\n " + node.second + " " + node.first + " : " + result);
			return;
		}
		printTree(node.left, result + "0");
		printTree(node.right, result + "1");
	}
	// Construct Huffman Code Tree
	public TreeNode buildHuffmanCodes(String data, int n)
	{
		PriorityQueue q = new PriorityQueue();
		TreeNode root = null;
		TreeNode n1 = null;
		TreeNode n2 = null;
		int i = 0;
		// Use to get A to Z character
		int[] frequency = new int[26];
		for (i = 0; i < 26; ++i)
		{
			frequency[i] = 0;
		}
		for (i = 0; i < n; ++i)
		{
			frequency[data.charAt(i) - 'A']++;
		}
		// First add all elements into priority queue
		for (i = 0; i < 26; ++i)
		{
			if (frequency[i] > 0)
			{
				root = new TreeNode(frequency[i], (char)(i + 65));
				q.enQueue(root);
			}
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1)
		{
			// Get first smallest node  
			n1 = q.peek();
			//Remove a front element
			q.deQueue();
			// Get second smallest node
			n2 = q.peek();
			// Remove a front element
			q.deQueue();
			// Make new node using two smallest node
			root = new TreeNode(n1.first + n2.first, ' ');
			// Add new node into priority queue 
			q.enQueue(root);
			// Set left and right child
			root.left = n1;
			root.right = n2;
		}
		q.deQueue();
		return root;
	}
	// Put the leaf node information  to given map
	public void getCode(TreeNode node, Map < Character, String > m, String result)
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			// Add Initialize leaf node value and generated code result
			m.put(node.second, result);
			return;
		}
		// Recursively, visiting left and right subtree to select
		getCode(node.left, m, result + "0");
		getCode(node.right, m, result + "1");
	}
	// Get encoding text by using generated tree
	public String enCodingText(TreeNode root, String data, int n)
	{
		Map < Character, String > map = new HashMap < > ();
		// Find the path from root to leaf nodes
		getCode(root, map, "");
		String encode = "";
		for (int i = 0; i < n; i++)
		{
			encode += map.get(data.charAt(i));
		}
		return encode;
	}
	// Returns the decode of given encode and tree
	public String deCodingText(TreeNode root, String encode)
	{
		int n = encode.length();
		String decode = "";
		TreeNode auxiliary = root;
		// Execute loop through by encode length
		for (int i = 0; i < n; i++)
		{
			if (encode.charAt(i) == '0')
			{
				// Visit to left child
				auxiliary = auxiliary.left;
			}
			else
			{
				// Visit to right child
				auxiliary = auxiliary.right;
			}
			if (auxiliary.left == null && auxiliary.right == null)
			{
				// When get leaf node
				decode += auxiliary.second;
				// Start with root of tree
				auxiliary = root;
			}
		}
		// Return decoded text
		return decode;
	}
	public static void main(String[] args)
	{
		HuffmanCodes task = new HuffmanCodes();
		// Given input data
		String data = "ABEECAAAABBBEAEEEE";
		int n = data.length();
		// Construct  Tree
		TreeNode root = task.buildHuffmanCodes(data, n);
		// Get encode
		String encode = task.enCodingText(root, data, n);
		// Get decode using encode
		String decode = task.deCodingText(root, encode);
		// Display result
		System.out.print("\n Data : " + data);
		//  Print all leaf node information
		task.printTree(root, "");
		// Display encode text
		System.out.print("\n Encode : " + encode);
		// Display decode text
		System.out.print("\n Decode : " + decode);
	}
}

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE