@@ -0,0 +1,2233 @@
+package data_structures.trees;%0D%0A%0D%0A/*%0D%0A * Huffman coding assigns variable length codewords to fixed length input%0D%0A * characters based on their frequencies. More frequent characters are assigned%0D%0A * shorter codewords and less frequent characters are assigned longer codewords.%0D%0A * A huffman tree is made for the input string and characters are decoded based%0D%0A * on their position in the tree. We add a '0' to the codeword when we move left%0D%0A * in the binary tree and a '1' when we move right in the binary tree. We assign%0D%0A * codes to the leaf nodes which represent the input characters.%0D%0A * %0D%0A * For example:%0D%0A *      %7B@,5%7D%0D%0A *     0/   %5C 1%0D%0A *   %7B@,2%7D %7BA,3%7D%0D%0A *  0/   %5C1%0D%0A * %7BB,1%7D %7BC,1%7D%0D%0A * Input characters are only present on the leaves. Internal nodes have a%0D%0A * character value of @. Codewords:%0D%0A * %0D%0A * A - 1%0D%0A * B - 00%0D%0A * C - 01%0D%0A * No codeword appears as a prefix of any other codeword. Huffman encoding is a%0D%0A * prefix free encoding technique.%0D%0A * %0D%0A * Encoded String %221001011%22 represents the string %22ABACA%22%0D%0A * %0D%0A * You have to decode an encoded string using the huffman tree.%0D%0A * %0D%0A * You are given pointer to the root of the huffman tree and a binary coded%0D%0A * string. You need to print the actual string.%0D%0A * %0D%0A * Input Format: %0D%0A * You are given a function,%0D%0A * %0D%0A * void decode_huff(node * root, string s) %7B%0D%0A * %0D%0A * %7D%0D%0A * %0D%0A * The structure for node is defined as:%0D%0A * struct node %7B%0D%0A *     int freq;%0D%0A *     char data;%0D%0A *     node * left;%0D%0A *     node * right;%0D%0A * %7D node;%0D%0A * %0D%0A * Note:%0D%0A * Internal nodes have data='%5C0'(@ )%0D%0A * %0D%0A * Output Format: %0D%0A * Output the decoded string on a single line.%0D%0A * %0D%0A * Sample Input:%0D%0A *      %7B@,5%7D%0D%0A *     0/   %5C 1%0D%0A *   %7B@,2%7D %7BA,3%7D%0D%0A *  0/   %5C1%0D%0A * %7BB,1%7D %7BC,1%7D%0D%0A * %0D%0A * S=%221001011%22%0D%0A * %0D%0A * Sample Output: %0D%0A * ABACA%0D%0A */%0D%0Apublic class HuffmanDecoding %7B%0D%0A%0D%0A%09void decode(String S, Node root) %7B%0D%0A%09    %0D%0A%09    StringBuilder sb = new StringBuilder();%0D%0A%09    Node treeNode = root;%0D%0A%09    %0D%0A%09    for (int i = 0; i %3C S.length(); i++) %7B%0D%0A%09        treeNode = S.charAt(i) == '1' ? treeNode.right : treeNode.left;%0D%0A%09        if (treeNode.data != '%5C0') %7B%0D%0A%09            sb.append(treeNode.data);%0D%0A%09            treeNode = root;%0D%0A%09        %7D%0D%0A%09    %7D%0D%0A%09    System.out.print(sb.toString());%0D%0A%09%7D%0D%0A%7D

Add HuffmanDecoding