I need to know what every line means. Java Language. /* Erik Eldagsen Marquez CS
ID: 3841026 • Letter: I
Question
I need to know what every line means. Java Language.
/*
Erik Eldagsen Marquez
CSC 310 Analysis of Algorithms
02-28-2017
Project 2(BST)
*/
public class BinarySearchTree{
private Node root;
public BinarySearchTree(){ //create empty tree
root = null;
}
class Node{ //node that will store data from child nodes to the left and right
public String data;
public Node left;
public Node right;
public void addNode(Node newNode){ //inserting a new node that will be a descendant of the node of this node
//newNode = to the node that we are inserting
int comp = newNode.data.compareTo(data);
if (comp < 0){
if (left == null){
left = newNode;
}
else {
left.addNode(newNode);
}
}
else if (comp > 0){
if (right == null){
right = newNode;
}
else {
right.addNode(newNode);
}
}
}
public void printNodes(){ //prints this node and all the descendants from left to right order
if (left != null){
left.printNodes();
System.out.print(data + " ");
}
if (right != null){
right.printNodes();
}
}
}
public void addValue(String newValue){ //newValue = the new value to insert in the parameter
Node newNode = new Node(); //inserting new node into tree
newNode.data = newValue;
newNode.left = null;
newNode.right = null;
if (root == null){ //if empty
root = newNode; //then new node
}
else{
root.addNode(newNode); //if not empty then we add new node
}
}
public boolean search(String searchValue){ //searching for a value in the tree
Node current = root;
while (current != null){
int d = current.data.compareTo(searchValue);
if (d == 0){ //find the value in the tree then return true
return true;
}
else if (d > 0){ //if not then
current = current.left; //searching to the left
}
else{
current = current.right; //if not to the right
}
}
return false;
}
public void inOrderTraversal(){ //travers the bst in-order
inOrder(root);
}
public void inOrder(Node bst){
if(bst != null){ //if the node is not null.
inOrder(bst.left); //travers the left subtree in-order.
System.out.print(bst.data+" "); //print the data in that node.
inOrder(bst.right); //travers the right subtree in-order.
}
}
public void preOrderTraversal(){ //traver the bst in pre-order
preOrder(root);
}
public void preOrder(Node bst){
if(bst != null){ //if the node itself is not null.
System.out.print(bst.data+" "); //print the data in that node.
preOrder(bst.left); //travers the left subtree in pre-order.
preOrder(bst.right); //travers the right subtree in pre-order.
}
}
public void postOrderTraversal(){ //travers the bst in post-order
postOrder(root);
}
public void postOrder(Node bst){
if(bst != null){ //ff the node itself is not null.
postOrder(bst.left); //traverse the left subtree in post order.
postOrder(bst.right); //traverse the right subtree in post order.
System.out.print(bst.data+" "); //print the data in that node.
}
}
}
/*
Erik Eldagsen Marquez
CSC 310 Analysis of Algorithms
02-28-2017
Project 2(BST)
*/
import java.util.*;
import java.io.*;
class BinarySearchTreeTest{
public static void main(String[] args) throws FileNotFoundException{
BinarySearchTree bstTree = new BinarySearchTree();
Scanner sc = new Scanner(new File("500words.txt"));
while(sc.hasNext()){
String word = sc.next();
bstTree.addValue(word);
}
System.out.print("Pre-order traversal: ");
bstTree.preOrderTraversal();
System.out.println();
System.out.println();
System.out.print("In-order traversal: ");
bstTree.inOrderTraversal();
System.out.println();
System.out.println();
System.out.print("Post-order traversal: ");
bstTree.postOrderTraversal();
System.out.println();
System.out.println();
Scanner in = new Scanner(System.in);
System.out.print("Please input a word: ");
String word = in.next();
if(bstTree.search(word)){
System.out.println("'" + word + "' was found ");}
else{
System.out.println("'" + word + "' was NOT found ");
}
while(true){
System.out.print("Please input another word (CTRL+D to exit): ");
if(!in.hasNext()){
break;
}
word = in.next();
if(bstTree.search(word)){
System.out.println("'" + word + "' was found! ");
}
else{
System.out.println("'" + word + "' was NOT found! ");
}
}
}
}
Explanation / Answer
HI,
I am providing the comments after each eand of the line. Start with the main function, You can understand easily.
public class BinarySearchTree{
private Node root;
public BinarySearchTree(){ //create empty tree
root = null;
}
class Node{ //node that will store data from child nodes to the left and right
public String data;
public Node left;
public Node right;
public void addNode(Node newNode){ //inserting a new node that will be a descendant of the node of this node
//newNode = to the node that we are inserting
int comp = newNode.data.compareTo(data); //it compares the value in data and the newnode if newnode < data, it returns -1,newnode > data it return 1, else it will give 0
if (comp < 0){ // based on the above rule all the words entered into the tree
if (left == null){
left = newNode;
}
else {
left.addNode(newNode);
}
}
else if (comp > 0){
if (right == null){
right = newNode;
}
else {
right.addNode(newNode);
}
}
}
public void printNodes(){ //prints this node and all the descendants from left to right order
if (left != null){
left.printNodes();
System.out.print(data + " ");
}
if (right != null){
right.printNodes();
}
}
}
public void addValue(String newValue){ //newValue = the new value to insert in the parameter,newvalue brings the word from the file
Node newNode = new Node(); //inserting new node into tree
newNode.data = newValue; //storing the word onto the new node
newNode.left = null; //initializing the left and right node as null
newNode.right = null;
if (root == null){ //if empty
root = newNode; //then new node
}
else{
root.addNode(newNode); //if not empty then we add new node, it will redirect tot the function, let's move
}
}
public boolean search(String searchValue){ //searching for a value in the tree
Node current = root;
while (current != null){
int d = current.data.compareTo(searchValue);
if (d == 0){ //find the value in the tree then return true
return true;
}
else if (d > 0){ //if not then
current = current.left; //searching to the left
}
else{
current = current.right; //if not to the right
}
}
return false;
}
public void inOrderTraversal(){ //travers the bst in-order
inOrder(root);
}
public void inOrder(Node bst){
if(bst != null){ //if the node is not null.
inOrder(bst.left); //travers the left subtree in-order.
System.out.print(bst.data+" "); //print the data in that node.
inOrder(bst.right); //travers the right subtree in-order.
}
}
public void preOrderTraversal(){ //traver the bst in pre-order
preOrder(root);
}
public void preOrder(Node bst){
if(bst != null){ //if the node itself is not null.
System.out.print(bst.data+" "); //print the data in that node.
preOrder(bst.left); //travers the left subtree in pre-order.
preOrder(bst.right); //travers the right subtree in pre-order.
}
}
public void postOrderTraversal(){ //travers the bst in post-order
postOrder(root);
}
public void postOrder(Node bst){
if(bst != null){ //ff the node itself is not null.
postOrder(bst.left); //traverse the left subtree in post order.
postOrder(bst.right); //traverse the right subtree in post order.
System.out.print(bst.data+" "); //print the data in that node.
}
}
}
//main function
import java.util.*;
import java.io.*;
class BinarySearchTreeTest{
public static void main(String[] args) throws FileNotFoundException{ //program will start from here
BinarySearchTree bstTree = new BinarySearchTree(); //creating the object for the class
Scanner sc = new Scanner(new File("500words.txt")); // we are taking the file as input, which contains the 500 words
while(sc.hasNext()){ //it returns true if there's still more elements after the current position of the iterator
String word = sc.next(); //next()function returns the value of the element at the current position. After returning this value, it also advances the pointer to the next element.
bstTree.addValue(word); //it will redirect to the function public void addValue(String newValue) let's go there
}
System.out.print("Pre-order traversal: ");
bstTree.preOrderTraversal(); //it's calling the public void inOrderTraversal() function
System.out.println();
System.out.println();
System.out.print("In-order traversal: ");// it's calling the public void inOrderTraversal()
bstTree.inOrderTraversal();
System.out.println();
System.out.println();
System.out.print("Post-order traversal: ");
bstTree.postOrderTraversal(); //it's calling the public void postOrderTraversal()
System.out.println();
System.out.println();
Scanner in = new Scanner(System.in);
System.out.print("Please input a word: ");//it takes the input from the user
String word = in.next();
if(bstTree.search(word)){ //it will call the function public boolean search(String searchValue) and gives true, if the entered input found in the tree,else it will give false
System.out.println("'" + word + "' was found ");}
else{
System.out.println("'" + word + "' was NOT found ");
}
while(true){
System.out.print("Please input another word (CTRL+D to exit): "); //it will take the input fro the use
if(!in.hasNext()){ // if the entered work not the tree, it will come out from the loop
break;
}
word = in.next();
if(bstTree.search(word)){
System.out.println("'" + word + "' was found! ");
}
else{
System.out.println("'" + word + "' was NOT found! ");
}
}
}
}