IN JAVA!

--------------------------

Description:

Write a program to decipher messages encoded using a prefix code, given the encoding tree. Such codes are widely used in applications that compress data, including JPEG for images, MP3 for music, and DivX for video.

Prefix codes. A prefix code is most easily represented by a binary tree in which the external nodes are labeled with single characters that are combined to form the message. The encoding for a character is determined by following the path down from the root of the tree to the external node that holds that character: a 0 bit identifies a left branch in the path, and a 1 bit identifies a right branch. In the following tree, black circles are internal nodes and gray squares are external nodes. The code for b is 111, because the external node holding b is reached from the root by taking 3 consecutive right branches. The other codes are given in the table below.

	character encoding ------------------- a 0 b 111 c 1011 d 1010 r 110 ! 100

Note that each character can be encoded with a different number of bits. In the example above, the character 'a' is encoded with a single bit, while the character 'd' is encoded with 4 bits. This is a fundamental property of prefix codes. In order for this encoding scheme to reduce the number of bits in a message, we use short encodings for frequently used characters, and long encodings for infrequent ones. A second fundamental property of prefix codes is that messages can be formed by simply stringing together the code bits from left to right. For example, the bitstring

0111110010110101001111100100

encodes the message "abracadabra!". The first 0 must encode 'a', then the next three 1's must encode 'b', then 110 must encode r, and so on as follows:

|0|111|110|0|1011|0|1010|0|111|110|0|100 a b r a c a d a b r a !

The codes can be run together because no encoding is a prefix of another one. This property defines a prefix code, and it allows us to represent the character encodings with a binary tree, as shown above. To decode a given bit string:

Start at the root of the tree.

Repeat until you reach an external leaf node.

Read one message bit.

Take the left branch in the tree if the bit is 0; take the right branch if it is 1.

Print the character in that external node.

This whole process is repeated, starting over at the root, until all of the bits in the compressed message are exhausted. Your main task is to parse the binary tree and implement this procedure.

Representing the binary tree. To decode a bit string, you need the binary tree that stores the character encodings. We use the preorder traversal of the binary tree to represent the tree itself. Internal nodes are labeled with the special character '*'. (For convenience, we artificially restrict ourselves to messages that do not contain this special character.) The preorder traversal of the above tree is:

* a * * ! * d c * r b 

Input format. The input will consist of the preorder traversal of the binary tree, followed immediately on a new line by the compressed message. For the example above, the input file is abra.pre:

*a**!*dc*rb 0111110010110101001111100100

In order to read the input one character at a time, use the library CharStdIn.java.

---------------------

I got so far code, but it wont give correct output - abracadabra!, so basically i need to fix my code according to task description provided. Please provide code as copy-paste not as image!!!!!

class Node { char ch; Node left, right; } class Decode { Node root; StringBuilder sb = new StringBuilder(); public Decode(String preOrder) { root = buildTree(preOrder); } public Node buildTree(String preOrder) { return buildTree(preOrder, 0, preOrder.length()); } public Node buildTree(String preOrder, int start, int end) { if (start >= end) { return null; } Node node = new Node(); char ch = preOrder.charAt(start); node.ch = ch; if (ch == '*') { int i = start + 1; while (i < end && preOrder.charAt(i) == '*') { i++; } node.left = buildTree(preOrder, i, end); node.right = buildTree(preOrder, i + 1, end); } return node; } public void decode(String message) { Node node = root; for (char ch : message.toCharArray()) { if (node == null) { break; } node = ch == '0' ? node.left : node.right; if (node != null && node.left == null && node.right == null) { sb.append(node.ch); node = root; } } } public String getDecodedMessage() { return sb.toString(); } } public class DecodeMessage { public static void main(String[] args) { String preOrder = "*a**!*dc*rb"; String message = "0111110010110101001111100100"; Decode decoder = new Decode(preOrder); decoder.decode(message); String decodedMessage = decoder.getDecodedMessage(); System.out.println("Decoded message: " + decodedMessage); } }