Assignment 9 Solutions

CSCI 132 Data Structures--Spring 2014

Assignment 9 Solutions
Solution binary tree functions

/*******************************************************************
* Name: Brenda Student
* Date: 4/28/14
* Course: CSCI 132 Section 01
* Assignment: Assignment 9
* Instructor: Royden
* Program: binary_tree.cc
* Purpose:  Implements the functions in the Binary_tree class
***************************************************************************/

template <class Entry>
int Binary_tree<Entry> :: size() const
/* Post: Returns the number of nodes in the tree
Uses: The function recursive_size */
{
  return recursive_size(root);
}

template <class Entry>
int Binary_tree<Entry> :: recursive_size(Binary_node<Entry> *sub_root) const
/* Post: Returns the number of nodes in the tree or subtree pointed to by sub_root*/
{
  if (sub_root == NULL) {
  	return 0;
  } else {
  	return 1 + recursive_size(sub_root -> left) + recursive_size(sub_root -> right);
  }
}

template <class Entry>
void Binary_tree<Entry> :: clear( )
/* Post: All entries of the binary tree are removed. */
{
  recursive_clear(root);
}


template <class Entry>
void Binary_tree<Entry> :: recursive_clear(Binary_node<Entry> * &sub_root)
/* Post: The subtree rooted at sub_root is cleared. */
{
  Binary_node<Entry> *temp = sub_root;
  if (sub_root == NULL) return;
  recursive_clear(sub_root->left);
  recursive_clear(sub_root->right);
  sub_root = NULL;
  delete temp;
}