Changes to the Files for the Binary Tree Assignment

The files that are here now are up to date and presumably free from errors. A few changes have been made since they were originally posted, mostly to remove some of the more complex functionality that has been eliminated from this assignment. The differences are detailed below.

BinaryTree.h

Originally this class included extra functionality that we decided not to include. Also, a couple of the names have been changed, as has the display method. In what follows, struck text indicates the code has been removed (or needs to be remove), and highlighted text indicates new code. Comments in green describe changes; Comments in red describe fixed errors. 
⋮

template <class T>
class BinaryTree {
 public:

  /* Construction */
  BinaryTree() { root = NULL; }
  BinaryTree( T *elements, int n_elements );

  // This was for constructing an incomplete binary tree
  BinaryTree( T **elements, int n_elements );

  BinaryTree( const BinaryTree& src );
  ~BinaryTree() { empty_this(); }

  /* Access and Tests */
  bool is_empty() const;
  int height() const         { return height(root); }
  int node_count() const     { return node_count(root); }
  int leaf_count() const     { return leaf_count(root); }

  /* Mutators, and other Initialization */
  bool empty_this() { 
    empty(root); 
    root = NULL; // without this, the root node would be a dangling pointer   
    return true; 
  }

  // This function was intended to output an incomplete tree
  // in complete-tree order.
  int to_flat_array( T** nodes, int max ) const;

  // Now it assumes the tree is complete.
  int to_flat_array( T* elements, int max ) const;

  // This function initializes the tree as a complete tree
  // (it existed as a private method only; see below)
  void init_complete( T *elements, int n_elements );
  
  /* Traversal */
  void preorder( void (*f)(const T&) )  const { return preorder(f, root); }
  void inorder( void (*f)(const T&) )   const { return inorder(f, root); }
  void postorder( void (*f)(const T&) ) const { return postorder(f, root); }
               
  /* Operators */
  bool operator==( const BinaryTree& src ) const;
  bool operator!=( const BinaryTree& src ) const;

  // The const qualifier on this method is wrong;
  // the = operator has to be able to change 'this' instance
  BinaryTree& operator=( const BinaryTree& src ) const;

  /* Input/Output */
  // The input operator has been removed
  template<class S>
  friend istream& operator>>( istream& in, BinaryTree<S>& src );
  template<class S>  
  friend ostream& operator<<( ostream& out, BinaryTree<S>& src );

  /* Display */
  //  The display method now requires a PDF argument, and an optional annotation for the page
  void display() const;
  void display(PDF* pdf, const string& annotation = "") const;


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

  /* "Helper" functions for the basic operations */
  BTNode<T> *clone( BTNode<T> *node );
  
  int height( BTNode<T>* node ) const;

  // Balance factor computation has been eliminated from this assignment
  int balance_factor( BTNode<T>* node ) const;

  int node_count( BTNode<T>* node ) const;
  int leaf_count( BTNode<T>* node ) const;

  void preorder( void (*f)(const T&), BTNode<T> *node ) const;
  void inorder( void (*f)(const T&), BTNode<T> *node ) const;
  void postorder( void (*f)(const T&), BTNode<T> *node ) const;

  void empty( BTNode<T>* node );

  // These initialization helpers have been removed
  BTNode<T>* init( T *elements, int n_elements, int index );
  BTNode<T>* init( T **elements, int n_elements, int index );

  // and replaced with this helper, for initializing as a complete tree.
  BTNode* init_complete( T *elements, int n_elements, int index );

  // This method now assumes the binary tree is complete    
  int to_flat_array( T **nodes T *elements, int max, BTNode<T> *node, int index,
                     int& max_index ) const;

  // The display helper requires extra arguments.
  void display( BTNode<T>* node ) const;
  void display( PDF *pdf, BTNode* node, int leaf_dist,
                double x, double y, double scale ) const;


  // This helper for the input operator is no longer needed        
  template<class S> friend istream& operator>>( istream& in, BTNode<S>& src );

  template<class S> friend ostream& operator<<( ostream& out, BTNode<S>& src );

  //  Note: you may need more helper functions

}; 

#include "BinaryTree.cpp"

#endif
Also, the version I posted late last night had a couple of mistakes. Most notably, I accidentally removed the prototype for the output operator and left the prototype for the input operator.

BinaryTree.cpp

This file reflects the changes in the BinaryTre.h file. Also, the version I posted last night had a mistake: I changed the to_flat_array output parameter name from nodes to elements but apparently I forgot to change it in the function body.

PDF.h, PDF.cc, PDFFonts.cc

I originally had PDFFonts.cc included directly in PDF.cc (which is sometimes done when a source file contains only data or something). But that caused some trouble, so I took it out and PDFFonts.cc needs to be compiled explicitly.

I reworked the PDF code, to get rid of some sloppy memory handling, some unnecessarily slow code, and to fix a bug in the font selection.