Part (a)
// precondition: the priority queue is not empty
// postcondition: a data value of smallest priority is returned;
// the priority queue is unchanged
public Object peekMin()
{
if (root == null)
throw new NoSuchElementException(); 1
TreeNode t = root;
while(t.getLeft() != null) 2
t = t.getLeft();
return ((Item)t.getValue()).getData(); 3
}
Notes:
- This check is optional because the precondition states
that the queue is not empty.
But, strictly speaking, the precondition here contradicts the
description of the
peekMin method in the
PriorityQueue interface.
- The smallest value in a BST is in its leftmost node.
It is easier to find that node using iterations,
rather than recursion.
- Not
return t.getValue();
You need the cast to Item to call getData .
Part (b)
// postcondition: obj has been added to the subtree rooted at t;
// the resulting subtree is returned
private TreeNode addHelper(Comparable obj, TreeNode t)
{
if (t == null)
return new TreeNode(new Item(obj)); 1
Item item = (Item)t.getValue();
int diff = obj.compareTo(item.getData());
if (diff == 0)
item.incrementCount();
else if (diff < 0)
t.setLeft(addHelper(obj, t.getLeft())); 2
else // if (diff > 0)
t.setRight(addHelper(obj, t.getRight()));
return t;
}
Notes:
- Not
return new TreeNode(obj);
- It is important to not just call
addHelper ,
but also append the tree returned by it to the parent node.
|