Data Structures

Lab #6: Binary Search Trees

Objective

During this activity, students will be able to:


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.