The Morse Code was designed to quickly transfer messages using a series of “dots (.)” and “dashes (-)”. Morse code was named after Samuel Morse, one of the inventors of the telegraph.
The International Morse Code includes the 26 letters of the alphabet (there is no distinction between lowercase and uppercase characters), the 10 Arabic numerals (digits from 0 to 9) and a few punctuation and arithmetic signs such as +, -, = etc.
Each character consists of a series of 1 to 5 dots or dashes (also called “dits” and “dahs”). The code was designed taking into consideration the frequency of each character in the English language so that most frequent characters such as E and T consist of just 1 dot or dash (E = “.”, T = “–”) whereas less frequent characters may include 4 to 5 dots or dashes (e.g. Q = “– – . –” and J = “. – – –”)
To find out the morse code for each character of the International Morse Code, we can use the following binary tree. Starting at the root of the tree, the succession of branches connecting the root node to the required character gives us the morse code for this character considering that:
- a left branch corresponds to a dot (.)
- a right branch corresponds to a dash (–)
For instance, the morse code for letter P is . – – . as explained on this diagram:
Morse Code encoder using a Binary Tree
The following code is using a binary tree data structure to store the more code binary tree.
It then uses the tree to convert a message into morse code by locating each character in the message within the tree and working out the morse code equivalent for each character.
In the code below, our binary tree only includes the first four levels, needed to code all 26 letters of the alphabet.
Your task consists of completing the above program to take a user input in morse code, and use the binary tree to decode the message one character at a time.