Please send questions to
st10@humboldt.edu .
/************************************************************/
/* ADAPTED FROM: */
/* http://www.cs.colorado.edu/~main/chapter10/bt_class.h */
/* */
/* Main and Savitch, "Data Structures and Other Objects */
/* using C++", 2nd edition, Addison-Wesley, Ch.10 */
/************************************************************/
//-----------------------------------------------------------
// File: binary_tree.h
// Name: Michael Main, Walter Savitch
// (adapted by Sharon M. Tuttle)
// last modified: 3-31-05
//
// Template Class: binary_tree<Item> (a binary tree where each
// node contains an Item)
//
// Note that each non-empty binary_tree instance
// always has a "current node". The location of
// the current node is controlled by three
// member functions: shift_to_root,
// shift_left, and shift_right.
//
// VALUE SEMANTICS for the binary_tree<Item> template class:
// Assignments and the copy constructor may be used
// with binary_tree<Item> objects.
//
// DYNAMIC MEMORY USAGE by the binary_tree<Item> template class:
// If there is insufficient dynamic memory, then the
// following functions throw bad_alloc:
// create_root, add_left, add_right, the copy constructor,
// and the assignment operator.
//-----------------------------------------------------------
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
#include <cstdlib> // Provides NULL and size_t
#include "binary_tree_node.h" // binary tree node template
// class adapted from Ch.
// 10 of Savitch and Main
using namespace std;
template <typename Item>
class binary_tree
{
public:
/******************************************************/
/* TYPEDEFS and MEMBER CONSTANTS for the binary tree */
/* class */
/******************************************************/
// The template parameter, Item, is the data type of the
// items in the nodes of the binary_tree, also defined
// as binary_tree<Item>::value_type.
// It may be any of the C++ built-in types (int, char,
// etc.), or a class with a default constructor, a
// copy constructor, and an assignment operator.
//
typedef Item value_type;
/****************************************************/
/* CONSTRUCTORS and DESTRUCTOR */
/****************************************************/
// postcondition: creates an empty binary tree instance
// (with no nodes).
//
binary_tree( );
// copy constructor
//
binary_tree(const binary_tree<Item>& source);
// destructor
//
// Library facilities used: binary_tree_node.h
~binary_tree();
/*******************************************************/
/* ACCESSORS and other constant member functions */
/* (observers) */
/*******************************************************/
// postcondition: returns the number of nodes in the
// binary_tree.
//
// Library facilities used: binary_tree_node.h
//
size_t get_size( ) const;
// postcondition: returns true if the binary_tree is
// empty, returns false otherwise.
//
bool is_empty( ) const;
// precondition: get_size( ) > 0
// postcondition: returns (non-destructively) the data
// from the "current node", BUT the binary_tree is
// unchanged.
//
Item retrieve( ) const;
// postcondition: returns true if get_size( ) > 0 and
// and the "current node" is the root.
//
bool is_root( ) const;
// postcondition: returns true if get_size( ) > 0 and
// the "current node" is a leaf (has no children)
//
bool is_leaf( ) const;
// postcondition: returns true if get_size( ) > 0 and
// the "current node" has a parent.
//
bool has_parent( ) const;
// postcondition: returns true if get_size( ) > 0 and
// the "current node" has a left child.
//
bool has_left_child( ) const;
// postcondition: returns true if get_size( ) > 0 and
// the "current node" has a right child.
//
bool has_right_child( ) const;
/****************************************************/
/* MODIFIERS and other modifying member functions */
/****************************************************/
// precondition: get_size( ) == 0
// postcondition: the binary tree now has one node (a
// root node) containing the specified entry. The
// new root node is the "current node".
//
void create_root(const Item& entry);
// precondition: get_size( ) > 0, and
// has_left_child( ) == false
// postcondition: a left child has been added to the
// "current node", with the given entry as its value.
//
void add_left(const Item& entry);
// precondition: get_size( ) > 0, and
// has_right_child( ) == false
// postcondition: a right chld has been added to the
// "current node", with the given entry as its value.
//
void add_right(const Item& entry);
// precondition: get_size( ) > 0, and
// has_left_child( ) == false
// postcondition: a left subtree has been added to the
// "current node", consisting of the passed tree.
//
void add_left_subtree(binary_tree<Item>& left_subtree);
// precondition: get_size( ) > 0, and
// has_right_child( ) == false
// postcondition: a right subtree has been added to the
// "current node", consisting of the passed tree
//
void add_right_subtree(binary_tree<Item>& right_subtree);
// precondition: get_size( ) > 0
// postcondition: the data at the "current node" has
// been changed to the new entry
//
void change(const Item& entry);
// preconditions: get_size( ) > 0, and has_left_child( )
// == true
// postcondition: the left subtree of the "current node"
// has been removed from the tree.
//
void remove_left_subtree( );
// preconditions: get_size( ) > 0, and has_right_child( )
// == true
// postcondition: the right subtree of the "current node"
// has been removed from the tree.
//
void remove_right_subtree( );
// postconditions: the tree is empty (and so there is
// no "current node")
//
void clear_tree( );
// precondition: get_size( ) > 0
// postcondition: the "current node" is now the root
// of the tree.
//
void shift_to_root( );
// precondition: has_left_child( ) == true
// postcondition: the "current node" has been shifted
// down to the left child of the old current node.
//
void shift_left( );
// precondition: has_right_child( ) == true
// postcondition: the "current node" has been shifted
// down to the right child of the old current node.
//
void shift_right( );
// preconditions: if !is_empty( ), depth is the depth of the
// calling binary_tree instance.
// postconditions: if !is_empty(), then the contents of the
// root and all of its descendants have been written to
// cout with the << operator using a backward in-order
// traversal. Each node is indented four times its depth.
void print_tree(size_t depth);
/****************************************************/
/* OVERLOADED OPERATORS */
/****************************************************/
// postcondition: the binary_tree that activated this
// will be made to have the same items as source
//
void operator =(const binary_tree<Item>& source);
private:
binary_tree_node<Item> *root_ptr; // points to root
// of binary tree
binary_tree_node<Item> *current_ptr; // points to
// "current node"
// in tree
};
#include "binary_tree.template" // Include the implementation
#endif