CS 596 Assignment 2
| CS 596|
Fall Semester, 1998
|To Assignment Index|
San Diego State University -- This page last updated 20-Sep-98
30, in class for SDSU section,
1 in class for Qualcomm section
a ternary search tree with integer keys. A ternary search tree is like a binary
search tree, except each node in the tree has up to two keys and three
subtrees. Figure A below shows a node with keys 10 and 20. The subtree A
contains keys with values less than 10, the subtree B contains keys with values
between 10 and 20. The subtree C contains keys with values greater than 20.
When you insert a key into an empty ternary tree, that key becomes a key in the
root node. The second key inserted into the ternary tree becomes the second key
in the root node. These two keys are kept in order. All subsequent keys are
inserted using the same rules in the proper subtree of the root note. So if we
were to insert the numbers 10, 40, 7, 20, 5, 6, 30, 15 we would get the tree in
Figure B. Your ternary tree needs to have the following methods:
int key, Object value) which stores the key and object in the proper location
in the tree as described above. If key is already in the tree, its value is
changed to the new value.
int key) returns the value stored in with the given key in the tree.
int key) returns true if the tree contains the key.
returns a string representation of the tree using the following recursive rule:
for each node print "(" then left subtree, smallest key, middle subtree,
largest key, right subtree ")". So toString() on the tree in figure B will
result in (( 5 (6) 7 ) 10 ( (15) 20 30) 40 )
ternary tree and any support classes need to be in a package. Your test program
can not be in that package. Test input will be given later.
Copyright © 1998 SDSU & Roger Whitney, 5500 Campanile Drive, San Diego, CA 92182-7700 USA.
All rights reserved.
visitors since 20-Sep-98