CSCE 2014 - Laboratory Assignment 11

    The objective of this laboratory assignment is to gain experience with the operations involving binary search trees. As you will see, this abstract data type is similar uses dynamic memory allocation to grow as the size of the data set grows. Unlike linked lists, a binary search tree is very fast to insert, delete and search.

  1. Introduction to Binary Search Trees
  2. A binary search tree (BST) is defined to be a linked set of nodes, where each node in the BST has a key value associated with it, and zero, one or two subtrees. All of the key values of all nodes in the left subtree are lower than the node's key value, and the key values of all the nodes in the right subtree are higher than the node's key value. This is illustrated in the BST below.

    Since this relationship between nodes is true for all nodes in the BST, we can search the tree to locate a specific value very quickly and easily (which is why defined the tree in this way). It turns out that insertion into a BST and deletion from a BST is also very fast and relatively easy. The remainder of this lab will focus on the implementation of these BST operations.

  3. The BinaryTree Class
  4. Consider the following C++ declaration of the BinaryTree class. First, you will notice that we have declared a very basic class called "Node" that contains three public variables, a Value and two Node pointers. We will be building our binary search tree using these Nodes.

    You also will see that the BinaryTree class has four basic operations: Search, Insert, Delete, and Print. You will also notice that there are private "Helper" methods for each of these operations that have ugly Node pointer parameters. We do this to hide Node pointers from users of this BinaryTree class.

    //-----------------------------------------------------------
    //  Purpose:    Header file for the BinaryTree class.
    //  Author:     John Gauch
    //-----------------------------------------------------------
    #include < iostream >
    #include < fstream >
    using namespace std;
    
    // Data node definition
    class Node
    {
       public:
       int Value;
       Node *Left;
       Node *Right;
    };
    
    //-----------------------------------------------------------
    // Define the binary tree class interface. 
    //-----------------------------------------------------------
    class BinaryTree
    {
     public:
       // Constructor functions
       BinaryTree();
      ~BinaryTree();
    
       // General binary tree operations
       bool Search(int Value);
       bool Insert(int Value);
       bool Delete(int Value);
       void Print();
    
     private:
       // Helper functions
       bool SearchHelper(int Value, Node * Tree);
       bool InsertHelper(int Value, Node * &Tree);
       bool DeleteNode(Node * &Tree);
       bool DeleteHelper(int Value, Node * &Tree);
       void PrintHelper(Node * Tree);
    
       // Tree pointer
       Node *Root;
    };
    

  5. BinaryTree Implementation
  6. Consider the partial implementation of the BinaryTree class below. We have intentionally left several functions empty, and we have omitted the Delete functions for now.

    //-----------------------------------------------------------
    //  Purpose:    Implementation of BinaryTree class.
    //  Author:     John Gauch
    //-----------------------------------------------------------
    #include "tree.h"
    
    //-----------------------------------------------------------
    // Constructor function.
    //-----------------------------------------------------------
    BinaryTree::BinaryTree()
    {
       Root = NULL;
    }
    
    //-----------------------------------------------------------
    // Destructor function.
    //-----------------------------------------------------------
    BinaryTree::~BinaryTree()
    {
    }
    
    //-----------------------------------------------------------
    // Search helper function.
    //-----------------------------------------------------------
    bool BinaryTree::SearchHelper(int Value, Node * Tree)
    {
       // Data value not found 
       if (Tree == NULL)
          return false;
    
       // Data value found 
       else if (Tree->Value == Value)
          return true;
    
       // Recursively search for data value
       else if (Tree->Value > Value)
          return (SearchHelper(Value, Tree->Left));
       else if (Tree->Value < Value)
          return (SearchHelper(Value, Tree->Right));
    }
    
    //-----------------------------------------------------------
    // Search for data in the binary tree.
    //-----------------------------------------------------------
    bool BinaryTree::Search(int Value)
    {
       // Call tree searching function
       return (SearchHelper(Value, Root));
    }
    
    //-----------------------------------------------------------
    // Insert helper function.
    //-----------------------------------------------------------
    bool BinaryTree::InsertHelper(int Value, Node * &Tree)
    {
       // Insert data into the tree
       if (Tree == NULL)
       {
          Tree = new Node;
          Tree->Value = Value;
          Tree->Left = NULL;
          Tree->Right = NULL;
          return true;
       }
    
       // Data value already inserted
       else if (Tree->Value == Value)
          return false;     
    
       // Recursively search for insertion position
       else if (Tree->Value > Value)
          return (InsertHelper(Value, Tree->Left));
       else if (Tree->Value < Value)
          return (InsertHelper(Value, Tree->Right));
    }
    
    //-----------------------------------------------------------
    // Insert data into the binary tree.
    //-----------------------------------------------------------
    bool BinaryTree::Insert(int Value)
    {
       // Call tree insertion function
       return (InsertHelper(Value, Root));
    }
    
    //-----------------------------------------------------------
    // Print helper function.
    //-----------------------------------------------------------
    void BinaryTree::PrintHelper(Node * Tree)
    {
       // Check terminating condition
       if (Tree != NULL)
       {
          // Print left subtree
          PrintHelper(Tree->Left);
    
          // Print node value
          cout << " " << Tree->Value << " ";
    
          // Print right subtree
          PrintHelper(Tree->Right);
       }
    }
    
    //-----------------------------------------------------------
    // Print all records in the binary tree.
    //-----------------------------------------------------------
    void BinaryTree::Print()
    {
       // Call tree printing function
       PrintHelper(Root);
       cout << endl;
    }
    
    //-----------------------------------------------------------
    // Main program.
    //-----------------------------------------------------------
    int main()
    {
       // ADD HERE
    }
    

  7. Testing the BinaryTree Class
  8. Copy and paste the class declaration into a file called "tree.h" in your NetBeans project. Then copy and paste the class implementation into a file called "tree.cpp". When you compile and run this code, it should do nothing.

    Now extend the main function, to create a BinaryTree object called "tree" and then call the Insert method to store 10 random numbers between [0..9] into the binary search tree. You should use the "rand()" function to do this.

    When you run this program, you will notice that it does not print anything out. If you look at the implementation of the "Insert" and "InsertHelper" methods you will see that they return "true" when the insertion was successful and "false" otherwise. Using this information, edit your main function and add a cout statement to print out a message when a value is correctly inserted, and a different message if the insert fails.

    Cut and paste your new main function below:

    Cut and paste your new program output below:

  9. More Testing of BinaryTree
  10. In order to see what data is in the binary search tree, modify your main function to call the "Print" method after your 10 insertions. You should see a sequence of values in ascending order. Unfortunately, this does not look like much of a tree. To improve this situation, modify the "Print" method to print out brackets "(" and ")" before the left subtree and after the right subtree respectively. Now your tree output should look something like this:

    (( 1 ( 2 )) 3 ( 4 ( 5 (( 6 ) 9 ))))

    This tree has 3 at the root, and the top of the left subtree is 1, and the top of the right subtree is 4. The more "(" and ")" there are around a value, the further down the tree that node is.

    Now modify your main program again and create a second BinaryTree object called "tree2" and insert 10 numbers in increasing order into this tree. When you print tree2, your output should be very different from above. Repeat the experiment and create "tree3" with 10 numbers inserted in descending order, and print out tree3. It should look very different from "tree" and "tree2".

    Cut and paste your new main function below:

    Cut and paste your new program output below:

  11. Writing a Count Method
  12. Now that you have seen how the print function operates, you are ready to write your own recursive binary search tree function. The easiest operation to implement is to count the nodes in the tree. Write two functions, a public "Count" and a private "CountHelper" that return the number of nodes in the binary search tree.

    As with any recursive function think about your terminating condition and your recursive calls. Now test your new "Count" method by calling it to print out the number of nodes in your "tree", "tree2" objects. Hopefully your results will confirm what you see when you "Print" these binary search trees.

    Cut and paste your two new "Count" methods below:

    Cut and paste your new program output below:

  13. Writing a Height Method
  14. The height of a binary tree is given by the length of the longest sequence of nodes from the root to any leaf node. This height tells us how many comparisons will be needed in the worst case when searching the tree for a specified data value. The difference between the heights of the left subtree and right subtree for a node also tells us how unbalanced a tree is. Hence being able to calculate tree heights is an important operation.

    Write two "Height" functions, one public and one private (similar to Count above) that work together to calculate the height of a binary search tree. Again, think about your terminating condition and how to use information gathered in recursive calls. Now test your new "Height" function with your "tree" and "tree2" objects to debug your code.

    As your last experiment, go back to your main function and initialize "tree" with 1024 random values between [0..1024], and "tree2" with 1024 values in increasing values. You will probably want to remove your cout commands as data is inserted. Now, call your "Height" function on "tree" and "tree2" and compare the results. Hopefully, you will see that one tree is significantly shorter than the other.

    Cut and paste your two new "Height" methods below:

    Cut and paste your new program output below:

  15. Submit Work
  16. This lab assignment will be submitted electronically to the TAs once you fill in the fields below and click on the "submit" button. You do NOT need to print a copy of this document to hand in.

    Your full name:
    Your uaid number: