“C” Option (WARNING: Only the FindCustomerRecursive method is recursive!):

You may use Ada, C++, assembly or Java.  If you desire to use another language ask for permission.  Implement the following package using constructs in the language of your choice.  Please make all data structures private types in your implementation language. I have recommended but not required "limited private" in Ada.  This is a special feature of Ada developed specifically for high security situations encountered by the military, NSA, Homeland Security, and other security conscience agencies/applications.  As an analogy, it allows you to provide a "key" to a user.  The user has complete functional use of the key but the language translator enforces the abstraction the user may not make a copy of the key.  This level of security in programming languages is very rare and not in any of the previously listed languages other than Ada.

package BinarySearchTree is

type String10 is new String(1..10);  // You may use an enumeration type if desired.

— Points to a node in a binary search tree.

type BinarySearchTreePoint is limited private;  — or type BinarySearchTreePoint is private;

— This procedure inserts a node (customer) into the tree in search tree order. If a customer with

— duplicate name already customer exist, the new customer should be inserted so they would

— appear “after” the older customer when the tree is traversed in inorder.

— The tree must be threaded in “inorder.” The search to locate the position for the new

— record must be iterative!

procedure InsertBinarySearchTree(Root:  in out BinarySearchTreePoint;

custName: in String10; custPhone: String10 );

— This procedure locates a customer using a binary search.  A pointer is returned to the

— customer record if they exist, otherwise a Null pointer is returned (in CustomerPoint).

— The search must be implemented iteratively.

procedure FindCustomerIterative(Root: in BinarySearchTreePoint;

CustomerName:  in String10;

CustomerPoint:  out BinarySearchTreePoint);

— This procedure locates a customer using a binary search.  A pointer is returned to the

— customer record if they exist, otherwise a Null pointer is returned (in CustomerPoint).

— The search must be implemented recursively.

procedure FindCustomerRecursive(Root: in BinarySearchTreePoint;

CustomerName:  in String10;

CustomerPoint:  out BinarySearchTreePoint);

— This function returns the address of the next node in “inorder” taking advantage of threads.

— The user may enter the  tree at any random location.  This is sometimes called an iteration

— function or iterater (no recursion).

function InOrderSuccessor(TreePoint: in BinarySearchTreePoint)

return BinarySearchTreePoint;

— Access functions to return customer names and phone numbers.

function CustomerName(TreePoint: in BinarySearchTreePoint) return String10;

function CustomerPhone(TreePoint: in BinarySearchTreePoint) return String10;

private

type Customer is

record

Name:  String10;

PhoneNumber: String10;

end record;

type Node;

type BinarySearchTreePoint is access Node;

type Node is

record

Llink, Rlink:  BinarySearchTreePoint;

Ltag, Rtag:  Boolean; — True indicates pointer to lower level, False a thread.

Info:  Customer;

end record;

end BinarySearchTree;

You may amend the package specification if required but management would really prefer the actual tree remain limited private (the tree should only be accessible via member functions by users of the package).  C++ and Java support the “private” concept but do not support the concept of “limited private.”  The runtime system assures the user data of type limited private may not be copied by a user of the system.  This is a very important security feature for implementing high security software.

The implementation of the above tree constitutes an ple of a abstract data type (ADT). The tree search to locate the position in the tree where a new node is to be inserted must be iterative in procedure InsertBinarySearchTree(Root:  in out BinarySearchTreePoint;  custName: in String10; custPhone: String10 );. You may not use recursion to implement any method other than FindCustiomerRecursive and PostOrderRecursive..

Process the following transactions in the indicated order:

1) Insert the following data in the tree using InsertBinarySearchTree: Nkwantal, 295-1492;  Ortiz, 291-1864;  Glosson, 295-1601;  Yang, 293-6122;  Parker, 295-1882;  Kresta,  291-7890;  Rock, 294-8075; Bell, 584-3622.

2) Find Kresta and print the phone number using FindCustomerIterative.

3) Find Kresta and print the phone number using FindCustomerRecursive.

4) Find Acevedo and print the phone number using FindCustomerIterative.

5) Find Acevedo and print the phone number using FindCustomerRecursive.

6) Starting with Parker, traverse the entire tree in inorder back to Parker printing the name field of each node encountered. (you should be able to do this starting at any node, i.e., find Parker using a binary search then traverse the tree from this point in inorder).

7) Insert Devin, 294-1568; Morah, 294-1882; and Zembo 295-6622.

8) Traverse the tree in inorder starting at the root using the method InOrderSuccessor.  Print the name and phone number of each node as it is encountered.

“B” Option:

In addition to the “C” option, add a method to delete a random item from the tree leaving a binary search tree, a method ReverseInOrder, and a method preorder as described below.

DeleteRandomNode(DeletePoint: in BinarySearchTreePoint): This procedure deletes a random node from the tree.  The resulting tree is a binary search tree.  Note that DeletePoint = Root, DeletePoint = P.LLink or DeletePoint = P.Rlink.  Management would be impressed if you minimize the number of nodes that must be ined to determine which of the above is true.  Your procedure should contain comments explaining your strategy.  You may add additional parameters if desired.

The procedure ReverseInOrder(treePoint: in BinarySearchTreePoint); is defined as:

Traverse the right subtree.

Visit the node (print its contents)

Traverse the left subtree.

You must implement ReverseInOrder recursively.

Process the following transactions after processing the “C” option transactions in the specified order:

7) Delete: Kresta, Najar, and Glosson.   (Note they may not be in the tree.) Locate the nodes to be deleted using a binary search.

8) Insert: Novak, 294-1666; and Gonzales, 295-1882.

Traverse the tree in inorder starting at the root using the method InOrderSuccessor.  Print the name and phone number of each node as it is encountered.

Traverse the tree using ReverseInOrder starting at the root.

Traverse the tree in preorder printing the name field using an iterative routine taking advantage of the threads.

Remember, a good programmer would not allow hemorrhaging of either blood or gray matter (memory) to occur in their programs.

Specific Grading Checks all Options:

InsertBinarySearchTree(–) is iterative.

FindCustomerIterative(–) is a binary search accomplished iteratively.

FindCustomerRecursive(–) is a binary search accomplished recursively.

InOrderSuccesor(–) is iterative.

PreOrder(–) is recursive.

PostOrderIterative(–) is iterative.

PostOrderRecursive(–) is recursive.

ReverseInOrder(–) is recursive.