I have the program here. I just have to do the following two things: (1) Create
ID: 3642466 • Letter: I
Question
I have the program here. I just have to do the following two things:(1) Create a data (text) file containing some (any number of)
integers, one per line.
(2) Write a program to test the class BinSearchTree. In particular,
in your main method:
* Create a BST (it will be initially empty).
* Read the integers from your data file. As you read each value,
insert it into the BST. (Use the tree's "add" method.)
* Do preorder, inorder, and postorder traversals of the BST; use
the methods given in BinSearchTree.java.
* Print the height of the tree. (The method "height" is defined
as part of a tree object.)
* Prompt the user for an integer data value, and search the tree to
see if the value is there. (Again, "search" is defined for you.)
Print a message telling the user the result of the search.
Note: Of course, the user will know the result in advance
because you will be displaying the contents of the tree
beforehand. No problem; it's just an exercise.
///////////////////////////////////////////////////////////////
//
// The class BinSearchTree: a link-based implementation.
//
// Note that the utility methods preorder, inorder,
// and postorder are included in this module as
// static methods---essentially trusted clients.
//
//
//
///////////////////////////////////////////////////////////////
public class BinSearchTree
{
// define the "Node" class to be private to "BinSearchTree."
private class Node
{
int item; // root item of tree
BinSearchTree lsubtree; // reference to left subtree
BinSearchTree rsubtree; // reference to right subtree
}
// reference to the root
private Node root;
////////////////////////////////////////////////////////////
BinSearchTree()
{
//
// create an empty tree by setting the root reference
// to null
//
root = null;
} // end constructor
////////////////////////////////////////////////////////////
public boolean isEmpty()
{
//
// Determine if the tree is empty. Simply
// check the root reference for a value of null.
//
boolean retVal;
if(root == null)
retVal = true;
else
retVal = false;
return retVal;
} // end isEmpty
////////////////////////////////////////////////////////////
public int height()
{
//
// This method returns the height of the tree, which is
// either 0 if the tree is empty or, otherwise, 1 more
// than the maximum of the heights of the left subtree
// and the right subtree.
//
if(root == null)
return 0;
else
return 1 + Math.max(root.lsubtree.height(),
root.rsubtree.height());
} // end height
////////////////////////////////////////////////////////////
public void add(int new_item)
{
//
// Add the given data item "new_item" to the tree. If
// the tree is currently empty, then the new item will
// be its root. If not, add the new item to the root's
// left subtree in the case that new_item < root, or
// otherwise add it to the root's right subtree.
//
if(isEmpty())
{
root = new Node();
root.item = new_item;
root.lsubtree = new BinSearchTree();
root.rsubtree = new BinSearchTree();
}
else if(new_item < root.item)
root.lsubtree.add(new_item);
else
root.rsubtree.add(new_item);
} // end add
////////////////////////////////////////////////////////////
public boolean search(int x)
{
//
// Determine if the data item x is in the tree.
// Returns "true" if it is; "false," otherwise.
//
boolean retVal;
// if the tree is empty, then the item can't be there
if(isEmpty())
retVal = false;
// if not, is the root the item we're looking for?
else if(x == root.item)
retVal = true;
// otherwise, check the left subtree if x < root, or the
// right subtree if x > root
else if(x < root.item)
retVal = root.lsubtree.search(x);
else
retVal = root.rsubtree.search(x);
return retVal;
} // end search
////////////////////////////////////////////////////////////
public static void preorder(BinSearchTree t)
{
//
// perform a preorder traversal of the tree t
//
if(!t.isEmpty())
{
// visit (print) the root
System.out.println(t.root.item);
// preorder the left subtree
preorder(t.root.lsubtree);
// preorder the right subtree
preorder(t.root.rsubtree);
}
} // end preorder
////////////////////////////////////////////////////////////
public static void inorder(BinSearchTree t)
{
//
// perform an inorder traversal of the tree t
//
if(!t.isEmpty())
{
// inorder the left subtree
inorder(t.root.lsubtree);
// visit (print) the root
// visit (print) the root
System.out.println(t.root.item);
// inorder the right subtree
inorder(t.root.rsubtree);
}
} // end inorder
////////////////////////////////////////////////////////////
public static void postorder(BinSearchTree t)
{
//
// perform a postorder traversal of the tree t
//
if(!t.isEmpty())
{
// postorder the left subtree
postorder(t.root.lsubtree);
// postorder the right subtree
postorder(t.root.rsubtree);
// visit (print) the root
System.out.println(t.root.item);
}
} // end postorder
////////////////////////////////////////////////////////////
} // end BinSearchTree
Explanation / Answer
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;
public class BSTTest {
public static void main(String[] args) {
BinSearchTree tree = new BinSearchTree();
FileWriter fstream;
try {
fstream = new FileWriter("data.txt");
BufferedWriter out = new BufferedWriter(fstream);
Random rand = new Random();
for(int i = 0; i < 20; ++i) {
out.write(Math.abs((rand.nextInt() % 30) + 1) + " ");
}
out.close();
}
catch (IOException e1) {
System.out.println("File not found");
}
try {
Scanner in = new Scanner(new File("data.txt"));
while(in.hasNextInt()) {
tree.add(in.nextInt());
}
System.out.println("Preorder traversal: ");
tree.preorder(tree);
System.out.println("Inorder traversal: ");
tree.inorder(tree);
System.out.println("Postorder traversal: ");
tree.postorder(tree);
System.out.println("Height of tree: " + tree.height());
Scanner user = new Scanner(System.in);
System.out.print("Enter an integer: ");
if(tree.search(user.nextInt())) {
System.out.println("The integer was found in the tree");
}
else {
System.out.println("The integer was not found in the tree");
}
}
catch (FileNotFoundException e) {
System.out.println("File not found");
}
}
}