Is it possible for you to write the whole code for this and not just the structure outline? The actual specifications are listed here.

Transcribed Image Text:

DESCRIPTION: In this assignment you are required to implement prefix-free codes using binary trees with linked nodes. For this, you have to write the Java classes BinTree and TNode in the same package. Class BinTree uses binary trees with linked nodes to represent prefix-free codes. Class TNode represents the nodes of the binary tree. You also need to perform the time and space complexity analysis of your algorithms. You are not allowed to use any predefined Java methods other than those de- fined in the classes java.util.ArrayList, java.lang.String and java.lang. Math. DEFINITIONS: A prefix-free code (used in data compression) is a set of binary sequences (sequences of 0's and 1's) such that none of them is a prefix of another. For instance, the set A = {0, 10, 110, 111} is a prefix-free code. On the other hand, the set {0, 10, 100, 111} is not a prefix-free code because the sequence 10 is a prefix of 100. The elements of the prefix-free code are referred to as (binary) codewords. A prefix-free code can be used to encode a sequence of symbols from an alphabet B (i.c., convert the sequence of symbols into a bitstream) as follows. Each symbol in alphabet B = {0, c1, c2,,cn} is assigned a distinct binary codeword. Then we can encode any sequence of symbols by replacing every symbol by the corresponding binary codeword. For instance, assume that alphabet B contains 4 symbols. Then they are c0, c1, c2, c3. Further, assume that symbol c0 is assigned 0, c1 is assigned 10, 2 is assigned 110 and c3 is assigned 111. Consider now the following sequence of symbols over the alphabet B: "c2 c3 cl c2 c0 c0 c0". This sequence is encoded into the bitstream "11011110110000". Conversely, a bit sequence is decoded by dividing it first into non-overlapping code- words and then replacing each codeword with the corresponding alphabet symbol. For instance, the sequence "0011001010111" can be parsed as follows: "0,0,110,0,10,10,111". Then the decoded alphabet sequence is "c0 c0 c2 c0 cl cl c3". Note that the prefix-free property ensures that the parsing of the binary sequence into codewords is unique. A prefix-free code can be represented using a binary tree. Note first that any path in the tree, from some node to one of its descendants, can be regarded as a sequence of branches. By replacing any left branch with 0 and any right branch with 1 we obtain a binary sequence that represents the path. In a binary tree representation of a prefix-free code, the paths from the root to the leaves represent the codewords. Thus, the number of leaves equals the number of codewords. Each leaf stores the alphabet symbol corresponding to the binary codeword that describes the path from the root to that leaf. DESCRIPTION: In this assignment you are required to implement prefix-free codes using binary trees with linked nodes. For this, you have to write the Java classes BinTree and TNode in the same package. Class BinTree uses binary trees with linked nodes to represent prefix-free codes. Class TNode represents the nodes of the binary tree. You also need to perform the time and space complexity analysis of your algorithms. You are not allowed to use any predefined Java methods other than those de- fined in the classes java.util.ArrayList, java.lang.String and java.lang. Math. DEFINITIONS: A prefix-free code (used in data compression) is a set of binary sequences (sequences of 0's and 1's) such that none of them is a prefix of another. For instance, the set A = {0, 10, 110, 111} is a prefix-free code. On the other hand, the set {0, 10, 100, 111} is not a prefix-free code because the sequence 10 is a prefix of 100. The elements of the prefix-free code are referred to as (binary) codewords. A prefix-free code can be used to encode a sequence of symbols from an alphabet B (i.c., convert the sequence of symbols into a bitstream) as follows. Each symbol in alphabet B = {0, c1, c2,,cn} is assigned a distinct binary codeword. Then we can encode any sequence of symbols by replacing every symbol by the corresponding binary codeword. For instance, assume that alphabet B contains 4 symbols. Then they are c0, c1, c2, c3. Further, assume that symbol c0 is assigned 0, c1 is assigned 10, 2 is assigned 110 and c3 is assigned 111. Consider now the following sequence of symbols over the alphabet B: "c2 c3 cl c2 c0 c0 c0". This sequence is encoded into the bitstream "11011110110000". Conversely, a bit sequence is decoded by dividing it first into non-overlapping code- words and then replacing each codeword with the corresponding alphabet symbol. For instance, the sequence "0011001010111" can be parsed as follows: "0,0,110,0,10,10,111". Then the decoded alphabet sequence is "c0 c0 c2 c0 cl cl c3". Note that the prefix-free property ensures that the parsing of the binary sequence into codewords is unique. A prefix-free code can be represented using a binary tree. Note first that any path in the tree, from some node to one of its descendants, can be regarded as a sequence of branches. By replacing any left branch with 0 and any right branch with 1 we obtain a binary sequence that represents the path. In a binary tree representation of a prefix-free code, the paths from the root to the leaves represent the codewords. Thus, the number of leaves equals the number of codewords. Each leaf stores the alphabet symbol corresponding to the binary codeword that describes the path from the root to that leaf.