CSS 343-A Binary Tree Programming Assignment

This assignment asks you to complete the implementations of binary tree classes. Unlike the previous assignment, in which you were allowed a fair amount of flexibility, for this assignment you will need to follow the internal implementation specification. (This allows for "white-box" testing, as the details of the implementation are available to the test code). Please do not deviate from the specification (you can add functions and functionality, but do not change the basic structure or any of the specified public methods).

The assignment is divided into three parts:

Part 1: Binary Tree Class
Part 2: Binary Search Tree Class
Part 3: AVL Tree

Part 1: Binary Tree Class Implementation

For this first part, you are asked to complete a C++ implementation of a general binary tree class. This is not specifically a binary search tree (that is in Part 2). The class is named BinaryTree, and is implemented as a template class where the class parameter is the type of the element stored in each node. See BinaryTree.h and BinaryTree.cpp for partial implementations. There is also a short main function in main.cc, that illustrates construction and display. (See also the Testing section below.)

You will also need PDF.h, PDF.cc, and PDFFonts.cc to get the graphical PDF output.

Note: these files have been modified slightly since they were first posted; a summary of the changes can be fount here (this also contains errata as other bugs surface).

Structure for Tree Nodes

The BinaryTree class uses the following struct to represent nodes.

template <class T>
struct BTNode {
  T       elem;  // element contained in the node
  BTNode *left;  // pointer to the left child (can be NULL)
  BTNode *right; // pointer to the right child (can be NULL)

  // Constructors
  BTNode();
  BTNode( T elem, BTNode* left = NULL, BTNode* right = NULL );
  BTNode( const BTNode& src );

  // Simple tests
  bool is_leaf() const;
};

Binary Tree Class

Your BinaryTree class is implemented as a template class, where the class parameter T is the type of the element stored in a node (i.e., it matches the T class parameter in BTNode). The following is a template for the BinaryTree class. Note that the only data member is a pointer to a BTNode, the root. (The access for the root node is protected, which means is will be visible to subclasses but otherwise is private.)

template <class T>
class BinaryTree {
 public:

  /* Construction */
  BinaryTree() { root = NULL; }
  ...

 protected:
  BTNode<T> *root;  // Root node (NULL if the tree is empty)
  ...
};

Constructors

BinaryTree() – constructs an empty binary tree.
BinaryTree( T *elements, int n_elements ) – constructs a complete tree having elements, in the usual order of a complete binary tree.
Note: the code implementing this is provided.
BinaryTree( const BinaryTree& src ) – copy constructor; constructs a duplicate of src
~BinaryTree() – destructor (deletes all the nodes in this tree).

Access and Tests

bool is_empty() – returns true if this tree is empty, and false otherwise
int node_count() const – returns the total number of nodes in this tree
int leaf_count() const – returns the number of leaf in this tree
int height() const – returns the height of this tree: the height of the empty tree is 0; the height of a nonempty tree is one plus the longest path from the root to any leaf.

Mutators, and other Initialization

bool empty_this() – empties (and deallocates) this tree
int to_flat_array( T* nodes, int max ) const – copies the node elements to the nodes array assuming this is a complete binary tree.
Note: the code implementing this is provided.

Traversal

void preorder( void (*f)(const T&) ) const – Performs a preorder traversal of this tree, applying f on the element of each node visited.
void inorder( void (*f)(const T&) ) const – Performs an inorder traversal of this tree, applying f on the element of each node visited.
void postorder( void (*f)(const T&) ) const – Performs a postorder traversal of this tree, applying f on the element of each node visited.

Operators

bool operator==( const BinaryTree& src ) const – returns true if this and src are identical; that is, if the tree structures are the same and the corresponding elements match.
bool operator!=( const BinaryTree& src ) const – logical complement of the == operator.
BinaryTree& operator=( const BinaryTree& src ) const – assignment operator: copies src to this tree (removing the prior content).

Input/Output

template<class S> friend ostream& operator<<( ostream& out, BinaryTree<S>& src ); – writes the sequence of nodes of src in complete-tree order to out assuming this is a complete binary tree.
Note: the code implementing this has been provided.

Compilation

The command-line compilation command (which will be used to compile and test your submitted code) is

g++ PDF.cc PDFFonts.cc main.cc

(or with test.cc in place of main.cc).

Testing

As usual, you are responsible for testing your own code. The file test.cc, which has its own main() function, contains some of the tests that will be used for your final submission.

Submission

Please submit your BinaryTree.h and BinaryTree.cpp files via the Catalyst dropbox by the specified due date.

Note: if you submit by Friday, we can provide feedback on your submission to assist in Part 2.

Clarifications and Caveats

In developing your methods, do not assume that the binary tree is complete. That may seem like a reasonable assumption, because only complete trees can be created as the class stands; however, any subclasses (e.g., the BinarySearchTree) may use the implementations in BinaryTree.
The display method uses the height method to determine the scale of the output. So if your height method isn't right, the output may be too large or too small.
You can add functionality to the BinaryTree.h and BinaryTree.cpp, such as helper functions for the == and = operators.

