Lab 2: Binary Search Trees (part 2)

Lab Structure

  1. Do NOT login until your TA directs you to do so.
  2. Read through the lab and make sure you understand it.
  3. Use your book to look up anything that is unclear to you about the lab. Do NOT copy down any of the steps or code from the book.
  4. After using the book, if something is still unclear, ask you TA or neighbor. Do NOT take any code or pseudocode (verbally or on paper) from your neighbor.
  5. Once you feel ready to do the lab on your own, your TA will allow you to log in.
  6. Once you have logged in, you may NOT use the book for reference or talk to another student. You should be able to write all of the code by yourself.

Object-Oriented Programming p. 12

  • A class consists of its members: data and fuctions. The data in a class are in the form of instance variables. The operations are in the form of methods. An object is an instance of a class. Whereas a class defines the behavior for a set of objects, and object is an individual implementation of a class.
  • An instance variable is a variable belonging to a class. Every object of that class has its own copy of the instance variables. The instance variables are also called the data attributes and represent the state of the object.
  • A key difference between a class and a group of related functions is that a class maintians state (i.e. has data attributes associated with the member functions).
  • A method (aka member function) is a function with access to the instance variables in the object. There are different types of methods in a class:
    1. Accessor methods (p. 15): use one or more of the instance variables without changing them. These methods are marked as const methods because they do not modify the state of the object.
    2. Mutator methods: modify one or more of the instance variables.
    3. Constructors: perform any initialization needed for the class. In other words, each constructor provides initial values to each instance variable. There are three (3) types of special constructors:
      1. Default constructor (p. 12): Takes no parameters. Can be called implicitly: BNode node;
      2. Conversion constructor (p. 14): Takes one parameter. It is called the conversion constructor because it converts a variable to an object of the class: BNode node (14); It is called implicitly with this notation: BNode node = 14;
      3. Copy constructor (p. 24): Takes one parameter: a constant reference to an object from this class. The copy constructor is written for you automatically, but if your class has dynamically allocates any memory or uses pointers, you may need to override the default behavior. It can be called implicitly with this notation: BNode node1 = node2;
        NOTE: node1 = node2 calls the assignment operator operator= (p. 24). The difference is that the copy constructor can be called only when the object is first created.
    4. Destructor (pp. 23-24): perform any cleanup needed. Any memory that was allocated for the object should be deleted in the destructor.
  • Encapsulation: One of the goals of Object-Oriented programming (OO) is to keep the data encapsulated; that is, the data is accessible only through official means: use of the accessor and mutator methods. Therefore instance variables are usually private to prevent unauthorized access and modification.
  • Friends: Declaring a function or class to be friends actually breaks encapsulation and allows access without use of methods. However, sometimes it is difficult to depend solely on get and set methods. Additionally, operator overloading is sometimes impossible without befriending the class.

Lab 2 Assignment

  1. Type up the starter code below.
  2. Implement The new methods in BNode:
    1. operator==(int), operator> (int), and operator< (int) (pp. 32-33): Compare the data in this BNode to the value passed in.
    2. operator==(int, const BNode &), operator> (int, const BNode &), and operator< (int, const BNode &): Compare value to the data in the passed in BNode.
    3. operator<< (std::ostream &, const BNode &): Output this node and its subtree recursively.
    4. operator<< (std::ostream &, const BST &): call operator<< on the root.
    5. findMin (p. 125) and contains (p. 125): should be straightforward.
    6. remove (pp. 130-131):
      1. If the node is a leaf (no children), simply remove it.
      2. If the node has one child, promote its child to replace it.
      3. If the node has two children, replace the node with the smallest value in the right subtree. findMin should come in handy.
    7. Copy this makefile to compile all the code together. Be sure you understand what is going on for future makefiles:

      # Source, Object, and Header extensions (XT)
      # To use these variables, use a $ with parentheses: $(variable)
      SCXT    = cpp
      OBXT    = o
      HDXT    = h

      # C Compiler and Compiler flags
      CC      = g++
      CFLAGS  = -Wall

      # A list of the needed header files and Object files
      HEADERS = BST.$(HDXT) BNode.$(HDXT)
      OBJS = BNode.$(OBXT) BST.$(OBXT)

      # The magic: For any file *.cpp that we need a .o file for, this code will
      # be used to perform the compilation.
      .$(SCXT).$(OBXT):
              $(CC) -c $(CFLAGS) $(INCLUDE) -o $*.$(OBXT) $*.$(SCXT)

      # The final linking of the object files
      a.out: $(HEADERS) driveBST.$(OBXT) $(OBJS)
              $(CC) driveBST.$(OBXT) $(OBJS)

