Lab #6: Binary Search Trees

Objective

During this activity, students will be able to:

Design and implement operations on binary search trees using C++.

Description

NOTE: The files needed to start this lab are available in this tarball file: treeset.tgz. To uncompress, type at the Linux terminal:

tar xzf treeset.tgz

This lab consists of defining a class TreeSet<T> which implements a generic set (a collection without repeated elements) using a binary search tree. The class must be fully declared and implemented in the treeset.h file, and must include all of the operations described below.

IMPORTANT: Before the definition of each operation you must include a comment that indicates its corresponding time complexity.

Operation	Description
`TreeSet()`	Constructor. Creates an empty tree.
`TreeSet( std::initializer_list<T> args )`	Constructor. Creates an initialized tree from the elements contained in `args`.
`~TreeSet()`	Destructor. Frees this tree’s dynamically allocated memory.
`bool add(T value)`	Member function. Add `value` to this tree. Returns `true` if it was successfully added, or `false` otherwise (if `value` already existed in the tree).
`int size() const`	Member function. Returns the number of elements contained in this tree.
`bool is_empty() const`	Member function. Returns `true` if this tree is empty, or `false` otherwise.
`bool contains(T value) const`	Member function. Returns `true` if `value` is contained in this tree, or `false` otherwise.
`void inorder( std::function<void(T)> fn ) const`	Member function. Traverses this tree in inorder, calling `fn(value)` when visiting each node.
`void preorder( std::function<void(T)> fn ) const`	Member function. Traverses this tree in preorder, calling `fn(value)` when visiting each node.
`void postorder( std::function<void(T)> fn ) const`	Member function. Traverses this tree in postorder, calling `fn(value)` when visiting each node.
`void levelorder( std::function<void(T)> fn ) const`	Member function. Traverses this tree by levels (breadth-first), calling `fn(value)` when visiting each node.
`int height() const`	Member function. Returns the height of this tree. Returns -1 if the tree is empty. Returns 0 if the tree has only one node.
`bool is_full() const`	Member function. Returns `true` if this tree is full, or `false` otherwise. A full binary tree is one in which each node has zero or two children. As a special case, an empty tree is considered full.
`int leaf_count() const`	Member function. Returns the total number of leaves in this tree. A leaf is a node that has no children.
`bool is_perfect() const`	Member function. Returns `true` if this tree is perfect, or `false` otherwise. A binary tree is perfect if all the internal nodes have two children and if all their leaves are at the same level.

Test your code using the unit tests contained in the tests.cpp file (contains a total of 111 assertions). Also, run the code using valgrind to check for memory leaks and other memory related errors.

Deliverables

Nothing. This is a class exercise.