Lab 9: Binary Search Trees II

Objectives

Learn how to remove data from the tree data structure.

Assignment

  1. Provide the implementation (tree.cpp) for the following tree_t interface (tree.h):
    #ifndef TREE_H
    #define TREE_H
    
    // forward declcarations
    template <typename T> class tree_t;
    template <typename T> std::ostream& operator<<(std::ostream&, const tree_t<T>&);
    
    template <typename T>
    class tree_t {
    
      private:
      struct node_t    // an all public class with data only, no member ftns
      {
           T        data;
           node_t   *left;
           node_t   *right;
    
           node_t(const T& d = T(), node_t *l = NULL, node_t *r = NULL) : \
                  data(d), left(l), right(r) \
                                          { };
      };
    
      public:
      // constructors (overloaded)
      tree_t();
    
      // copy constructor
    //tree_t(const tree_t& rhs);
    
      // destructors
      ~tree_t()                           { clear(); }
    
      // friends -- note the extra <> telling the compiler to instantiate
      // a templated version of the operator<< -- <T> is also legal,
      // i.e.,
      // friend std::ostream& operator<< <T>(std::ostream& s, const tree_t&);
      friend
      std::ostream& operator<< <>(std::ostream& s, const tree_t& rhs);
      friend
      std::ostream& operator<<(std::ostream& s, tree_t *rhs)
                                          { return(s << (*rhs)); }
      void inorder(std::ostream& s, node_t* const &t) const;
    
      // assignment operator
      const tree_t& operator=(const tree_t&);
    
      // operators
    
      // members
      bool     empty() const              { return root == NULL ? true : false;}
      bool     contains(const T& x) const { return contains(x,root); }
      void     insert(const T& x)         { insert(x, root); }
      void     erase(const T& x)          { erase(x, root); }
      void     clear()                    { clear(root); }
      const T& min() const                { if(!empty()) return(min(root)->data); }
      const T& max() const                { if(!empty()) return(max(root)->data); }
    
      private:
      node_t   *root;
    
      bool     contains(const T&, node_t* ) const;
      void     insert(const T& x, node_t* &t);
      void     erase(const T& x, node_t* &t);
      void     clear(node_t* &);
      node_t*  min(node_t* ) const;
      node_t*  max(node_t* ) const;
      node_t*  clone(node_t* ) const;
    };
    #endif
       
    Details
  2. Test code with the following main function:
    #include <iostream>
    #include <cstdlib>
    #include <sys/time.h>
    
    #include "pairs.h"
    #include "tree.h"
    
    int        main();
    
    int main()
    {
            int             num;
            tree_t<int>     tree;
            tree_t<pairs_t> ptree;
    
            struct timeval  tp;
    
      // get time of day
      gettimeofday(&tp,NULL);
    
      // use microseconds as the seed
    //srand((unsigned int)tp.tv_usec);
      srand((unsigned int)1337);
    
      // sort while inserting, thus maintaining list as priority queue
      std::cout << "Inserting:" << std::endl;
      for(int i=0;i<10;i++) {
        num = static_cast<int>((float)rand()/(float)RAND_MAX*100.0);
        std::cout << num << " ";
        tree.insert(num);
      }
      std::cout << std::endl;
    
      tree.insert(57);
      tree.insert(87);
      tree.insert(100);
    
      std::cout << "Tree min: " << tree.min() << std::endl;
      std::cout << "Tree max: " << tree.max() << std::endl;
    
      std::cout << "Tree contains 57? " << tree.contains(57) << std::endl;
    
      std::cout << "Tree: " << tree << std::endl;
    
      ptree.insert(pairs_t(45.0,'b'));
      ptree.insert(pairs_t(37.2,'c'));
      ptree.insert(pairs_t(42.6,'a'));
      ptree.insert(pairs_t(53.7,'d'));
    
      std::cout << "Pair Tree: " << ptree << std::endl;
    
      std::cout << "Tree: erasing 86" << std::endl;
      tree.erase(86);
      std::cout << "Pair tree: erasing (37.2,'c')" << std::endl;
      ptree.erase(pairs_t(37.2,'c'));
    
      std::cout << "Tree: " << tree << std::endl;
      std::cout << "Pair Tree: " << ptree << std::endl;
    }
    	

Sample output

Inserting:
1 86 24 21 30 74 89 64 21 68 
Tree min: 1
Tree max: 100
Tree contains 57? 1
Tree: 1 21 24 30 57 64 68 74 86 87 89 100 
Pair Tree: ('a',42.6) ('b',45) ('c',37.2) ('d',53.7) 
Tree: erasing 86
Pair tree: erasing (37.2,'c')
Tree: 1 21 24 30 57 64 68 74 87 89 100 
Pair Tree: ('a',42.6) ('b',45) ('d',53.7) 

Turn in

Turn in all of your code, in one tar.gz archive of your lab##/ directory, including:
  1. A README file containing
    1. Course id--section no
    2. Name
    3. Lab description
    4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
    5. Lessons learned, identified interesting features of your program
    6. Any special usage instructions
  2. Makefile
  3. source code (.h headers and .cpp source)
  4. object code (do a make clean before tar)

How to hand in

See sendlab notes