Prefix Codes: Tree Construction, Decoding, and Analysis

Problem Statement

Prefix Codes: Tree Construction, Decoding, and Analysis Problem 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 are 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. (Note: Image of tree diagram would be here) character enc