Assignment 8: Binary Search Tree

Implement the abstract data type Binary Search Tree by writing a unit called BinSTree using the following types:

    Order = string;   { either 'pre', 'post', or 'in' }
    Status = record
                   size, height: integer;
                   avgLen: real;
             end;

    KeyType    = Integer;
    StdElement = Record
                       key: KeyType;
                       value: String;
                  end;     
    NodePointer = ^TreeNode;
    TreeNode = Record
                     left : NodePointer;
                     data : StdElement;
                     right : NodePointer;
               end;
    BinarySearchTree = Record
                       root : NodePointer;
                       current : NodePointer;
                 end;

Your unit should implement the following functions and procedures:

procedure Traverse(BST: BinarySearchTree; ord: Order);
{ PRE:  the tree is not empty }
{ POST: Traverses the tree in the indicated order and prints }
{       out each node it encounters                          }
procedure Insert(var BST: BinarySearchTree; el: StdElement; var success: boolean);
{ PRE:  the tree is not full
{ POST: If a node with the given key value does not exist,   }
{       inserts a node with data el into the tree at the     }
{       appropriate position, sets the current node to the   }
{       new node, and sets Success to true. Otherwise, sets  }
{       Success to false.                                    }
procedure Delete(var BST: BinarySearchTree; key: KeyType; var success: boolean);
{ PRE:  The tree is not empty                                }
{ POST: If node with given key value exits, it is deleted    }
{       and success is set to true. The current element is   }
{       set to the Root of the tree. Otherwise, success is   }
{       false.                                               }
procedure Retrieve(BST: BinarySearchTree; var el: StdElement);
{ PRE:  the tree is not empty                                }
{ POST: Retrieves data from corrent node and stores it in el }
procedure Find(var BST: BinarySearchTree; key: KeyType; var Success: boolean);
{ PRE:  none                                                 }
{ POST: Finds a node with the corresponding key value, if    }
{       possible, and sets current to that node.             }
function IsFull(BST: BinarySearchTree): boolean;
{ PRE:  tree is a valid tree                                 }
{ POST: Returns true if there is no more room to insert a    }
{       new node into the tree.                              }
function IsEmpty(BST: BinarySearchTree): boolean;
{ PRE:  tree is a valid tree                                 }
{ POST: Returns true if the tree is currently empty          }
procedure MakeEmptyTree(var BST: BinarySearchTree);
{ PRE:  none                                                 }
{ POST: Creates an valid, empty tree                         }
procedure Characters(BST: BinarySearchTree; var ST: Status);
{ PRE:  tree is a valid tree                                 }
{ POST: Shows some characteristics of the tree               }
{ ***********************************************************}

To help with the complicated Delete routine, click here to see my version of it. You should be able to use that routine in your unit without changes.

To help in testing your unit, I wrote a main program to test your unit BinSTree. You can also download that one and use it to test your unit by clicking here, but you need to add the two routines

	Procedure WriteStdElement(el: StdElement)
	Procedure ReadStdElement(var el: StdElement)

in the interface and implementation part of your unit. Also, you need to implement the Characters routine as well, which is optional for this assignment.

(bgw)