Application #1

The Morse code is a common code that is used to encode messages. In our application, we will assume that the messages contain letters only. Each letter consists of a series of dots (.) and underscores (_); for example, the code for the letter a is ._ and the code for the letter b is _....

See the table below:

Our program stores each letter of the alphabet in a binary tree. The root of the tree contains no letter. Its left node store the letter e (code is .), and its right node stores the letter t (code is _). The 4 nodes at the next level store the letters with codes (.., ._, -., __) .

To build the tree we created a text file where each line consists of a letter and its code. The letters in the file are ordered by the tree level. The method buildMorseCodeTree() creates the Morse Code Tree:

Study the provided MorseCode.java and run the program. It has main method that prompts the user for a message encoded in Morse code and calls the decode method to decode the message and display the result. Your task is to implement the decode method. To find the position for a letter in the tree, scan the code and branch left for the dot and branch right for an underscore. Assume that the encoded letters are separated by spaces.

Implement decode method defined in the MorseCode.java file.

public class MorseCode { private BinaryNode root; public MorseCode() { this.root = new BinaryNode(' '); } private void buildMorseCodeTree() { int index; BinaryNode current; BinaryNode letterTree; String code = null; try { Scanner file = new Scanner(new File("MorseCode.txt")); System.out.println("The Morse Code:"); System.out.println("==============="); while (file.hasNext()) // test for the end of the file { code = file.nextLine(); // read a line System.out.println(code); // print the line read // building the tree letterTree = new BinaryNode(code.charAt(0)); current = this.root; index = 2; for (; index out.println("Unable to find MorseCode.txt, exiting"); } catch (IOException ioe) { ioe.printStackTrace(); } } private void decode(String encoded) { // TODO Project 1  System.out.println("Decoding "" + encoded + """); BinaryNode current = this.root; StringBuilder answer = new StringBuilder();; // YOUR CODE GOES HERE System.out.println("The decoded string is "" + answer.toString() + """); } public void displayInPreOrder() { System.out.println(" " + displayInPreOrder(this.root)); } public String displayInPreOrder(BinaryNode current) { return (current.getLeftChild() != null ? current.getLeftChild().getData() + " " + displayInPreOrder(current.getLeftChild()) : "") +(current.getRightChild() != null ? current.getRightChild().getData() + " " + displayInPreOrder(current.getRightChild()) : ""); } public LevelOrderIterator getLevelOrderIterator() { return new LevelOrderIterator(); } // end getLevelOrderIterator private class LevelOrderIterator implements Iterator { //private QueueInterface nodeQueue; private LinkedBlockingQueue> nodeQueue; public LevelOrderIterator() { this.nodeQueue = new LinkedBlockingQueue(); if (root != null) { this.nodeQueue.offer(root); } } // end default constructor public boolean hasNext() { return !this.nodeQueue.isEmpty(); } // end hasNext public BinaryNode next() { BinaryNode nextNode; if (hasNext()) { nextNode = this.nodeQueue.poll(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // add to queue in order of recursive calls if (leftChild != null) this.nodeQueue.offer(leftChild); if (rightChild != null) this.nodeQueue.offer(rightChild); } else { throw new NoSuchElementException(); } return nextNode; } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end LevelOrderIterator public static void main(String[] args) { MorseCode morseCode = new MorseCode(); morseCode.buildMorseCodeTree(); LevelOrderIterator iter = morseCode.getLevelOrderIterator(); System.out.println(" The Morse Code Tree in level order:"); while (iter.hasNext()) { System.out.print(iter.next().getData() + " "); } System.out.println(" "); System.out.println(" The Morse Code Tree in pre-order:"); morseCode.displayInPreOrder(); System.out.println(" "); String input = ""; boolean done = false; Scanner keyboard = new Scanner(System.in); do { do { System.out.println("Please enter a message in Morse Code, use space as a separator. Press enter to stop."); input = keyboard.nextLine(); if (input.equals("")) done = true; } while (!input.matches("[._ ]+") && !done); if (!done) morseCode.decode(input); } while (!done); System.out.println("Done decoding."); } }

Sample Run.

The Morse Code:

===============

e .

t _

i ..

a ._

n _.

m __

s ...

u .._

r ._.

w .__

d _..

k _._

g __.

o ___

h ....

v ..._

f .._.

l ._..

p .__.

j .___

b _...

x _.._

c _._.

y _.__

z __..

q __._

The Morse Code Tree in level order:

e t i a n m s u r w d k g o h v f l p j b x c y z q

The Morse Code Tree in pre-order:

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

Please enter a message in Morse Code, use space as a separator. Press enter to stop.

... ___ ...

Decoding "... ___ ..."

The decoded string is "sos"

Please enter a message in Morse Code, use space as a separator. Press enter to stop.

_._. ... .._ _._. ..

Decoding "_._. ... .._ _._. .."

The decoded string is "csuci"

Please enter a message in Morse Code, use space as a separator. Press enter to stop.

._.

Decoding "._."

The decoded string is "r"

Please enter a message in Morse Code, use space as a separator. Press enter to stop.

._._

Decoding "._._"

Not a morse pattern.

Please enter a message in Morse Code, use space as a separator. Press enter to stop.

Done decoding.

Process finished with exit code 0

Morse Code for Letters n ) k )