Binary Search Tree Pt2

Video 




you will create a Binary Search Tree
copy over all the files from the last lab

and copy over the runable examples from the directory for this lab

 
             Binary Search Tree
  ===============================================
  i  Insert a value into the tree                
  c  Does the tree contain a specific value      
  d  Delete a value from the tree                
  y  Print the values of the tree in pre order
  p  Print the values of the tree in order
  z  Print the values of the tree in post order
  m  Show this menu
  x  Exit                                        
  ===============================================
  Enter selection:




the output when testing should match that of the runable examples

you will need to add and test the following functions


    // private helper function for class destructor
    // parameter a node pointer for the tree
    // call this function from your destructor to clean up all the nodes created
    // Used for recursive POST ORDER traversal
    // and deletion of a node and its children
    // return type void
    void deallocateSubtree(TreeNode * subtree)
    {
      // try to go down both sides
      // finally delete this node

    }


    // private helper function for search. Performs the BST search on the given subtree
    // root node. It uses recursion to traverse in PRE ORDER the proper search path for the
    // given value.
    // return type bool, was the value found
    bool  containsSubtree(TreeNode *subtree, T elem)
    {

        // if the current node contains the value you are looking for return true
        
        // if the element we are looing for is less than the value stored in the current node search left
        // if the left pointer is valid cascade the search down that path
        
        // if the elemnt was NOT less than the value stored in the current node search right
        // if the right pointer is valid cascade the search down that path
    }



copy your print and print subtree functions twice so that you can have one that prints in pre order and post order as well

 print
 printsubtree
 
 printpre
 printpresubtree

 pringpost
 pringpostsubtree






MAKE sure you output matches the examples when you redirect in the testfiles
MAKE sure your print output can be used on the viewlist page

 viewtree 



your ouput must work with the viewlist page

check for leaks

> make clean
> make LOGLEVEL=0
> valgrind --leak-check=full ./runme_int

look for 

==12988== 
==12988== All heap blocks were freed -- no leaks are possible
==12988==