Lab 9: Binary Search Trees II

Objectives

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
   • The private erase method: To remove a specific node, you must first locate it (recursively traversing the appropriate left or right subtree depending on each node's data value).
     If it is found and one of its children is NULL, set the current node to its non-NULL node and then delete the node.
     If, however, both of the node's subtrees are non-NULL, replace the current node's data with the smallest element in its right subtree, then (recursively) erase the element with that value from the node's right subtree.
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

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