CMSC 214 - Project #3

C M S C 2 1 4
C o m p u t e r S c i e n c e I I
S p r i n g 2 0 0 2

MovieBstSortedList Specifications

Corrections, etc.

All three traversals (and print()) should print "EMPTY LIST" if the tree is empty (one of them printed something else, and that was an error).
Changed the message from [PREORDER TRAVERSAL] to [PRINT_PREORDER],. and [INORDER TRAVERSAL] to [PRINT_INORDER], and [POSTORDER TRAVERSAL] to [PRINT_POSTORDER] to match BNF posted. (4/2)
Added the default constructor definition. (3/22)
The return type for getData() in MovieBstSortedList::Node has been corrected to return Movie references. (3/20)

Definition of Recursive Function

For the purposes of this project, a "recursive" function is defined as a function that has no loops, and either calls itself, or calls a helper function that calls itself. (Most people define "recursive" functions as any function that calls itself, regardless whether there is a loop or not---however, we will use the loopless definition, which is more restrictive).

DO NOT CHANGE PARAMETERS OF PUBLIC METHODS. If necessary, call a helper function with additional parameters.

MovieBstSortedList

You will need to templatize this class in the same way you templatized the MovieSortedList class. Since you won't have to submit MovieBstSortedList (only need to submit BstSortedList), you can make the name of MovieBstSortedList shorter (using MBSL for example). However, you shouldn't make BstSortedList shorter. That should be left alone.

Data Members

Declaration	Description
*Node root**	Pointer to the root of a BST

You may add any or all of the following additional private data members, although it is optional:

Node *first, which points to the node with the smallest key.
Node *last, which points to the node with the largest key.
int listSize, which contains the number of nodes in the tree.

Try to avoid adding other data members, without asking the instructors first.

Public Methods

MovieBstSortedList() ;

Default constructor. Sets root to NULL. Should initialize the BST to an empty tree. (ADDED: 3/22)

bool add( const Movie &dataIn ) ;

Add a Movie object to the BST, only if the Movie's title does not already exist in the BST. If it does NOT, then return true. If the title already exists, return false. You MUST use locate() to implement.

IMPLEMENT RECURSIVELY.

bool remove( const Movie &dataIn ) ;

Remove a Movie object from the BST, with the same title as dataIn (the earnings are ignored). Return true if such a node was successfully removed. Return false if the node is not in the tree, and therefore not removed. You MUST use locate() to implement this method.

IMPLEMENT RECURSIVELY.

bool contains( const Movie &dataIn ) const ;

