# CS1102 02/03 Semester 2 Lab 4A

17 March 2003 to 25 March 2003

### Problem 1 (30%)

In this problem, you are to modify the code for binary search tree in your textbook (pg 471 -- 474).  The source code can be downloaded from

Your task is to augment the implementation for binary search tree in your textbook so that every node maintains the following members:

·      TreeNode parent  a reference to the parent node.  The parent field for the root node points to itself.

·      int height  the height of the node.

·      int size  the size of the subtree rooted at the node.

·      TreeNode successor  a reference to the node with the next larger value in the tree.

·      TreeNode predecessor  a reference to the node with the next smaller value in the tree.

All five fields must be correctly updated after insertion and deletion on the tree.

### Input

Input to your program is a series of insert and delete instructions.  Each line in the input contains an instruction of the form <operation> <data>.  <operation> must be either INSERT or DELETE, and <data> is an integer.  Your program should read these instructions and perform the sequence of operations as specified by the instructions, starting with an empty BST.

### Output

Your program should perform preorder traversal on the BST that you have constructed, and output each of the members that you added, in the order specified above, one line per node.  For references to TreeNode, you should output the item stored in the referenced TreeNode.

INSERT 4

INSERT 9

INSERT 2

INSERT 1

INSERT 10

INSERT 11

DELETE 10

DELETE 1

INSERT 8

4 3 5 8 2

4 2 1 4 _

4 2 3 11 8

9 1 1 9 4

9 1 1 _ 8

### Problem 2 (70%)

The goal of this problem is to implement predictive text-based input for mobile phone using a tree-based data structure called trie.

Numeric inputs 1 to 9 from the mobile phone keypad can be mapped into a set of three uppercase letters are given below.

 2 ABC 3 DEF 4 GHI 5 JKL 6 MNO 7 PQRS 8 TUV 9 WXYZ

To enter a word in a mobile phone, a user enters a sequence of digits whose letters in the word are mapped from.  For example, to enter the word LAB, the user enters 522.

You are asked to implement a program that maintains a dictionary, takes in a sequence of digits as input, and outputs words in the dictionary in alphabetical order that could be represented by that sequence of digits.  Your program must take care of the following two properties.

Non-uniqueness. Since each digit can represent up to three letters, the word represented by a sequence of digits might not be unique.  For example, 228 could represent CAT, ACT or BAT.  In this case, your program must output all three choices.

Prediction.  You can predict the word the user wants to enter if there is only one possible way the word could be completed.  For instance, 23 corresponds to AD, AE AF, BE,  CE and CF.  Besides matching the word BE, your program should also output AFTER and CERTAIN, because they are the only words in the dictionary that matches the prefix AF and CE respectively.  There are more than one words that matches the prefix AD (ADD, ADDITION, ADDICT etc) so these words starting with AD should not be in the output.

For simplicity, you only need to output complete words in the dictionary (i.e. no partial matching as in normal mobile phone).  You can assume that the input dictionary contains only words with uppercase letters (no blanks, numbers, symbols and punctuations).

To implement this program efficiently, you will need to use a tree-based data structure called trie.  A trie is a structure commonly used to represent words in a dictionary.  Each path from a root to a leaf corresponds to one word in the dictionary.  To avoid confusion between words like THE and THEN, we add a special end-marker \$ to the ends of all words.  Each node in the trie can have at most 27 children, one for each letter, and \$.  The following figure shows an example of the trie data structure for words {THIS, THE, THEN, THIN, SING, SIN}.

In this problem, you should implement the trie data structure, populate it with words from an input dictionary, and use it to covert sequence of input digits into word(s).

Some sample dictionaries can be downloaded from

The dictionary contains one word per line.

### Implementation Hints

·      You will notice that most nodes will have far fewer than 27 children.  For simplicity, you can use an array to store references to children, even though it is a waste of space.

·      You can save some space by not storing nodes with \$.

·      Think recursively.

·      Design before you implement.  This is not as difficult as you think.  The solution should be at most 300 lines.

### Input

The input contains both the dictionary and a sequence of mobile phone inputs, one per line.  The dictionary can be read from a local file (good for testing and debugging) or read from stdin (what OJ will use for testing).

Option 1: To read from a local file, the first line of the input must be #filename, where filename is the name of a dictionary file.  This is followed by multiple lines of mobine phone inputs.

Option 2: To read the dictionary from stdin, the inputs must begin with words in the dictionary, one per line.  Followed by multiple lines of mobile phone inputs.  Since dictionary must contains only uppercase letters, any numeric inputs indicates the end of dictionary words and the begin of mobile phone inputs.

### Output

The output contains either the exact word, or the possible words represented by the digits on the corresponding line.  Words on the same line must be in alphabetical order.

#850Basic.txt

23

5683

737

### Sample Output 1

AFTER BE CERTAIN

LOUD LOVE

PERSON REPRESENTATIVE REQUEST

THIS

THIN

THE

SIN

SING

THEN

SINGER

746

74643

SIN

SINGER