Starter Code

// BinaryNode
// BNode

#include <iostream>
using namespace std;

class BNode {
   private:
      int data;
      BNode *left, *right;

   public:
      BinaryNode (); // default constructor
      BinaryNode (int d); // conversion constructor
      BNode (int d=0, BNode *l=NULL, BNode *r=NULL);
      BNode (const BNode &node); // Not necessary. For example purposes only.

      bool operator==(int value) const;
      bool operator> (int value) const;
      bool operator< (int value) const;

   friend bool operator==(int value, const BNode &node);
   friend bool operator> (int value, const BNode &node);
   friend bool operator< (int value, const BNode &node);
   // output this node's entire subtree (left, data, and right).
   friend std::ostream &operator<< (std::ostream &out, const BNode &node);
   friend class BST;
};

// The code after the : is an initializer list. (See page 13.) It is more
//   efficient than assignment for complex types.

BNode::BNode (int d=0, BNode *l=NULL, BNode *r=NULL) :
data (d), left (l), right (r) {
}

BNode::BNode (const BNode &node) : data (node.data), left (node.left),
                                   right (node.right) {
}

// BinarySearchTree
// BST
#include "BNode.h"

class BST {
   private:
      BNode *root;
      int findMin (const BNode *node) const;
      bool contains (int value, const BNode *node) const;
      void makeEmpty (BNode * &node);
      void insert (int value, BNode * &node);
      void printTree (const BinaryNode *node, ostream &out);
      void remove (int value, BNode * &node);

   public:
      BST ();
      ~BST ();

      bool isEmpty () const;
      bool contains (int value) const;
      int findMin () const;
      void makeEmpty ();
      void insert (int value);
      void remove (int value);
      void printTree (ostream &out);

   friend std::ostream &operator<< (std::ostream &out, const BST &tree);
};

BST::BST () : root (NULL) {
}

BST::~BST () {
   makeEmpty();
}

bool BST::isEmpty() const {
   return NULL == root;
}

void BST::makeEmpty () {
   makeEmpty (root);
}

void BST::makeEmpty (BNode * &node) {
   if (NULL != node) {
      makeEmpty (node->left);
      makeEmpty (node->right);
   }
   delete node;
   node = NULL;
}

void BST::insert (int value) {
   insert (value, root);
}

void BST::insert (int value, BNode * &node) {
   if (NULL == node) {
      node = new BNode (value, NULL, NULL);
   } else if (*node > value) { // calls operator> in BNode
      insert (value, node->left);
   } else if (*node < value) { // calls operator< in BNode
      insert (value, node->right);
   }
}


#include <fstream>
int main (int argc, char *argv[]) {

   BST tree;
   std::ofstream out("output.txt", std::ios::out); // output to a file
   out << tree;

   if (argc < 2) {
      std::cerr << "USAGE: " << argv[0] << " numbers to insert " << std::endl;
      return EXIT_FAILURE;
   }

   for (int i=1; i < argc; ++i) {
      tree.insert (atoi(argv[i]));
   }
   tree.printTree(cout);
   out << tree << std::endl;

   if (!tree.contains (atoi (argv[1]))) {
      out << "ERROR: " << argv[1] << " is not in the tree." << std::endl;
   }

   out << "Removing " << argv[argc/2] << std::endl;
   tree.remove (atoi (argv[argc/2]));
   out << tree;
   out.close();

   return EXIT_SUCCESS;
}
  • Turn in your code and a Makefile to create a.out.
    Use sendlab.212.302 2 *.cpp *.h Makefile