Part 2: Binary Search Tree Class Implementation

For this part, you are asked to extend your binary tree class from Part 1 into a binary search tree. Recall that a binary search tree (BST) is a binary tree in which each node has a key element (usually with other data) and the tree satisfies the binary search tree property: For each node, all the key values in the left subtree are strictly less than the key of the node, and all the key values in the right subtree are strictly greater than the key of the node. Duplicate key values are not allowed. Insertion and deletion of elements must be done in a way that maintains the binary search tree property. A BST is normally built by sequentially inserting elements; however, the structure of the tree is determined by the order of insertion.

Binary search trees are so named because they implement the basic operation of a binary search. To search a BST for an element having a specific key, start at the root: if the key element matches the search key, it is found; if the search key is less than the key of the node, proceed to the left child; otherwise the search key is strictly greater than the key of the node, so proceed to the right child. The maximum number of nodes that must be visited is therefore equal to the height of the tree.

A binary search tree is thus a binary tree with the extra functionality of insertion, deletion, and searching. In C++ (or any other object-oriented language), extending the functionality of a class is naturally done using the mechanism of inheritance. The binary tree class from Part 1 can therefore be made into a binary search tree by constsructing a subclass called BinarySearchTree of BinaryTree. This is done as follows (this file is available as BinarySearchTree.h).

template <class T>
class BinarySearchTree : public BinaryTree<T> {
 public:
  BinarySearchTree() { this->root = NULL; }
  BinarySearchTree( const BinarySearchTree *src ) : BinaryTree<T>(src) {}
  BinarySearchTree( T *elements, int n_elements );
  ~BinarySearchTree();
  
  /* BST Operations */
  bool insert( const T& elem );
  template<class K> T* lookup( const K& key ) const;

  /* Other Operations */
  void init_from_sorted_array( T *elements, int n_elements );
  int to_array( T *elements, int max );

  /* Input/Output Operators */
  template<class S>
  friend istream& operator>>( istream& in, BinarySearchTree<S>& obj );
  
 protected:
  // helper functions
};

BinarySearchTree is a subclass (also called a derived class or extension) of BinaryTree. All of the functions and data members from BinaryTree are directly inherited by BinarySearchTree except constructors, the destructor, and friend functions (although friend functions can still be applied because each subclass instance is also a superclass instance). As it happens, that's what we want, because the construction, input, and output are all different for a binary search tree.

Note on destructors: Destructors are not inherited directly, but the superclass destructor gets called immediately after the class destructor is called. The BinarySearchTree destructor could actually be empty, or even omitted.

Constructors

BinarySearchTree() – constructs an empty binary search tree.
BinarySearchTree( T *elements, int n_elements ) – constructs a binary search tree by sequentially inserting elements from the elements array (assuming elements contains n_elements). Note that this constructor is fundamentally different from that in the BinaryTree class, which treated the input as elements in a complete binary tree.
BinarySearchTree( const BinaryTree& src ) – copy constructor; constructs a duplicate of src. (This operation is identical to the construction of a general binary tree, so the BinaryTree copy constructor is called directly in the listing above.)
~BinaryTree() – destructor

BST Operations

bool insert( T elem ) – inserts elem into this tree, returning true on success, and false otherwise (i.e., if an element having the same key as elem exists in the tree).
lookup( K key ) – searches this tree for an element having key key, and returns a pointer to the element (not the node) in which it is found, or NULL if it is not found. The type parameter K is the type of the key, which need not be the same as the type T of the node elements. However, you can assume that = and < operators exist for comparing values of type K with values of type T (see the Remarks page below).
init( T* elements, int n_elements ) – initializes this tree by inserting each each element from the elements array in sequence. As this is an initialization, the tree should be emptied first.
init_from_sorted_array( T* elements, int n_elements ) – initializes this tree from the elements array, assuming the array is sorted. The resulting tree must be balanced. In order to do this, you will have to insert the elements non-sequentially, as discussed in class. Again, the first thing this function should do is empty the tree. (Properly implementing this function is a major part of this assignment.)
to_array( T* elements, int max ) const – copies the elements from this tree to the elements by way of an inorder traversal. At most max elements are copied, and the return value is the total number of elements.
operator>> reads a string of elements, inserting them into this tree in the order read. Note: this method does not empty the tree first, so that multiple >> operations continue to grow the tree.
operator<< writes the nodes of this tree in sorted order (i.e., via an inorder traversal).

As in the BinaryTree class, the best way to implement most of these is by way of (recursive) helper functions.

Testing

As usual, you are responsible for testing your own code. The source file test_bst.cc should help you get started.

Submission

Please submit your BinarySearchTree.h and BinarySearchTree.cpp files via the Catalyst dropbox by the specified due date.

Part 3: AVL Tree Implementation

This part has been postponed.

For more on the design decisions, see the Remarks page for this assignment.