Universidad Carlos III de Madrid

A BSTree tree has a reference to its root node.

A BSNode has the key's comparator, the data to be stored and the nodes references representing both left and right subtrees.

Define attributes for BSTree and BSNode classes, according to the structure shown at the previous figure.

Provide a constructor, with no parameters, for BSTree class that initializes an empty tree (that is, the one with the root's node set to null). Provide also a constructor for BSNode auxiliary class. This constructor should receive both the node's search key and the data to be stored as parameters. Left and right children subtrees will be initialized to null. For each class, provide necessary get and set access methods.

Program a boolean isEmpty() method that tests whether the tree is empty or not.

Program a public Object search(Comparable key) method that returns the object that is stored at the node which associated key matches with the one passed in the parameter.

Program a public void insert(Comparable key, Object info) method that enters a new data in the tree. To do so, it must create a new node at the correct place, which should contain both the key and the object that are passed in as parameters. If the tree already contains a node with that key, it must overwrite the data stored at the object.

Program a void printPreOrder() method that prints to console all tree's entries when traversing it in preorder.

Program a DirectoryEntry class that stores all data associated with an entry: Name, Surname, Address, Phone, Mobile and Email

Program a Directory class that uses a binary search tree to store data from an electronic directory. The search key that is used to order the directory's data is the whole name according to the following format: Surname, Name.

Add a void insert(DirectoryEntry data) method to Directory class that enters into the directory all data passed in as parameters. Remember that you must concatenate both Surname and Name to generate the associated search key. Add a void insert() method that enters a new entry into the directory with data input by keyboard.

Add a DirectoryEntry search(String fullName) method to Directory that permits to obtain data from a certain entry from the full name (Surname and Name).

Program a void printInOrder() method that prints the contents of the directory to console, in alphabetical order (inorder traversal).

Build a NTree class based on the previous recursive definition. Implement a constructor without parameters that initializes an empty tree. Program an additional constructor that receives just a single parameter, the information (Object class type) to be stored in the root node of the tree.

Build a NNode class based on the previous recursive definition, which encapsulates the information to be stored in the node as well as a Vector with the references to the children. Implement a constructor that receives just a single parameter, the information to be stored, (Object class type). Program also the corresponding accessor methods (get and set).

Program the size method that returns the number of nodes in the tree.

Program the preorder method that prints the elements in the tree applying a preorder traversal.

Some auxiliary methods will be also needed for building and traversing the tree, such as int getNumberOfChildren(), void addChild(NNode child), void addChildAt(int index, NNode child), NNode getChildAt(int index), and other.

Implement a BinaryHeap class that represents a binary heap, as previously defined, using an inner Vector to store the data. Define all attributes of the class and implement a constructor, with no parameters, that initializes an empty heap. Observe that each heap's element stores two pieces of information: the priority and the object. Program a PriorityQueueElement auxiliary class that encapsulates all of this information.

Add to BinaryHeap class the following methods: int size(); that returns the number of elements and boolean isEmpty(); that indicates if the tree is empty or not.

Add to BinaryHeap class the void insert(int priority, Object info); method that stores a new element at the heap keeping the structural properties and the heap order.

To insert an element X at the heap, first of all we have to add a new node to the tree. This node must be added at the end of the structure to guarantee that it remains complete. Once the new element has been added at that final position, the property of heap order must be maintained. To do so, we must test whether the data of the new child node is higher than its father. In such case, the heap is still ordered an the process ends. But, on the other hand, if the new data is lower than the data stored at the father's node, we must swap them and repeat the process of comparison until we reach a node that can be both the root or other node that fulfills the heap principle (father lower or equal than child).

Add to BinaryHeap class a Object extract(); method that returns the stored object at the root node, that is, the one with the highest priority, and reorganize the heap so that it maintains its structure and order. Remember that higher priorities correspond to lower values, being 1 the highest priority.

Return the searched object is trivial because heaps's order property guarantee that it is located at the root node.

The main difficulty of this method consists of the subsequent reorganization of the heap's structure because the root node can have two childs. That's why it is neccesary to make the opposite process of "refloating" when inserting an element to "sink" the generated "hole" until the correct position.

To occupy the empty position, we must select the least of the two child nodes of the node (if they exist). The child node swaps with the father so that the "hole" goes down one level. The process repeats until we reach a "leaf" node (that without children)

The tree still must be complete, so the last element passes to the position in which the "hole" has remained.

Add to BinaryHeap class the print() method that prints out to console all stored elements with their priority. Elements must be presented in order, according to their position at the heap.

A BBNode node contains the comparison's key, the data to be stored an both references to the left and right subtrees.

Modify the definition of BinaryHeap class so that it implementS the PriorityQueue interface.

interface PriorityQueue {

  static int MAX_PRIORITY = 1;

  /**
   * Insert the indicated object in the correct position in the queue, depending
   * on its priority. Priority is declared with a natural number (> 0). The
   * bigger is this number, the lower is the element priority associated with
   * the number. The value 1 corresponds to elements with maximum priority.
   */
  void insert(int priority, Object info);

  /**
   * Extract the object with highest priority out of the queue (that is, the one
   * with the minimum priority) In case that several elements have the same high
   * priority, the first introduced (FIFO) will be returned. If queue is empty,
   * null is returned.
   */
  Object extract();

  /**
   * Returns the number of elements in the queue.
   */
  int size();

  /**
   * Indicates if the queue is empty.
   */
  boolean isEmpty();

}

				

Using the BinaryHeap class developed at the previous sections, complete the PrintQueueManager class that manage the printing works by the use of a priority queue.

public class PrintQueueManager {

  PriorityQueue queue;

  /**
   * Initialize the manager, empty.
   */
  public PrintQueueManager() {
    // to be completed by the student
  }

  /**
   * Adds a new work to print, with the indicated priority. *
   */
  public void print(int priority, String file) {
    // to be completed by the student

  }

  /**
   * Processes (prints out of the printer) the first work of the queue, with the
   * highest priority, reorganizing the data structure.
   */
  public void process() {
    // to be completed by the student
  }
}

				

Observe that the type of the attribute that stores the queue is declared as a PriorityQueue interface. The reason is to make the code as generic as possible so that, in the future, we can change the implementation of the queue with a heap with minimal impact. We recommend you this philosophy for code development, trying to use wherever it is possible the type defined by the interface and avoiding (remember, wherever it is possible) to use references to the class that implements it.