CP164 Lab 8 : Binary Search Trees

Week of

Linked BST

The file BST_linked.py contains the linked implementation of the BST ADT. The Lab Instructor will walk you through the library and discuss its inner workings. Add the contents of this file to your data structures project in Eclipse.

Although you can implement a BST with an array-based structure, we will work only with the linked version of the BST.

Morse code is a method of encoding letters as a binary code where combinations of dots and dashes represent the two binary values. Morse code was developed by Samuel Morse in the mid-nineteenth century as an easy way to communicate over telegraph lines. Dots and dashes were created by short or long clicks respectively that were passed by electrical impulses over telegraph lines. The Morse Codes for letters are:

('A', '.-')
('B', '-...')
('C', '-.-.')
('D', '-..')
('E', '.')
('F', '..-.')
('G', '--.')
('H', '....')
('I', '..')
('J', '.---')
('K', '-.-')
('L', '.-..')
('M', '--')
('N', '-.')
('O', '---')
('P', '.--.')
('Q', '--.-')
('R', '.-.')
('S', '...')
('T', '-')
('U', '..--')
('V', '...-')
('W', '.--')
('X', '-..-')
('Y', '-.--')
('Z', '--..')

The tasks for this lab work with the data and classes defined in the file morse.py. This file contains three different insertion orders for letter and Morse code combinations, as well as classes, some of which you must complete. Import this file into your programs.

  1. In morse.py finish the class ByLetter . This class must define the appropriate comparisons for the letter attribute of the class.

    Test morse.py:


  2. In morse.py finish the class ByCode . The class must define the appropriate comparisons for the code attributes of the class. (The Morse codes are simply compared alphabetically.)

    Test morse.py:


  3. In morse.py finish the function fill_letter_bst that fills a BST with ByLetter objects.

    Test morse.py:


  4. In morse.py finish the function fill_code_bst that fills a BST with ByCode objects.

    Test morse.py:


  5. In morse.py finish the function encode_morse that takes a BST (created by fill_letter_bst ) and a string as parameters then converts that string into Morse code and returns the result. Ignore non-letters. In the Morse code version of the string put a space between each letter and start each word on a new line as in this example:

    English:
    My name is David Brown.
    Morse Code:
    -- -.--
    -. .- -- .
    .. ...
    -.. .- ...- .. -..
    -... .-. --- .-- -.
    

    Test morse.py:


  6. In morse.py finish the function decode_morse that takes a BST (created by fill_code_bst ) and a Morse Code string as parameters then converts that string into letters and returns the result. Example:

    Morse Code:
    ... --- ...
    English:
    SOS
    

    Test morse.py:

    Why is it necessary to have separate trees for encoding and decoding even when the same combination of letters and codes is being stored?


  7. What are the heights of the tree-by-letter possible trees?

    Draw the tree-by-letter trees represented by the data tuples in the morse.py file. (You may draw them on paper or use the style shown below.) Which of these three is the most inefficient tree? Why? Which of these is likely to be the most efficient tree? How could you (theoretically) figure that out?

    Sample Tree

         5
       /   \
      3     12
     / \   /  \
    1   4 9    35
                \
                 41