If you’re a CS student, it’s only a matter of time before you have to write a program implementing a Binary Search Tree. Below, I will go through how I would do it, but what makes this version different from most other examples on the Internet is that this one loads a configuration file (list of commands) and gives a specific output according to the instructions for my class at the time. Because the code to this assignment is pretty lengthy, I’ve made the source code available for download (MyBinarySearchTree.zip).
Instructions
This program is to implement Binary-Search-Tree (BST) operations. (No balancing is performed.) Assume integer key values. Implement the following operations:
- Search: Search for an element with a given key.
- Insert: Insert a new element.
- Delete: Find and delete an element with a given key.
- Print: Print an inorder listing of all elements in the tree.
Your program must read and execute a list of commands from a file, where each command follows one or more integers separated by white-space. The letter I represents the Insert command; the letter D represents the Delete command; the letter S represents the Search command; the letter P represents the Print command.
Note that when an insert or delete fails (for an element already in a list or an element not in the list), an appropriate error message should be returned.
Configuration File
Before I started programming, I made the configuration file, which holds the commands for the program to execute. I called this file config.txt (but you can name it whatever you like, so long as you call it the right name in your program).
I 60 90 100 20 30 80 10 P I 70 75 40 35 32 78 72 37 P D 60 P D 30 80 10 100 P I 90 D 5
Note that the last Insert command (I 90, where 90 is already in the tree) should throw an error, as will the last Delete command (D 5, where 5 is not in the tree).
Creating a Binary Search Tree Node
Before we can create a Binary Search Tree, we have to create a node — more specifically, a root node (which is based on a regular node, regardless). Thus, we create a simple class for this purpose, and it will be used each time we need to construct a new node:
import java.util.Stack;
public class MyBinarySearchTree {
protected MyBinarySearchTreeNode root; // Root Node of Tree
/**
* Default Constructor
*/
public MyBinarySearchTree() {
root = null; // Create a blank tree
} // end default constructor
/**
* This exception is thrown when a duplicate
* item is in the tree.
*
*/
class DuplicateItemException extends RuntimeException {
private static final long serialVersionUID = 1L;
/**
* Default Constructor
*/
public DuplicateItemException( ) {
super();
} // end default constructor
/**
* DuplicateItemException Constructor
*
* @param error
*/
public DuplicateItemException( String error ) {
super( error );
} // end DuplicateItemException constructor
} // end DuplicateItemException class
/**
* This exception is thrown when the item
* is not found in the tree.
*
*/
class ItemNotFoundException extends RuntimeException {
private static final long serialVersionUID = 1L;
/**
* Default Constructor
*/
public ItemNotFoundException() {
super();
} // end default constructor
/**
* ItemNotFoundException Constructor
*
* @param error
*/
public ItemNotFoundException( String error ) {
super( error );
} // end ItemNotFoundException constructor
} // end class ItemNotFoundException
/**
* This method finds and deletes an
* element with a given key.
*
* @param element
*/
public void delete( Comparable element ) {
root = delete(element, root);
} // end method delete()
/**
* This method deletes a specified
* node in the tree.
*
* @param element
* @param node
* @return node
*/
private MyBinarySearchTreeNode delete( Comparable element, MyBinarySearchTreeNode node ) {
/**
* First, check if the item is in the tree.
* If it's not in the tree, throw a
* ItemNotFoundException object
*/
try {
if ( node == null ) {
throw new ItemNotFoundException( "DELETE " + element.toString() + " FAILED (not in the list)." );
}
} catch (ItemNotFoundException e ){
System.out.println("\n\nDELETE " + element.toString() + " FAILED (not in the list).");
return node;
}
/**
* Compare the element to the node. If it's
* less than zero, delete the left node.
*/
if ( element.compareTo( node.element ) < 0 ) {
node.left = delete( element, node.left ); // Delete left node
}
/**
* Compare the element to the node. If it's
* greater than 0, delete the right node.
*/
else if ( element.compareTo( node.element ) > 0 ) {
node.right = delete( element, node.right ); // Delete right node
}
/**
* Otherwise, the node has two children. Find the
* minimum element on the right side and delete it.
*/
else if ( node.left != null && node.right != null ) {
node.element = getMin( node.right ).element;
node.right = deleteMin( node.right );
} else {
node = ( node.left != null ) ? node.left : node.right;
}
return node;
} // end method delete()
/**
* This method deletes the minimum
* node in the tree.
*/
public void deleteMin() {
root = deleteMin( root );
} // end method deleteMin()
/**
* This method deletes the minimum
* node in the tree.
*
* @param node
* @return node
*/
private MyBinarySearchTreeNode deleteMin( MyBinarySearchTreeNode node ) {
/**
* First check if the node exists.
* If not, throw a ItemNotFoundException
* object.
*/
if ( node == null ) {
throw new ItemNotFoundException( );
}
/**
* Otherwise, check if the left node is null.
* If it's not, delete the minimum element
* on the left side and return that node.
*/
else if( node.left != null ) {
node.left = deleteMin( node.left );
return node;
}
/**
* Otherwise, simply return the right node.
*/
else return node.right;
} // end method deleteMin()
/**
* This method returns a comparable element
* from a given node.
*
* @param node
* @return Comparable
*/
private Comparable elementAt( MyBinarySearchTreeNode node ) {
return node == null ? null : node.element;
} // end method elementAt()
/**
* This method returns a comparable object
* that is that maximum node.
*
* @return Comparable
*/
public Comparable getMax() {
return elementAt( getMax( root ) );
} // end method getMax()
/**
* This method returns the maximum
* node in the tree.
*
* @param node
* @return node
*/
private MyBinarySearchTreeNode getMax( MyBinarySearchTreeNode node ) {
/**
* First make sure the node is not
* null.
*/
if( node != null ) {
/**
* Keep traversing the right nodes until
* the right node is null. This node will
* be the max.
*/
while ( node.right != null ) {
node = node.right;
} // end while loop
} // end if
return node;
} // end method getMax()
/**
* This method returns the minimum
* node in the tree.
*
* @return Comparable
*/
public Comparable getMin() {
return elementAt( getMin( root ) );
} // end method getMin()
/**
* This method returns the minimum
* node in the tree.
*
* @param node
* @return node
*/
private MyBinarySearchTreeNode getMin( MyBinarySearchTreeNode node ) {
/**
* First make sure the node is not
* null.
*/
if ( node != null ) {
/**
* Keep traversing the tree until
* the left node is not null.
* This is the minimum element in
* the tree.
*/
while( node.left != null ) {
node = node.left;
} // end while loop
} // end if
return node;
} // end method getMin()
/**
* This method inserts a given element
* into the binary search tree.
*
* @param element
*/
public void insert( Comparable element ) {
root = insert( element, root );
} // end method insert()
private MyBinarySearchTreeNode insert( Comparable element, MyBinarySearchTreeNode node ) {
try {
/**
* Root node is null
*/
if ( node == null ) {
node = new MyBinarySearchTreeNode( element );
}
/**
* Insert element to the left
*/
else if ( element.compareTo( node.element ) < 0 ) {
node.left = insert( element, node.left );
}
/**
* Insert element to the right
*/
else if ( element.compareTo( node.element ) > 0 ) {
node.right = insert( element, node.right );
}
/**
* Element is already in the tree
*/
else {
throw new DuplicateItemException( element.toString() );
}
} catch (DuplicateItemException e ){
System.out.println("\n\nINSERT " + element.toString() + " FAILED (already in the list).");
return node;
}
return node;
} // end method insert()
/**
* This method returns a boolean
* value depending on whether or
* not the tree is empty.
*
* @return boolean
*/
public boolean isEmpty() {
return root == null;
} // end method isEmpty()
/**
* This method makes the tree empty
*/
public void makeEmpty() {
root = null;
} // end method makeEmpty()
/**
* This method iteratively traverses the
* tree using a stack to store the nodes.
*
*/
public void nonRecursiveInTraversal() {
Stack<MyBinarySearchTreeNode> stack = new Stack<MyBinarySearchTreeNode>(); // Stack of nodes
MyBinarySearchTreeNode currentNode = root; // Current node gets the root
/**
* Make sure the root node is not null
*/
while ( ( currentNode != null ) || ( !stack.empty() ) ) {
/**
* If the current node is not null,
* put the node in the stack and traverse
* to the left
*/
if ( currentNode != null ) {
stack.push(currentNode); // Put the current node in the stack
currentNode = currentNode.left; // Current node gets the left node now
}
/**
* Otherwise, the current node is null,
* so traverse to the right
*/
else {
currentNode = (MyBinarySearchTreeNode) stack.peek(); // Get the current node value
stack.pop(); // Remove the node from the stack
System.out.println(currentNode.element + " ");
currentNode = currentNode.right;
}
} // end while loop
} // end method nonRecursiveInTraversal()
/**
* This method is the helper method to
* recursively traverse the tree.
*
*/
public void recursiveInorderTraversal() {
recursiveInorderTraversal( root );
} // end method recursiveInorderTraversal()
/**
* This method recursively traverses
* the tree.
*
* @param node
*/
private void recursiveInorderTraversal( MyBinarySearchTreeNode node ) {
if ( node != null ) {
recursiveInorderTraversal( node.left );
System.out.print( node.element + " " );
recursiveInorderTraversal ( node.right );
}
} // end method recursiveInorderTraversal()
/**
* This method finds and returns a comparable element
*
* @param element
* @return
*/
public Comparable search( Comparable element ) {
return elementAt( search( element, root ) );
} // end method find()
private MyBinarySearchTreeNode search( Comparable element, MyBinarySearchTreeNode node ) {
/**
* Make sure root node is not null
*/
while( node != null ) {
/**
* If the element is less than 0,
* get the node on the left
*/
if( element.compareTo( node.element ) < 0 ) {
node = node.left;
}
/**
* If the element is greater than 0,
* get the node on the right
*/
else if( element.compareTo( node.element ) > 0 ) {
node = node.right;
}
/**
* Otherwise, a match was found
*/
else {
System.out.println("\n\nElement " + element + " found!");
return node; // Match!
}
} // end while loop
System.out.println("\n\nElement " + element + " not found!");
return null; // Not found
} // end method search()
} // end class MyBinarySearchTree
Note that in this example, we include both a recursive and non-recursive traversal method. In the application itself, we use the recursive method, but in your project, you may be required to understand and perform either.
Loading the Configuration
The next problem to solve is how to load the configuration file. One thing to keep in mind is, this class should be able to use your default configuration file and it should also be flexible so that someone else can use their own configuration file. The basic logic for loading and interpreting / executing the commands is the following:
- Read the file line-by-line (until there are no lines left)
- Does the line start with I? Insert all the elements after the command until the line terminates.
- Does the line start with P? Print an inorder list of all the elements in the tree.
- Does the line start with S? Search for all the elements following the command until the line terminates.
- Does the line start with D? Delete all the elements following the command until the line terminates.
Here’s the code:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class LoadConfiguration {
private String fileName; // Configuration File Name
private MyBinarySearchTree t = new MyBinarySearchTree(); // New Binary Search Tree
/**
* Default constructor
*/
public LoadConfiguration() {
this.fileName = "config.txt";
} // end default constructor
/**
* Overloaded constructor
* @param fileName
*/
public LoadConfiguration ( String fileName ) {
this.fileName = fileName;
} // end overloaded constructor
/**
* This method reads the whole
* configuration file. Useful for
* testing and debugging. Results
* are printed to the console.
*
*/
public void readFile() {
/**
* Read the configuration file and check
* for commands.
*/
try {
String line; // String to store each line
final BufferedReader br = new BufferedReader( new FileReader( fileName ) );
/**
* While the line is not null,
* keep reading the file.
*/
while ( ( line = br.readLine()) != null ) { // while loop begins here
System.out.println( "\nInstruction: \t" + line + "\n"); // Instruction to execute
/**
* Insert command
*/
if ( line.startsWith("I") ) {
System.out.println("Inserting elements...");
System.out.println("------------------------------");
StringBuffer linebuffer = new StringBuffer(); // Buffer to store elements
int i = 1; // start index at end of identifier length (one char)
char c = line.charAt(i); // get the char at current index
/**
* A StringIndexOutOfBoundsException will be thrown
* once there are no more strings on the given line
*/
try {
/**
* Keep reading until the line terminates
*/
while ( c != '\n' ) { // terminate on \n
linebuffer.append(c); // append char to stringbuffer
c = line.charAt(++i); // increment char index
} // end while
} catch ( StringIndexOutOfBoundsException e ) {}
String finalResult = linebuffer.toString(); // Final Result
finalResult = finalResult.replaceAll("\t", ""); // Get rid of tabs
System.out.print(finalResult); // Print the Final Result for debugging
StringTokenizer st = new StringTokenizer( finalResult, " " ); // Get tokens after each space
/**
* While we have more tokens, get the
* next token and insert it into the tree
*/
while ( st.hasMoreTokens() ) {
String next = st.nextToken(); // Get next token
t.insert( next ); // Insert it into the tree
} // end while
System.out.println(); // Print a blank line
} // end if (insert command)
/**
* Traverse & Print the Tree Elements
*/
else if ( line.startsWith("P") ) {
System.out.println("Traversing & Printing Tree Elements...");
System.out.println("---------------------------------------");
t.recursiveInorderTraversal(); // Traverse the tree (recursive in-order)
System.out.println(); // Print a blank line
} // end if (traverse and print)
/**
* Delete An Element
*/
else if ( line.startsWith("D") ) {
System.out.println("Deleting Elements...");
System.out.println("---------------------------------------");
StringBuffer linebuffer = new StringBuffer();
int i = 1; // start index at end of identifier length
char c = line.charAt(i); // get the char at current index
/**
* A StringIndexOutOfBoundsException will be thrown
* once there are no more strings on the given line
*/
try {
/**
* Keep reading until the line terminates
*/
while ( c != '\n' ) { // terminate on \n
linebuffer.append(c); // append char to stringbuffer
c = line.charAt(++i); // increment char index
} // end while
} catch ( StringIndexOutOfBoundsException e ) {}
String finalResult = linebuffer.toString(); // Final Result
finalResult = finalResult.replaceAll("\t", ""); // Get rid of tabs
System.out.print(finalResult); // Print the Final Result for debugging
StringTokenizer st = new StringTokenizer( finalResult, " " ); // Get tokens after each space
/**
* While we have more tokens, get the
* next token and delete it from the tree
*/
while ( st.hasMoreTokens() ) {
String next = st.nextToken(); // Get the next token
t.delete( next ); // Delete it from the tree
} // end while
System.out.println(); // Print a blank line
} // end if (delete item)
/**
* Search
*/
else if ( line.startsWith("S") ) {
System.out.println("Searching Elements...");
System.out.println("---------------------------------------");
StringBuffer linebuffer = new StringBuffer();
int i = 1; // start index at end of identifier length
char c = line.charAt(i); // get the char at current index
/**
* A StringIndexOutOfBoundsException will be thrown
* once there are no more strings on the given line
*/
try {
/**
* Keep reading until the line terminates
*/
while ( c != '\n' ) { // terminate on \n
linebuffer.append(c); // append char to stringbuffer
c = line.charAt(++i); // increment char index
} // end while
} catch ( StringIndexOutOfBoundsException e ) {}
String finalResult = linebuffer.toString(); // Final Result
finalResult = finalResult.replaceAll("\t", ""); // Get rid of tabs
System.out.print(finalResult); // Print the Final Result for debugging
StringTokenizer st = new StringTokenizer( finalResult, " " ); // Get tokens after each space
/**
* While we have more tokens, get the
* next token and search for it
*/
while ( st.hasMoreTokens() ) {
String next = st.nextToken(); // Get the next token
t.search( next ); // Search for the token in the tree
} // end while
System.out.println(); // Print a blank line
} // end if (search element)
} // end while
System.out.println("\nEnd of config file.\n");
} catch (final IOException e) {
System.err.println("Error Reading File: " + e + "\n");
} // end try
} // end readFile() method
} // end LoadConfiguration
Now that we’ve got the majority of the program finished, all we have to do is create a class to hold the main method, which will open the configuration file and help create the tree.
The Main Method
We’ll create a class called MyBinarySearchTreeApp.java to hold the main method (just to keep it separate from the rest of the code). This class will take the command arguments from the console and load either the default or a given configuration file and run it. This, in turn, will execute the configuration file and run the commands.
public class MyBinarySearchTreeApp {
/**
* Main Method
*
* @param args
*/
public static void main(String[] args) {
System.out.println("\nDefault Usage: java MyBinarySearchTreeApp");
System.out.println("\n\nTo load your own configuration file:");
System.out.println("----------------------------------------------------");
System.out.println("java MyBinarySearchTreeApp pathToYourConfigFile\n\n");
LoadConfiguration lc = null;
/**
* Load the default config file
*/
if ( args.length < 1 ) {
System.out.println("Reading default config file...");
lc = new LoadConfiguration(); // New config file
}
/**
* Load a given config file
*/
else {
System.out.println("Reading given config file... (overriding default).");
lc = new LoadConfiguration( args[0] ); // Given config file
}
/**
* Make sure config file is not null
*/
if ( lc != null ) {
lc.readFile(); // Read the config file
} else {
System.out.println("Error: Could not read config file.");
}
} // end main method
} // end class MyBinarySearchTreeApp
Output and Conclusion
After compiling all of the above code and running the main class with the default configuration file, the following is my output:
Default Usage: java MyBinarySearchTreeApp To load your own configuration file: ---------------------------------------------------- java MyBinarySearchTreeApp pathToYourConfigFile Reading default config file... Instruction: I 60 90 100 20 30 80 10 Inserting elements... ------------------------------ 60 90 100 20 30 80 10 Instruction: P Traversing & Printing Tree Elements... --------------------------------------- 10 100 20 30 60 80 90 Instruction: I 70 75 40 35 32 78 72 37 Inserting elements... ------------------------------ 70 75 40 35 32 78 72 37 Instruction: P Traversing & Printing Tree Elements... --------------------------------------- 10 100 20 30 32 35 37 40 60 70 72 75 78 80 90 Instruction: D 60 Deleting Elements... --------------------------------------- 60 Instruction: P Traversing & Printing Tree Elements... --------------------------------------- 10 100 20 30 32 35 37 40 70 72 75 78 80 90 Instruction: D 30 80 10 100 Deleting Elements... --------------------------------------- 30 80 10 100 Instruction: P Traversing & Printing Tree Elements... --------------------------------------- 20 32 35 37 40 70 72 75 78 90 Instruction: I 90 Inserting elements... ------------------------------ 90 INSERT 90 FAILED (already in the list). Instruction: D 5 Deleting Elements... --------------------------------------- 5 DELETE 5 FAILED (not in the list). End of config file.
Questions, comments, suggestions? Leave them in the comments!
Tags: binary search tree, bst, Data Structures & Algorithms, Java