An Alternate Implementation of the Binary-Search-Tree Data Type

This project illustrates that the binary-search-tree data type has more than one implementation. You can also use the technique described below to save a binary search tree (in fact, any binary tree) to disk so that it can be subsequently retrieved with its original structure.

Develop an array-based implementation of the binary-search-tree data type. Your class, Binary SearchTreeArray, will have the same method specifications as the BinarySearchTree class but will use indexes to simulate the parent, left, and right links. For example, the fields in your embedded Entry class might have:

E element;

int parent,

left,

right;

Similarly, the BinarySearchTreeArray class might have the following three fields:

Entry [ ] tree;

int root,

size;

The root Entry object is stored in tree [0], and a null reference is indicated by the index 1. For example, suppose we create a binary search tree by entering the String objects dog, turtle, cat, ferret. The tree would be as follows:

The array representation, with the elements stored in the order in which they are entered, is

The method definitions are very similar to those in the BinarySearchTree class, except that an expression such as