Description

Purpose
to familiarize you with Binary Search Trees

Tasks

• Create a Binary Search Tree Class (don’t allow duplicates)
  • Member variables
    • root
  • Constructor
  • Destructor
  • Size( ): Returns the number of elements in the tree
  • Print( ): Do the indented print that was discussed in class
    • Pre order traversal
    • Print one element per line
    • Indent according to the depth
      • See page 505
  • Erase(int item): Erase the occurrence of the item in the tree (there should be 1 or 0 occurrences).
    • Resulting tree should still be a BST
  • Insert(int item): Insert the item into the BST. Don’t allow duplicate numbers.
  • Traversals (just print out the items, don’t worry about passing functions as parameters)
    • Pre-Order
    • In-Order
    • Post-Order
• Create a Driver
  • Complete the interactive test driver
    • Start with the template provided, and fill it out
  • Test all public functions
    • You can test the destructor by having the destructor call another function called destroy, which should erase all of the elements in the tree by adapting one of the traversals to do this.
    • Think of all possible test cases
      • Root nil
      • Root has one member, no children
      • Many others
    • Be sure to test all types of delete, both at the root and below

Turn in

• Code (.h and .cpp files)
• Windows executable