The following properties hold for every codetree.
For example, consider the following codetree, C.
The code for each letter is a string formed by appending a "0" when taking a left branch and a "1" for a right branch when traversing the root-to-leaf path. In the codetree above, the code for "u" is "010" (left, right, left), the code for "s" is "00", and the code for "n" is "10". A word is encoded by appending the codes for letters in the word together. For example, the code for "sun" is "0001010", which is formed by appending the codes for "s", "u", and "n".
Consider the following declarations for a class that represents a codetree.
public class CodeTree
{
/**
* construct a codetree
*/
public CodeTree()
{
// not shown
}
/**
* Returns a decoded word for code.
* @precondition code valid string of 0's and 1's
* @return the decoded word for code
*/
public String bitsToWord(String code)
{
// not shown
}
/**
* Returns the code for word
* @precondition each character of word is in a leaf of codetree
* @return the code for word
*/
public String wordToBits(String word)
{
// not shown
}
/**
* Returns the code for s in codetree, returns "" if s not in tree
* @precondition pathSoFar is path of 0's and 1's from myRoot to t
* @return the path from myRoot to leaf containing s ,"" if no path
*/
private String wordToBitsHelper(String s, TreeNode t, String pathSoFar)
{
// not shown
}
private TreeNode myRoot; // root of codetree, nodes store Strings
}
Each character (substring of length one) of code represents a branch in the codetree where "0" represents a left branch and "1" represents a right branch. To decode the word represented by code, begin at the root and follow a branch for each "0" or "1" character in code. When a leaf is reached, one letter in the decoded word has been found. The decoding process begins again at the root of the codetree with the next "0" or "1" in code.
For example, using the CodeTree C as shown, if code is "1110", the call C.bitsToWord(code) returns the word "in". This result is obtained as follows. The path starts at the root and goes right for the first "1" character in code, right again for the second "1", and a leaf is reached, meaning the decoded word begins with "i" (note that each leaf TreeNode stores a String). Starting back at the root of the codetree and with the next "1" in code, the path goes right for the "1" and left for the "0", reaching the leaf containg "n". The decoded word is now "in", and since all the characters in code have been processed, "in" is returned. Simillarly, C.bitsToWord("000101010011") returns the word "sunny".
Complete method bitsToWord below. Assume that instance field myRoot has been initialized to the root of a codetree when bitsToWord is called.
/**
* Returns a decoded word for code.
* @precondition code valid string of 0's and 1's
* @return the decoded word for code
*/
public String bitsToWord(String code)
{
}
/**
* Returns the code for word
* @precondition each character of word is in a leaf of codetree
* @return the code for word
*/
public String wordToBits(String word)
{
String result = "";
for(int k=0; k < word.length(); k++) {
result += wordToBitsHelper(word.substring(k,k+1),myRoot,"");
}
return result;
}
You will wrote the CodeTree private method wordToBitsHelper.
Method wordToBitsHelper has a third parameter, pathSoFar, that can be used to keep track of the current path from myRoot to parameter t, should you choose to do so. For this reason, the value of pathSoFar in the call from wordToBits is the empty string "".
Using CodeTree C as shown, wordToBitsHelper("y",myRoot,"") would return the string "011" and wordToBitsHelper("n",myRoot,"") would return "10". Note that wordToBitsHelper("x",myRoot,"") would return "" since "x" is not in the codetree.
Complete method wordToBitsHelper below.
/**
* Returns the code for s in codetree, returns "" if s not in tree
* @precondition pathSoFar is path of 0's and 1's from myRoot to t
* @return the path from myRoot to leaf containing s ,"" if no path
*/
private String wordToBitsHelper(String s, TreeNode t, String pathSoFar)
{
}