Java Reference
In-Depth Information
trees is that operations such as inorder traversal can be implemented without
using recursion or a stack.
Re-implement the BST as a threaded binary tree, and include a non-recursive
version of the preorder traversal
5.3 Implement a city database using a BST to store the database records. Each
database record contains the name of the city (a string of arbitrary length)
and the coordinates of the city expressed as integer x- and y-coordinates.
The BST should be organized by city name. Your database should allow
records to be inserted, deleted by name or coordinate, and searched by name
or coordinate. Another operation that should be supported is to print all
records within a given distance of a specified point. Collect running-time
statistics for each operation. Which operations can be implemented reason-
ably efficiently (i.e., in (log n) time in the average case) using a BST? Can
the database system be made more efficient by using one or more additional
BSTs to organize the records by location?
5.4 Create a binary tree ADT that includes generic traversal methods that take a
visitor, as described in Section 5.2. Write functions
count
and
BSTcheck
of Section 5.2 as visitors to be used with the generic traversal method.
5.5 Implement a priority queue class based on the max-heap class implementa-
tion of Figure 5.19. The following methods should be supported for manip-
ulating the priority queue:
voidenqueue(intObjectID,intpriority);
intdequeue();
voidchangeweight(intObjectID,intnewPriority);
Method
enqueue
inserts a new object into the priority queue with ID num-
ber
ObjectID
and priority
priority
. Method
dequeue
removes the
object with highest priority from the priority queue and returns its object ID.
Method
changeweight
changes the priority of the object with ID number
ObjectID
to be
newPriority
. The type for
E
should be a class that
stores the object ID and the priority for that object. You will need a mech-
anism for finding the position of the desired object within the heap. Use an
array, storing the object with
ObjectID
i in position i. (Be sure in your
testing to keep the
ObjectID
s within the array bounds.) You must also
modify the heap implementation to store the object's position in the auxil-
iary array so that updates to objects in the heap can be updated as well in the
array.
5.6 The Huffman coding tree function
buildHuff
of Figure 5.29 manipulates
a sorted list. This could result in a (n
2
) algorithm, because placing an inter-
mediate Huffman tree on the list could take (n) time. Revise this algorithm
to use a priority queue based on a min-heap instead of a list.
