Question: Add printRang method to BST.java that, given a low... Add printRang me

Question

Question: Add printRang method to BST.java that, given a low...

Add printRang method to BST.java that, given a low key value, and high key value, print all records in a sorted order whose values fall between the two given keys. (Both low key and high key do not have to be a key on the list).

BST.java

import java.lang.Comparable;

/** Binary Search Tree implementation for Dictionary ADT */
class BST<Key extends Comparable<? super Key>, E>
implements Dictionary<Key, E> {
private BSTNode<Key,E> root; // Root of the BST
int nodecount; // Number of nodes in the BST

/** Constructor */
BST() { root = null; nodecount = 0; }

/** Reinitialize tree */
public void clear() { root = null; nodecount = 0; }

/** Insert a record into the tree.
@param k Key value of the record.
@param e The record to insert. */
public void insert(Key k, E e) {
root = inserthelp(root, k, e);
nodecount++;
}

// Return root

public BSTNode getRoot()
{
return root;
}

/** Remove a record from the tree.
@param k Key value of record to remove.
@return The record removed, null if there is none. */

public E remove(Key k) {
E temp = findhelp(root, k); // First find it
if (temp != null) {
root = removehelp(root, k); // Now remove it
nodecount--;
}
return temp;
}

/** Remove and return the root node from the dictionary.
@return The record removed, null if tree is empty. */
public E removeAny() {
if (root == null) return null;
E temp = root.element();
root = removehelp(root, root.key());
nodecount--;
return temp;
}

/** @return Record with key value k, null if none exist.
@param k The key value to find. */
public E find(Key k) { return findhelp(root, k); }

/** @return The number of records in the dictionary. */
public int size() { return nodecount; }
  
private E findhelp(BSTNode<Key,E> rt, Key k) {
if (rt == null) return null;
if (rt.key().compareTo(k) > 0)
return findhelp(rt.left(), k);
else if (rt.key().compareTo(k) == 0) return rt.element();
else return findhelp(rt.right(), k);
}
/** @return The current subtree, modified to contain
the new item */
private BSTNode<Key,E> inserthelp(BSTNode<Key,E> rt,
Key k, E e) {
if (rt == null) return new BSTNode<Key,E>(k, e);
if (rt.key().compareTo(k) > 0)
rt.setLeft(inserthelp(rt.left(), k, e));
else
rt.setRight(inserthelp(rt.right(), k, e));
return rt;
}
/** Remove a node with key value k
@return The tree with the node removed */

private BSTNode<Key,E> removehelp(BSTNode<Key,E> rt,Key k) {
if (rt == null) return null;
if (rt.key().compareTo(k) > 0)
rt.setLeft(removehelp(rt.left(), k));
else if (rt.key().compareTo(k) < 0)
rt.setRight(removehelp(rt.right(), k));
else { // Found it
if (rt.left() == null) return rt.right();
else if (rt.right() == null) return rt.left();
else { // Two children
BSTNode<Key,E> temp = getmin(rt.right());
rt.setElement(temp.element());
rt.setKey(temp.key());
rt.setRight(deletemin(rt.right()));
}
}
return rt;
}

private BSTNode<Key,E> getmin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt;
return getmin(rt.left());
}

private BSTNode<Key,E> deletemin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt.right();
rt.setLeft(deletemin(rt.left()));
return rt;
}
private void printhelp(BSTNode<Key,E> rt) {
if (rt == null) return;
printhelp(rt.left());
printVisit(rt.element());
printhelp(rt.right());
}

private StringBuffer out;

public String toString() {
out = new StringBuffer(400);
printhelp(root);
return out.toString();
}
private void printVisit(E it) {
out.append(it + " ");
}

}

BSTNode.java

class BSTNode<Key, E> implements BinNode<E> {
private Key key; // Key for this node
private E element; // Element for this node
private BSTNode<Key,E> left; // Pointer to left child
private BSTNode<Key,E> right; // Pointer to right child

/** Constructors */
public BSTNode() {left = right = null; }
public BSTNode(Key k, E val)
{ left = right = null; key = k; element = val; }
public BSTNode(Key k, E val,
BSTNode<Key,E> l, BSTNode<Key,E> r)
{ left = l; right = r; key = k; element = val; }

/** Get and set the key value */
public Key key() { return key; }
public void setKey(Key k) { key = k; }

/** Get and set the element value */
public E element() { return element; }
public void setElement(E v) { element = v; }

/** Get and set the left child */
public BSTNode<Key,E> left() { return left; }
public void setLeft(BSTNode<Key,E> p) { left = p; }

/** Get and set the right child */
public BSTNode<Key,E> right() { return right; }
public void setRight(BSTNode<Key,E> p) { right = p; }

/** @return True if a leaf node, false otherwise */
public boolean isLeaf()
{ return (left == null) && (right == null); }
}

BinNode.java

/** ADT for binary tree nodes */
public interface BinNode<E> {
/** Get and set the element value */
public E element();
public void setElement(E v);

/** @return The left child */
public BinNode<E> left();

/** @return The right child */
public BinNode<E> right();

/** @return True if a leaf node, false otherwise */
public boolean isLeaf();
}

Explanation / Answer

   //====================== Please add these methos to your BST Class ================//

    public void printRange(T ater, T before){
        System.out.print("| ");
        printRange(root,ater,before);
    }
  
    @SuppressWarnings("unused")
   private void printRange(Node tree,T ater, T before){
       printPreOrder(tree.left);
       @SuppressWarnings("unchecked")
       Comparable<T> comparableAfter = (Comparable<T>)ater;
       @SuppressWarnings("unchecked")
       Comparable<T> comparableBefore = (Comparable<T>)before;
       if((comparableAfter.compareTo(tree.data)>0) && (comparableBefore.compareTo(tree.data)<0))
           System.out.print(tree.data.toString()+" | ");
      
        printPreOrder(tree.right);
    }

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.