CptS
122 –
Data Structures
Lab
6: Data Structures and Dynamic Binary Search
Trees (BSTs) in C
Assigned: Week of
Due: At the end of the
lab session
I. Learner
Objectives:
At the conclusion
of this programming assignment, participants should be able to:
- Design,
implement and test a dynamic BST in C
- Compare
and contrast dynamic linked lists, dynamic stacks, dynamic BSTs, and
dynamic
BSTs
- Summarize
the advantages of applying a BST within certain applications
- Describe
the operations applied to a BST including
1. insertNode
( )
2. deleteNode
( )
3. inOrder
( )
4. preOrder
( )
5. postOrder
( )
II.
Prerequisites:
Before starting
this programming assignment, participants should be able to:
- Analyze
a basic set of requirements for a problem
- Compose
a small C language program
- Create
test cases for a program
- Apply
and implement structs in C
- Apply
and implement pointers in C
- Apply
and implement dynamic memory in C
- Design
and implement a dynamic singly linked list
- Design
and implement a dynamic stack
- Design
and implement a dynamic queue
This lab, along with
your TA, will help you navigate through designing, implementing,
and testing a dynamic BST. Recall, a BST data structure is a nonlinear,
two-dimensional data structure. A BST is traversed by starting at the
root
pointer. The root node is the first node inserted into the tree. Nodes
are
inserted into the tree such that all items to the left of the root node
are
less than, and all items to the right of the root are greater than its
item.
Also, this property holds true for any particular node in the tree. We
will
visualize a BST in the following way:
Labs are held in a
“closed” environment such that you may ask your TA
questions. Please use your TAs knowledge to your advantage. You are
required to
move at the pace set forth by your TA. Please help other students in
need when
you are finished with a task. You may work in pairs if you wish.
However, I
encourage you to compose your own solution to each problem. Have a
great time!
Labs are a vital part to your education in CptS 122 so work diligently.
Tasks:
1.
Command line arguments and file I/O (another review
exercise!)
Implement
a main program that will read, from the command
line, the name of the file containing the English text to convert to
Morse
code. At this point, just read from the test file and print it to the
screen to
be sure that you are reading the text correctly. You should be using
the fgets
( ) function for input and fputs ( ) or puts ( ) for output to the
screen.
2.
Defining the BSTNode structure
Create
a structure for the BSTNode data that will have as its
members a character and a character array of size 10. The character
will hold
the English text character, and the array will hold a string that
represents
the corresponding Morse characters for that English text character. You
also
need to define left and right child pointers that point to BSTNode
structures.
3.
Create the BST code and create a Morse lookup BST
You
should be able to read in the Morse table from a file. You
will have to rearrange the Morse table in the file to make sure that
your
lookup tree is balanced. (Think about the order of insertions).
Morse
Code Alphabet:
|
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
--.. |
0
----- 1
.---- 2
..--- 3
...-- 4
....- 5
..... 6
-.... 7
--... 8
---.. 9
----. FULLSTOP
.-.-.- Comma
‘,’ --..-- Query
‘?’ ..--.. |
As
you defined in Task 2, each BSTNode will have the data for
the English text characters and Morse code, and both left and right
child
pointers. You will need to create an insert ( ) function to fill the
tree with
each letter/Morse structure. You should arrange the tree so that it is
alphabetically ordered from left to right. Also create a print ( )
function
that uses recursion to traverse the tree in order (left most printed
first).
Finally build a search ( ) function that will return the Morse code for
each
English character searched for. Do you need to return a found indicator
from
the search function? Should you use recursion?
Also,
you should be able to print a diagram of your tree as
items are inserted into it!
4.
Putting the pieces together
Putting
it all together, you will read in a file on the
command line, look for each English letter with a search ( ) function
on the
BST, and print the Morse code for that letter. For each character in
the test
file, convert the character to a Morse code string. Each Morse
character will
be separated by a space. Each complete Morse string will be separated
by three
spaces. Each newline character will be echoed to the screen. The final
output
should be the FULLSTOP string. Note:
you
should convert any lowercase English characters to uppercase before
processing
the English text.
You
can create several small files to test your program or you may try the following:
This
is a test of the cpts 122
Morse
code conversion tool.
abc
def ghi jkl mno pqr stu vwx yz0 123 456 789
thanks
for your attention
- .... .. ...
.. ... .-
- . ... -
--- ..-.
- .... .
-.-. .--. - ...
.---- ..--- ..---
-- --- .-. ... .
-.-. --- -.. .
-.-. --- -. ...- . .-. ... .. --- -.
- --- --- .-.. .-.-.-
.- -... -.-.
-.. . ..-.
--. .... ..
.--- -.- .-..
-- -. ---
.--. --.- .-.
... - ..-
...- .-- -..
IV. Submitting Labs:
- You are
not required to submit your lab solutions. However, you should keep
them in a
folder that you may continue to access throughout the semester. You should not
store your solutions to the local C: drive on the Sloan 353 machines.
These
files are erased on a daily basis.
V. Grading Guidelines:
- This lab is worth 100 points. Your lab grade is assigned based on completeness and effort. To receive full credit for the lab you must show up on time
and continue to work on the problems and complete all the problems until the TA has dismissed you.