Program #5, Binary Search Tree Iterator

Provide an iterator for the Binary Search Tree class

Due: Wednesday, December 9, 1:30 pm

Last modified: 6Dec98 by R.Levow

Update: Corrected algorithm for begin and code for bitest.cc

Create a derived class BSTWithIter from the class BST defined in chapter 10 of the text in the files BST.h and BST.cc on pages 487 - 495. (A sample Data.h file is also provided.) To do this, extend the BST class by adding a contained class, iterator, and the following methods. Incomplete implementations are found in BSTiter.h and BSTiter.cc. Use the STL stack template class for the stack in your implementation. Your assignment is to complete these.

New methods in class BSTWithIter

begin()

returns an iterator pointing to the first element of the BST if it is not empty; else has the same value as end()

end()

returns a iterator with a value that represents the position after the last element of the BST. The pointer field of the iterator should be zero.

Methods in class iterator, a class contained in BSTWithIter

default constructor

creates an iterator initialized to end()

copy constructor
operator =

assignment operator for iterator; returns reference to iterator

operator *

unary operator to dereference the iterator for use as an lvalue; return a const reference to the contents of the current BST node

operator ++

increment the iterator to point to the next node; both pre- and postincrement versions; return a copy of the iterator
the pre-increment version has no parameters
the post-increment version has one parameter of type int; the int parameter is ignored

operator ==

compare two iterators for equality
note that both the left and right operands must be const

operator !=

compare two iterators for inequality
note that both the left and right operands must be const

The code will be structured like this.
    class BSTWithIter ...
    {
        class iterator
        {
            friend class BSTWithIter; // so begin() can access Cur.
          public:
            // declarations for iterator methods
          private:
            ptrType Cur;
            stack <ptrType> S;
        };
        // new methods for BSTWI that use iterator
        // rest of BSTWI...
    };

Note on scope modifiers in C++ class implementation files

Components of classes are recognized by the C++ compiler in one of two ways. The most common is that the component is accessed as a field of an object with one of the selection operators, '.' or '->'. The other is by use of the scope modifier. Whenever you reference a method other than a constructor outside a class declaration, you must use one of these techniques. Recall that the scope of a variable is the block, delimited by curly brackets, '{' and '}'. Normally identifiers can be used only in the scope in which they are declared. The scope modifier allows names to be used outside their normal scope. When it is applied to a declaration, it acts throughout the declaration. When it is applied to an identifier elsewhere, it normally applies only to the name it qualifies. Here's are a couple of examples.

BSTWithIter::iterator BSTWithIter::end() const

{

iterator newIter;

// default has Cur == 0

return newIter;

}

I need to qualify both iterator and begin() on the first line since both are members of BSTWithIter. Once inside the declaration, I can refer to iterator and RootPtr() directly, because I am in the extended scope of BSTWithIter. On the other hand, I refer to Cur by applying it to an object of type iterator.

BSTWithIter::iterator::iterator(const iterator& Iter)

:S(Iter.S), Cur(Iter.Cur)

{}

Here, iterator() is a function in class iterator in class BSTWithIter so I need the double qualification. BSTWithIter:: tells the compiler where to find the class iterator and BSTWithIter::iterator tells it where to find the method iterator().

Implementing the iterator class

The iterator must be able to traverse the BST without the benefit of a recursive routine. The solution is based on the nonrecursive traversal on page 469 of the text. The routine must be modified so that it can be called to return the next node each time it is called. The code will be split between two routines, begin() and operator++. Begin() takes us to the smallest node to start the traversal and operator++ takes us to the next node. We'll use NULL for end(). Using the same notation as in the text, two class variables are required

Cur, the current node
S, the stack of node pointers

Here's the pseudocode for begin() to construct an iterator pointing to the first node to visit. Note that Cur and S belong to the iterator. Code for the stack operations is in the style of the text and must be revised to the corresponding calls for the STL stack class, without the Success parameter and with method names in lowercase.

Create a default iterator

Iter

set Iter.Cur=RootPtr()

if (Iter.Cur == 0) // empty tree, quit now

return Iter

// find smallest (leftmost) entry

while (Iter.Cur != 0) {

Iter.S.Push(Iter.Cur, Success)

Iter.Cur = Iter.Cur->LChildPtr

}

Iter.S.GetStackTop(Iter.Cur, Success) // retrieve node from stack

Iter.S.Pop(Success)

return Iter

Operator++ must update the iterator on which it is invoked. The algorithm is essentially that of the nonrecursive traversal in the text except that it starts by going to the right child and ends where the text algorithm has visit. Here we are working in the iterator, so the Iter prefix of begin() is not needed.

if (Cur == 0) // already at end

return

Cur = Cur->RChildPtr

while (true) { // we'll use break to exit the loop

if (Cur != 0) {

S.Push(Cur, Success)

Cur = Cur->LChildPtr

}

else { // backtrack

if (!S.StackIsEmpty()) {

S.GetStackTop(Cur, Success)

S.Pop(Success)

break

}

else // stack is empty; done

{

Cur = 0

break

}

return

In implementing the assignment operator, remember that every class normally has an assignment operator. In particular, stack<> has an assignment so you can code S = RHS.S to clear and copy the stack portion of the iterator.

Note that Cur points to a tree node so when you dereference it with operator*, you need to return a reference to the itemClass component of the node.

Submitting your project

The program is due at the specified time on the due date. You must

Turn in a printed copy of your source code.
Turn in a printed record of the execution of the test program, bitest.cc , with data item declaration file, Data.h
Electronically submit the files BSTiter.h and BSTiter.cc using the hwroy program.