public class TreeNode<T> { private T element; // data field private TreeNode<T>
ID: 3828158 • Letter: P
Question
public class TreeNode<T> {
private T element; // data field
private TreeNode<T> left; // reference to left child node
private TreeNode<T> right; // reference to right child node
public TreeNode() // POST: empty tree node
{ element = null;
left = right = null;
}
public TreeNode (T elem) // POST: tree node with element set
{ element = elem;
left = right = null;
}
public TreeNode (T elem, TreeNode<T> left, TreeNode<T> right) // POST: tree node with element and child nodes
{ element = elem;
this.left = left;
this.right = right;
}
// accessors and mutators
public T getElement() { return element; }
public void setElement(T element) { this.element = element; }
public TreeNode<T> getLeft() { return left; }
public void setLeft(TreeNode<T> left) { this.left = left; }
public TreeNode<T> getRight() { return right; }
public void setRight(TreeNode<T> right) { this.right = right; }
public boolean isLeaf () // POST: return true if node is a leaf node
{ return (left == null && right == null); }
}
morsecode.txt:
e o
t -
i o o
a o -
n - o
m - -
s o o o
u o o -
r o - o
w o - -
d - o o
k - o -
g - - o
o - - -
h o o o o
v o o o -
f o o - o
l o - o o
p o - - o
j o - - -
b - o o o
x - o o -
c - o - o
y - o - -
z - - o o
q - - o -
Explanation / Answer
Here is the code with comments for the question (using the TreeNode from the question). Run the driver file for different input english messages to get the output shown in question. Sample output is attached. Please don't forget to rate the answer if it helped. Thank you very much.
MorseCodeTree.java
public class MorseCodeTree {
protected TreeNode<Character> root;
protected static final char DOT ='o';
protected static final char DASH ='-';
public MorseCodeTree()
{
root = new TreeNode<Character>(' ');
}
//insert a character into the tree by using its code to travel the tree
public void addNode(char ch, String morseCode)
{
char code[]=morseCode.replaceAll(" ","").toCharArray();
TreeNode<Character> current=root;
for(int i=0; i<code.length; i++)
{
if(code[i] == DOT)
{
if(current.getLeft() == null)
{
current.setLeft(new TreeNode<Character>(ch));
return;
}
else
current = current.getLeft();
}
else if(code[i] == DASH)
{
if(current.getRight() == null)
{
current.setRight(new TreeNode<Character>(ch));
return;
}
else
current = current.getRight();
}
}
}
//decodes the code message containing | delimiter between code into english message
// example when the input is - | o o o o | o | - - o - | o o - | o o | - o - o | - o - | o o - o | - - - | - o o - |
// the return value is t h e q u i c k f o x
public String decode(String codeMessage)
{
//get individual codes by splitting it on | , since | is a regex character, it should be escapped using \
String codes[]= codeMessage.split("\|");
String ret="";
for(int i=0; i < codes.length; i++)
{
ret+= travel(codes[i])+" ";
}
return ret;
}
//traverse the tree for the given code and returns the character that was reached at the end of traversal
public Character travel(String code)
{
//remove all extra spaces in the input
char elem[]=code.replaceAll(" ","").toCharArray();
TreeNode<Character> current = root;
for(int i=0;i<elem.length; i++)
{
if(elem[i] == DOT)
current = current.getLeft();
else if (elem[i] == DASH)
current = current.getRight();
}
return current.getElement();
}
//prints preorder traversal of tree
public void printPreorder()
{
System.out.print(" Preorder tree contents: ");
preorder(root);
}
private void preorder(TreeNode<Character> node)
{
if(node == null)
return ;
System.out.print(node.getElement()+" ");
preorder(node.getLeft());
preorder(node.getRight());
}
}
TreeDriver.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.InputMismatchException;
import java.util.Scanner;
public class TreeDriver {
String MORSE_CODES[];
public TreeDriver()
{
MORSE_CODES = new String [26]; //codes for the alphabet a-z
}
public void loadCodeFile(MorseCodeTree tree,String filename) throws FileNotFoundException, InputMismatchException
{
Scanner scanner = new Scanner(new File(filename));
String elem, code;
char ch;
while(scanner.hasNext())
{
elem = scanner.next();
if(elem.length() != 1 || !((ch=elem.charAt(0)) >='a' && ch<='z'))
throw new InputMismatchException("Unexpected input "+elem);
code=scanner.nextLine();
tree.addNode(ch, code);
MORSE_CODES[ch-'a'] = code;
}
scanner.close();
}
public String convertToMorseCode(String input)
{
char letters[] = input.replaceAll(" ", "").toCharArray();
String code="";
for(int i=0;i<letters.length;i++)
{
code+=MORSE_CODES[letters[i]-'a']+" |";
}
return code;
}
public static void main(String[] args) {
TreeDriver driver=new TreeDriver();
MorseCodeTree tree=new MorseCodeTree();
try {
driver.loadCodeFile(tree,"codes.txt");
Scanner keyboard=new Scanner(System.in);
tree.printPreorder();
System.out.print(" Enter English message: ");
String engmsg=keyboard.nextLine();
String codeMessage = driver.convertToMorseCode(engmsg);
System.out.println("m = "+codeMessage);
System.out.println("Message : "+tree.decode(codeMessage));
keyboard.close();
} catch (InputMismatchException e) {
System.out.println(e.getMessage());
} catch (FileNotFoundException e) {
System.out.println(e.getMessage());
}
}
}
Input file codes.txt
e o
t -
i o o
a o -
n - o
m - -
s o o o
u o o -
r o - o
w o - -
d - o o
k - o -
g - - o
o - - -
h o o o o
v o o o -
f o o - o
l o - o o
p o - - o
j o - - -
b - o o o
x - o o -
c - o - o
y - o - -
z - - o o
q - - o -
output
Preorder tree contents: e i s h v u f a r l w p j t n d b x k c y m g z q o
Enter English message: the quick fox
m = - | o o o o | o | - - o - | o o - | o o | - o - o | - o - | o o - o | - - - | - o o - |
Message : t h e q u i c k f o x
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.