Lab 8: Binary Search Trees I

Objectives

Learn how to implement the tree data structure.

Trees

Binary Search Trees pp. 124-130

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     clear()                    { clear(root); }
    
      private:
      node_t   *root;
    
      bool     contains(const T&, node_t* ) const;
      void     insert(const T& x, node_t* &t);
      void     clear(node_t* &);
      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);
    
      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;
    }
    	

Sample output

Inserting:
1 86 24 21 30 74 89 64 21 68 
Tree contains 57? 1
Tree: 1 21 24 30 57 64 68 74 86 89 
Pair Tree: ('a',42.6) ('b',45) ('c',37.2) ('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