Previous Section
 < Free Open Study > 
Next Section


8.2 Logical Level

We should be old hands at looking at an ADT from the logical level by now. We know that we need an operation to put an item into the structure (). We need to be able to delete an item from the structure (). We need the usual complement of observer functions (, , , and ). Let's also include a () operation and a () operation.

Traversals are more complicated in a binary search tree. In the List ADTs we have examined so far, we have traversed the structure in only two ways: from front to back or from back to front. In all but the SpecializedList class, we have started at the beginning of the list and continued until we accessed all the items. In fact, there are many ways to traverse the items in a tree. We let the client determine which way to traverse the tree by passing a traversal name as a parameter to the and operations. We discuss traversals in much more detail later in the chapter.

Binary Search Tree Specification

Structure:

The placement of each element in the binary tree must satisfy the binary search property: The value of the key of an element is greater than the value of the key of any element in its left subtree, and less than the value of the key of any element in its right subtree.

Operations (provided by TreeADT):

    • Assumption:

Before any call is made to a tree operation, the tree has been declared and a constructor has been applied.

  • MakeEmpty

Initializes tree to empty state.

    • Postcondition:

Tree exists and is empty.

  • Boolean IsEmpty

Determines whether tree is empty.

    • Postcondition:

Function value = (tree is empty).

  • Boolean IsFull

Determines whether tree is full.

    • Postcondition:

Function value = (tree is full).

  • int LengthIs

Determines the number of elements in tree.

    • Postcondition:

Function value = number of elements in tree.

  • RetrieveItem(ItemType& item. Boolean& found)

Retrieves item whose key matches item's key (if present).

    • Postcondition:

Key member of item is initialized.

If there is an element someItem whose key matches item's key, then found = true and item is a copy of someItem; otherwise, found = false and item is unchanged. Tree is unchanged.

  • InsertItem(ItemType item)

Adds item to tree.

Tree is not full. item is not in tree.

item is in tree. Binary search property is maintained.

  • DeleteItem(ItemType item)

Deletes the element whose key matches item's key.

Key member of item is initialized. One and only one element in tree has a key matching item's key.

No element in tree has a key matching item's key.

  • Print(ofstream& outFile)

Prints the values in the tree in ascending key order on outFile.

outFile has been opened for writing.

Items in the tree have been printed in ascending key order. outFile is still open.

  • ResetTree(OrderType order)

Initializes current position for an iteration through the tree in OrderType order.

Current position is prior to root of tree.

  • GetNextItem(ItemType& item, OrderType order, Boolean& finished)

Gets the next element in tree.

Current position is defined. Element at current position is not last in tree.

Current position is one position beyond current position at entry to GetNextItem. finished = (current position is last in tree). item is a copy of element at current position.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)