Question 1 (100 POINTS): Write a JAVA program to do the following: 1. Read an in
ID: 650217 • Letter: Q
Question
Question 1 (100 POINTS): Write a JAVA program to do the following:
1. Read an input file input.txt whose content is given as: 8 3 10 1 6 14 4 7 13
2. Construct a binary search tree (BST) based on this input
3. Display the BST as follows (you may print / and without arrowheads for easier display).
?Display the BST in a suitable format to the standard output that we can easily see the root node, Its children, and grandchildren, etc. All the way down to the leaves. Of course, as we are not using GUI, no fancy display is required here. Still, please make sure that your BST appears proper and easy to understand on the standard output.?
Explanation / Answer
Answer
code for reading in the file
import java.io.*;
import java.util.Scanner;
public class Assign3 {
public static void main(String[]args) throws IOException
{
//Checks if there is a correct number of arguments passed through the command line.
if (args.length != 1)
{
quitError("Invalid number of arguments.");
}
String inputFile = args[0];
BST btree = new BST();
try
{
BufferedReader input = new BufferedReader(new FileReader(inputFile));
//Scans each word from the input and prints it out
String data = input.readLine();
while (data != null)
{
btree.insert(data);
btree.inorder();
btree.breadthFirst();
data = input.readLine();
System.out.println(data);
}
return;
} catch(FileNotFoundException filenotfoundexception) //Catches file not found exception
{
System.out.println("File not found.");
}
catch(IOException ioexception) //Catches input/output exception
{
System.out.println("File input error occured!");
}
}
//Displays an error message, program exits
public static void quitError(String msg)
{
System.out.println(msg);
System.out.println("Program will now quit.");
System.exit(0);
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------
Code for the node class:
public class BSTNode {
protected String data;
protected BSTNode left, right;
public BSTNode()
{
left = null;
right = null;
}
public BSTNode(String data)
{
this(data,null,null);
}
public BSTNode(String data, BSTNode lt, BSTNode rt)
{
this.data = data;
left = lt;
right = rt;
}
}
---------------------------------------------------------------------------------------------------------------------------------------------------
Code for the tree class:
public class BST {
protected BSTNode root = null;
public BST(){}
public void clear()
{
root = null;
}
public boolean isEmpty()
{
return root == null;
}
public void insert(String data) {
BSTNode current = root;
BSTNode prev = null;
while (current != null) { // find a place for inserting new node;
prev = current;
if (current.data.compareTo(data) < 0)
{
current = current.right;
}
else
{
current = current.left;
}
}
if (root == null) // tree is empty;
{
root = new BSTNode(data);
}
else if (prev.data.compareTo(data) < 0)
{
prev.right = new BSTNode(data);
}
else
{
prev.left = new BSTNode(data);
}
}
private void inorder(BSTNode current)
{
if (current != null)
{
inorder(current.left);
System.out.print(current.data + " ");
inorder(current.right);
}
}
public void inorder()
{
inorder(root);
}
public void breadthFirst()
{
BSTNode current = root;
Queue queue = new Queue();
if (current != null)
{
queue.enqueue(current);
while (!queue.isEmpty())
{
current = (BSTNode) queue.dequeue();
System.out.print(current.data + " ");
if (current.left != null)
queue.enqueue(current.left);
if (current.right != null)
queue.enqueue(current.right);
}
}
}
public void delete(Comparable data) {
BSTNode node, current = root, prev = null;
while (current != null && !current.data.equals(data)) { // find the node current
prev = current; // with element data;
if (current.data.compareTo((String) data) < 0)
current = current.right;
else current = current.left;
}
node = current;
if (current != null && current.data.equals(data)) {
if (node.right == null)
node = node.left;
else if (node.left == null)
node = node.right;
else {
BSTNode temp = node.left;
BSTNode previous = node;
while (temp.right != null) {
previous = temp;
temp = temp.right;
}
node.data = temp.data;
if (previous == node)
previous.left = temp.left;
else previous.right = temp.left;
}
if (current == root)
root = node;
else if (prev.left == current)
prev.left = node;
else prev.right = node;
}
else if (root != null)
System.out.println("data " + data + " is not in the tree");
else System.out.println("the tree is empty");
}
}
---------------------------------------------------------------------------------------------------------------------------------------------
Code for the queue class:
import java.util.LinkedList;
public class Queue {
private java.util.LinkedList list = new java.util.LinkedList();
public Queue() {
}
public void clear() {
list.clear();
}
public boolean isEmpty() {
return list.isEmpty();
}
public Object firstEl() {
return list.getFirst();
}
public Object dequeue() {
return list.removeFirst();
}
public void enqueue(Object el) {
list.add(el);
}
public String toString() {
return list.toString();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.