Homework SourseObjective Provide range search function for Dictionary Add p
Objective: Provide range search function for Dictionary
Add printRang method to BST.java that, given a low key value, and high key value, print all records in sorted order whose values fall between the two given keys.
Binary (Search) Trees Traversal
Inorder traversal:
With inorder traversal, the left subtree of current node is visit first, then the current node then finally the right subtree of current node. The inorder traversal displays all the nodes in a BST in increase order.
Postorder traversal:
With postorder traversal, the left subtree is visit first, then the right subtree and finally the current node itself.
Preorder Traversal:
With preorder traversal, the current node is visited first, then the left subtree and finally the right subtree.
Provided Code:
/** Source code example for \"A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)\"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
/** ADT for binary tree nodes */
public interface BinNode {
/** Get and set the element value */
public E element();
public void setElement(E v);
/** @return The left child */
public BinNode left();
/** @return The right child */
public BinNode right();
/** @return True if a leaf node, false otherwise */
public boolean isLeaf();
}
//********************************************************************
// StringTree.java
//
//********************************************************************
import java.util.*;
public class StringTree
{
private Node root;
//----------------------------------------------------------------
// Creates an initially empty tree.
//----------------------------------------------------------------
public StringTree()
{
root = null;
}
//----------------------------------------------------------------
// Adds a string to the tree.
//----------------------------------------------------------------
public void addString (String str)
{
root = addStringToSubTree(str, root);
}
//----------------------------------------------------------------
// Adds a string to the subtree with the given root node
//----------------------------------------------------------------
private Node addStringToSubTree (String str, Node node)
{
Node result = node;
if (node == null)
result = new Node(str);
// If the new string comes before the string in the node, add
// the new string to the left child. Otherwise, add it to the
// right child.
else
if (str.compareTo(node.value) < 0)
node.left = addStringToSubTree(str, node.left);
else
node.right = addStringToSubTree(str, node.right);
return result;
}
//----------------------------------------------------------------
// Prints the result of a depth-first traversal of the tree using
// recursion.
//----------------------------------------------------------------
public void traverseWithRecursion()
{
traverseWithRecursion(root);
}
//----------------------------------------------------------------
// Prints the elements in the specified tree using recursion.
//----------------------------------------------------------------
private void traverseWithRecursion (Node node)
{
if (node != null)
{
traverseWithRecursion (node.left);
System.out.print (node.value+\" \");
traverseWithRecursion (node.right);
}
}
}
//********************************************************************
// Node for a binary tree of Strings.
//********************************************************************
class Node
{
public String value;
public Node left;
public Node right;
public Node (String value)
{
this.value = value;
this.left = left;
this.right = right;
}
}
/** Source code example for \"A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)\"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
/** The Dictionary abstract class. */
public interface Dictionary {
/** Reinitialize dictionary */
public void clear();
/** Insert a record
@param k The key for the record being inserted.
@param e The record being inserted. */
public void insert(Key k, E e);
/** Remove and return a record.
@param k The key of the record to be removed.
@return A maching record. If multiple records match
\"k\", remove an arbitrary one. Return null if no record
with key \"k\" exists. */
public E remove(Key k);
/** Remove and return an arbitrary record from dictionary.
@return the record removed, or null if none exists. */
public E removeAny();
/** @return A record matching \"k\" (null if none exists).
If multiple records match, return an arbitrary one.
@param k The key of the record to find */
public E find(Key k);
/** @return The number of records in the dictionary. */
public int size();
}
/** Source code example for \"A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)\"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
/** Binary tree node implementation: Pointers to children
@param E The data element
@param Key The associated key for the record */
class BSTNode implements BinNode {
private Key key; // Key for this node
private E element; // Element for this node
private BSTNode left; // Pointer to left child
private BSTNode 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 l, BSTNode 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 left() { return left; }
public void setLeft(BSTNode p) { left = p; }
/** Get and set the right child */
public BSTNode right() { return right; }
public void setRight(BSTNode p) { right = p; }
/** @return True if a leaf node, false otherwise */
public boolean isLeaf()
{ return (left == null) && (right == null); }
}
Text file:
CT16C1288B
DT14B1225F
MI15B1250A
MI15B1251A
HO03N1095A
HY07D1095BQ
KI04D2593C
DG12A1240AQ
HY03G2593BQ
TO30A1310A
HO03N1095AQ
HO01H1351C
HO01H1350C
FT18A1288B
LR15A1000A
BM12E1000A
VW02B3113A
NI23H1230AQ
LX03D2503A
LX03D2502A
LX03D2502A
VW22A3113B
VW22B3113A
Solution
/**
* Function Description: This method prints all of the data that is between the specified
* low_keyning and high_key keys (inclusive)
*
* Function Arguments:
* @arg node the root of the tree
* @arg low_key the low_keyning key to print from
* @arg high_key the high_keying key to print from
* @arg print_data the printwriter to print to
* Return value: None
* Assumption: low_key < high_key
**/
private void printRang(BSTNode node, Comparable low_key, Comparable high_key,
java.io.PrintWriter print_data);
/*
Function Implementation start
*/
private void printRang(BSTNode node, Comparable low_key, Comparable high_key,
java.io.PrintWriter print_data) {
// if there is no node or low_key node is greater than high_key node,
// simply return
if(node == null || (low_key.compareTo(high_key) > 0)) {
return;
}
// If the current node is greater than the low_key node, check it\'s
// left subtree for values to print
if(low_key.compareTo(node.key) < 0)
printRang(node.left,low_key,high_key,print_data);
// If the node is between the low_key and high_key node and or equal
// to one or both, print this node
if(node.key.compareTo(low_key) >= 0 && node.key.compareTo(high_key) <= 0)
print_data.println(node.key);
// If the current node is less than the high_key node, check it\'s right
// subtree for values to print
if(high_key.compareTo(node.key) > 0)
printRang(node.right,low_key,high_key,print_data);
}
/*
Function Implementation end
*/
