Laboratory
Objectives
- To practise implementing BST functions.
- To practise using function pointers.
Assessment
- Deadline
-
16 December 2018, 23:59:59
6 January 2019, 23:59:59 - Marks
- 3
- Submission
give cs2521 lab03
This lab should be done individually.
Setting up
Create a directory for this lab, change into it,
and retrieve the files with the fetch
command:
2521 fetch lab03 './btree.h' -> '/web/cs2521/19T0/week03/files.ln/btree.h' './item_btree_node.h' -> '/web/cs2521/19T0/week03/files.ln/item_btree_node.h' './item.h' -> '/web/cs2521/19T0/week03/files.ln/item.h' './item_int.h' -> '/web/cs2521/19T0/week03/files.ln/item_int.h' './queue.cse32.o' -> '/web/cs2521/19T0/week03/files.ln/queue.cse32.o' './queue.cse64.o' -> '/web/cs2521/19T0/week03/files.ln/queue.cse64.o' './queue.h' -> '/web/cs2521/19T0/week03/files.ln/queue.h' './testable.h' -> '/web/cs2521/19T0/week03/files.ln/testable.h' ./ Makefile btree.c test_btree.c
This will have provided you with several files (as you may have guessed by its output):
Makefile
- contains build rules.
btree.h
- A binary tree interface. Do not change this file.
btree.c
- A partial implementation of a binary tree; you need to modify this to finish implementing the interface.
test_btree.c
- A stub for you to write tests in.
item.h
- A generic
Item
type. Do not change this file. item_int.h
- Support for
int
s asItem
s. Do not change this file. item_btree_node.h
- Support for
BTreeNode
s asItem
s. Do not change this file. queue.h
- A Queue ADT interface. Do not change this file.
queue.cse32.o
- A Queue ADT implementation, which we’ve provided as a precompiled binary for 32-bit CSE systems.
queue.cse64.o
- A Queue ADT implementation, which we’ve provided as a precompiled binary for 64-bit CSE systems. (You probably don’t need this file.)
The provided code contains tags marking unused variables. You should remove these tags as you implement those functions.
The syntax for manipulating function pointers is sufficiently opaque that type aliases are almost a requirement for legible code.
Exercise 0: test_btree.c
In test_btree.c
,
for each of the following tasks,
you must write assert(3)-based unit tests
to test your functions.
You will lose half the marks for that exercise
if you don’t have reasonable tests.
Exercise 1: Count Leaves (0.5 marks)
In btree.c
,
implement the function btree_size_leaf
:
/** Returns the number of leaf nodes in the tree. */
size_t btree_size_leaf (BTreeNode tree);
Exercise 2: [thud] (0.5 marks)
In btree.c
,
implement the function btree_drop
:
/** Destroy a tree, releasing all resources it requires. */
void btree_drop (BTreeNode tree);
Exercise 3: Keep a Level(-Order) Head (1 mark)
In btree.c
,
there’s some very useful mechanics
for traversing a tree.
btree.h
only exposes one function,
btree_traverse
, which takes a tree,
and two parameters describing what to do:
a btree_traversal
, an enumeration describing
prefix-, infix-, postfix-, and level-order,
and a btree_visitor_fp
,
which is either NULL
or a pointer to a void
-returning function
that takes a btree_node
reference.
If the last argument is NULL
,
it returns an array of btree_node
pointers,
otherwise it returns NULL.
This seems all a bit opaque, so here’s an example that produces an array:
size_t n_nodes = btree_size (tree)
BTreeNode *nodes =
btree_traverse (tree, BTREE_TRAVERSE_PREFIX, NULL);
for (size_t i = 0; i < n_nodes; i++) {
BTreeNode node = nodes[i];
Item nvalue = btree_node_value (node);
char *str = item_show (nvalue);
printf ("%s ", str);
free (str);
}
free (nodes);
And here’s an example that prints the nodes as it goes.
static void node_print (BTreeNode node)
{
Item nvalue = btree_node_value (node);
char *str = item_show (nvalue);
printf ("%s ", str);
free (str);
}
btree_traverse (tree, BTREE_TRAVERSE_PREFIX, node_print);
There’s some code to make that work;
if you’re interested,
have a close read of
btree_traverse
and
btree_traverse_visit
.
We’ll talk more about
stateful iteration
later on in the course.
In btree.c
,
you should implement
the function btree_traverse_level
,
which performs the level-order traversal
of a binary tree.
static void btree_traverse_level (btree_node *, traverse_state *);
Here’s a diagram to give you an idea of how a level-order traversal scans the nodes in a tree:
The output from this traversal would be .
A level-order traversal cannot be done recursively — at least, not easily — and is instead typically implemented using a queue of items. The algorithm is roughly:
level_order bst = do
q = new Queue
q.join bst.root
while q.size > 0 do
node = q.leave
visit node
q.join node.left if exists node.left
q.join node.right if exists node.right
end
end
We’ve provided a Queue ADT interface and implementation, but with a twist: we’ve only given you a compiled object for the implementation. (You’ll want to do this exercise on CSE.)
We’ve also changed how Item works a little,
so you need to explicitly turn values into Items,
and explicitly turn Items back into values:
for int
s,
use int_item_new
to make an Item,
and int_item
to retrieve the value;
for BTreeNode
s,
use BTreeNode_item_new
to make an Item,
and BTreeNode_item
to retrieve the value.
Exercise 4: BSTs and Function Pointers (1 mark)
Write a function
size_t btree_count_if (BTreeNode tree, btree_pred_fp pred);
which traverses a binary tree,
and counts the number of items in the tree
for which the application of pred
returns a true value.
For example, given the tree
and a function
bool even_p (Item n);
which returns true
if n
is even,
and false
otherwise –
– calling
n_even_elems = btree_count_if (tree, even_p);
would return the value 3 in n_even_elems
.
You will need to write
some predicate functions,
including even_p
, odd_p
,
and negative_p
.
In your test_btree.c
file,
when you write test cases to test your function,
write a suite of tests
that use all predicates (even_p
, odd_p
, negative_p
).
Submitting
You must get the lab marked by your tutor in your lab.
Submit your work with the give command, like so:
give cs2521 lab03 btree.c test_btree.c
Or, if you are working from home, upload the relevant file(s) to the lab03 activity on WebCMS3 or on Give Online.