Return true if there exists a node in the BST with the same title as dataIn (using MovieComparator's operator() method to compare). Return false if the BST does not contain a movie by the same title. (Earnings from dataIn are ignored). You MUST use locate() to implement this method.

IMPLEMENT RECURSIVELY.

bool update( const Movie &dataIn ) ;

Return true if there exists a node in the BST with the same title as dataIn. If so, it updates it with dataIn and returns true. This update should be done by assigning the getData() reference from dataIn (i.e., dataIn is copied into getData() reference). If there does not exist a node with the same title as dataIn return false You MUST use locate() to implement this method.

IMPLEMENT RECURSIVELY.

int size() const ;

Returns the number of nodes in the BST.

void clear() ;

Removes all nodes in the BST, and deallocates the memory of the nodes. Also, sets root to NULL.

ConstIterator cfirst() const ;

Returns an iterator whose curr points to the node in the BST with the smallest key value. If the tree is empty, curr should be NULL.

ConstIterator clast() const ;

Returns an iterator whose curr points to the node in the BST with the largest key value. If the tree is empty, curr should be NULL.

ConstIterator cend() const ;

Returns an iterator with curr set to NULL.

void print( std::ostream & out ) const ;

This function will be provided to you. It prints the structure of the tree.

If there are no nodes in the tree, it prints out "EMPTY LIST" followed by a newline character.

int height() const ;

Returns the height of the tree. The height is defined to be the number of edges from the deepest node to the root. If a tree has one node, then the height is 0. If the tree is empty, the height is -1.

IMPLEMENT RECURSIVELY.

void printInorder() const ;

Using the same format as print() for SortedList, print the nodes of the BST in inorder. If the BST is empty, print "EMPTY LIST". Print this to standard output.

Here's an example:

[PRINT_INORDER]
(1) "Attack the Gas Station"   Earnings: 3000
(2) "Batman"   Earnings: 2000
(3) "Memento"   Earnings: 4000

IMPLEMENT RECURSIVELY.

void printPreorder() const ;

Using the same format as printInorder(), print the nodes of the BST in preorder. If the BST is empty, print "EMPTY LIST". Print this to standard output. Replace [PRINT_INORDER] by [PRINT_PREORDER] when printing.

IMPLEMENT RECURSIVELY.

void printPostorder() const ;

Using the same format as printInorder(), print the nodes of the BST in postorder. If the BST is empty, print "EMPTY LIST". Print this to standard output. Replace [PRINT_INORDER] by [PRINT_POSTORDER] when printing.

IMPLEMENT RECURSIVELY.

The following methods should be implemented, if you feel they are NECESSARY (meaning that the implicit versions of these methods are inadequate).

MovieBstSortedList( const MovieBstSortedList &other ) ;

Copy constructor. Copies the entire BST, maintaining the same structure as other. It can't just contain the same values--the structure must also be the same. If you choose to implement, you must use helper methods: freeMem(), init(), and/or copy().
IMPLEMENT RECURSIVELY.

MovieBstSortedList &operator=( const MovieBstSortedList &other ) ;

Assignment operator. Copies the entire BST, maintaining the same structure as other. It must first deallocate all nodes in the BST (and set root to NULL), before making the copy. If you choose to implement, you must use helper methods: freeMem(), init(), and/or copy().
IMPLEMENT RECURSIVELY.

~MovieBstSortedList();

Destructor. Deallocates all nodes in BST. If you choose to implement, you must use helper methods: freeMem(), init(), and/or copy().
IMPLEMENT RECURSIVELY.

Private Methods

You will need to implement the following private method:

bool locate( const Movie &dataIn, MovieBstSortedList::Node * & curr, MovieBstSortedList::Node * & parent ) const ;

Given dataIn, it will set curr to the node with dataIn as its value and parent to curr's parent, if such a node exists. If it does, it returns true.
Hint: you should set the parent parameter to "follow" curr just like you set prev to "follow" curr when doing locate() in a singly linked list.
If the node with the title in dataIn does not exist in the BST, curr is set to the "parent" of the node (don't confuse this with the parameter, parent), i.e., the node in the BST that will become the parent of the newly added node, given that a new node containing dataIn is added to the BST. The parameter parent is still set to curr's parent. Return false in this case.
Precondition: Prior to calling the method, curr is initialized to the root of the subtree which you wish to do locate() and parent is initialized to NULL.
(3/21) Use MovieComparator objects to compare Movies in the Nodes, as you did in Project 2.
(3/21) Second option. Instead of implementing as described above, you can make curr point to the node containing dataIn if it exists in the BST, or NULL if it does not. parent will the point to the parent of curr if curr is not NULL, or to the node just before curr fell off the tree.
The second option is easier to implement.
IMPLEMENT RECURSIVELY.

If you do choose to implement the copy constructor, assignment operator, and destructor, you need to implement the following methods and use them appropriately.

void init() ;

Set root to NULL.

void copy( const MovieBstSortedList & other ) ;

Copies the structure of other, allocate the same number of nodes as other.
Precondition: root == NULL.
IMPLEMENT RECURSIVELY.

void freeMem() ;

Deallocates nodes in BST
IMPLEMENT RECURSIVELY.

You may add other private methods.

MovieBstSortedList::Node

This is a private, nested class of MovieBstSortedList.

Data Members

Declaration	Description
Movie data	Stores a movie object
*Node left**	Points to left child
*Node right**	Points to right child
*Node pred**	Points to predecessor (node with next smallest value)
*Node succ**	Points to successor (node with next largest value)

DO NOT add a parent pointer. This will force you to use recursion to process the tree.

Public Methods

Node( const Movie &movieIn = Movie() ) ;

Default constructor.

Node * & getLeft() ; const Node * getLeft() const ;

Returns left. Notice this returns a reference pointer and a const pointer respectively.

Node * & getRight() ; const Node * getRight() const ;

Returns right. Notice this returns a reference pointer and a const pointer respectively.

Node * & getPred() ; const Node * getPred() const ;

Returns pred. Notice this returns a reference pointer and a const pointer respectively.

Node * & getSucc() ; const Node * getSucc() const ;

Returns succ. Notice this returns a reference pointer and a const pointer respectively.

Movie & getData() ; const Movie & getData() const ;

Returns data. Notice this returns a reference and a const pointer respectively. (Signature corrected on 3/20).
bool isLeaf() const ;

Returns true if the node is a leaf. Returns false, otherwise.

Notice there are NO set methods. That's because the get methods return references. You can therefore set nodes as follows:

   Node * newNode = new Node( movieIn ) ;
   curr->getLeft() = newNode ;  // instead of curr->setLeft( newNode )

MovieBstSortedList::ConstIterator

Data Members

Declaration	Description
*Node curr**	Points to a Node

Public Methods

ConstIterator( Node *currIn = NULL ) ;

Sets curr to currIn

const Movie *operator->() const ;

Returns pointer to Movie object stored inside Node pointed to by curr.

const Movie &operator*() const ;

Returns a reference to Movie object stored inside Node pointed to by curr.

ConstIterator &operator++(); ConstIterator operator++( int );

Pre-increment operator and post-increment operator, respectively. The preincrement operator move curr to its successor, and returns *this. The postincrement operator creates a temp ConstIterator object, which is a copy of *this, then moves curr to its successor, and returns temp, which still has its curr pointing to the original Node prior to calling this method.

ConstIterator &operator--(); ConstIterator operator--( int );

Pre-decrement operator and post-decrement operator, respectively. The pre-decrement operator move curr to its predecessor, and returns *this. The post-decrement operator creates a temp ConstIterator object, which is a copy of *this, then moves curr to its predecessor, and returns temp, which still has its curr pointing to the original Node prior to calling this method.

bool operator==( const ConstIterator &other ) const ;

Returns true if curr and other.curr point to the same Node (i.e., both store the same address). Returns false otherwise.

bool operator!=( const ConstIterator &other ) const ;

Returns false if curr and other.curr point to the same Node (i.e., both store the same address). Returns true otherwise.

See the class syllabus for policies concerning email
Last Modified: Wed Mar 13 20:20:09 EST 2002

Web Accessibility