hi i am trying to write this program and i dont know how to start. i will try to post code later, but i need some thing to start with.
thanx
main purpose:
To learn how to develop and use linked data structures.
The Sorted Interface
The sorted interface has the following methods for a data set of ints.
public void clear (); This method will delete all items in the data set.
public int delete (int value); This method will attempt to delete the item in the data set with the given value. If the item exists, the method will return the number of items that it had to examine to find the given item. If the item does not exist, the method will return -1 * the number of items examined.
public int find (int value); This method will attempt to find the item in the data set with the given value. If the item exists, the method will return the number of items that it had to examine to find the given item. If the item does not exist, the method will return -1 * the number of items examined.
public int insert (int value); This method will insert a new item into the data set with the given value. The method will return the number of items that it had to examine to find the location at which the new item should be inserted. Note: you may assume that no duplicate values will ever be inserted into the data set.
public void printAll (); This method will print all items in the data set in ascending order.
The classfile for the interface is given here. The Basic Node To implement the linked data structure, you must use the following Node. This class holds four fields -- one int value and three links.
Node.class
The Linked Data Structure For this program, you must implement the Sorted interface for a "Doubly Linked BST". This structure combines a BST with an extra link that points to the parent of each node (null for the root). The following shows an example:
insert (5) (5)
insert (3) (5) / (3) insert (4) (5) / (3) \ (4) find (4) - current now points to Node "4"
printAncestors () - print the current Node and all of its ancestors -- 4 3 5
Remember, when deleting a Node from a binary search tree, there are four cases: The Node is a leaf -- just delete the Node, and have the parent point to null. The Node has no left child -- delete the Node, and have the parent point to the right child of the deleted Node. The Node has no right child -- delete the Node, and have the parent point to the left child of the deleted Node. The Node has two children -- have the parent point to the largest value in the left sub-tree of the deleted Node -- i.e. this value will replace the deleted Node in the BST. Note: for the doubly linked BST, you may also have to update the parent link.
Previous Topic
