Use Java. Given the text file, follow the instructions and put the integers into
ID: 3879368 • Letter: U
Question
Use Java.
Given the text file, follow the instructions and put the integers into a binary tree. Read in the file using BufferedReader. Below are the input.txt and expected solution.
input.txt:
insert 40,50,30,20,60,35,45,47
find 35
delete 50
traverse 1
traverse 2
traverse 3
min
max
show
expected outcome:
Inserting: 40,50,30,20,60,35,45,47
Found: {35, 35.9}
Deleted: 50
Preorder traversal: 40 30 20 35 60 45 47
Inorder traversal: 20 30 35 40 45 47 60
Postorder traversal: 20 35 30 47 45 60 40
Min: {20, 20.9}
Max: {60, 60.9}
.................................................................
40
.................................................................
30 60
.................................................................
20 35 45 --
.................................................................
-- -- -- -- -- 47 -- --
Explanation / Answer
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
/* Class BinaryTreeNode */
class BinaryTreeNode
{
int data;
BinaryTreeNode left, right;
/* Constructor */
public BinaryTreeNode()
{
left = null;
right = null;
data = 0;
}
/** Constructor
* @param n : data to be insert
**/
public BinaryTreeNode(int n)
{
left = null;
right = null;
data = n;
}
//Start of getter setter methids
/* Function set left node */
public void setLeft(BinaryTreeNode n)
{
left = n;
}
/* Function set right node */
public void setRight(BinaryTreeNode n)
{
right = n;
}
/* Function to get left node */
public BinaryTreeNode getLeft()
{
return left;
}
/* Function to get right node */
public BinaryTreeNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
public class BinaryTree {
private BinaryTreeNode root;
/* Constructor */
public BinaryTree()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private BinaryTreeNode insert(BinaryTreeNode node, int data)
{
if (node == null)
node = new BinaryTreeNode(data);
else
{
if (data <= node.data)
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Function to search for an element */
public boolean search(int val)
{
return search(root, val);
}
/* Function to search for an element recursively */
private boolean search(BinaryTreeNode r, int val)
{
if (r.getData() == val)
return true;
if (r.getLeft() != null)
if (search(r.getLeft(), val))
return true;
if (r.getRight() != null)
if (search(r.getRight(), val))
return true;
return false;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(BinaryTreeNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(BinaryTreeNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(BinaryTreeNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
void deletedata(int data)
{
root = deleteNode(root, data);
}
private BinaryTreeNode deleteNode(BinaryTreeNode rootNode, int data) {
if(rootNode==null){
return null;
}
if(data==rootNode.getData()){
if(rootNode.getLeft()!=null && rootNode.getRight()!=null){
//Find Minimum from Right Tree OR find Maximum from Left Tree.
BinaryTreeNode minNode = getHighestNodeFromRight(rootNode.getRight());
rootNode.setData(minNode.getData());
rootNode.setRight(deleteNode(rootNode.getRight(), minNode.getData()));
}else if(rootNode.getLeft()==null){
return rootNode.getRight();
}
else
{
return rootNode.getLeft();
}
}else if(data>rootNode.getData()){
rootNode.setRight(deleteNode(rootNode.getRight(), data));
}else{
rootNode.setLeft(deleteNode(rootNode.getLeft(), data));
}
return rootNode;
}
public BinaryTreeNode getHighestNodeFromRight(BinaryTreeNode node)
{
if(node.getLeft()== null)
return node;
else
return(getHighestNodeFromRight(node.getLeft()));
}
/* Function to return least value */
public int minValue()
{
return minValue(root);
}
/* Function to return least value recursively */
private int minValue(BinaryTreeNode r)
{
if (r.left == null)
return r.data;
return minValue(r.left);
}
/* Function to return least value */
public int maxValue()
{
return maxValue(root);
}
/* Function to return least value recursively */
private int maxValue(BinaryTreeNode r)
{
if (r.right == null)
return r.data;
return maxValue(r.right);
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(BinaryTreeNode root)
{
if (root == null)
return 0;
else
{
/* compute height of each subtree */
int lheight = height(root.left);
int rheight = height(root.right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
public void show()
{
System.out.println(" .................................................................");
printLevelOrder(root);
}
/* Function to line by line print level order traversal a tree*/
void printLevelOrder(BinaryTreeNode root)
{
int h = height(root);
int i;
for (i=1; i<=h; i++)
{
printGivenLevel(root, i);
System.out.println(" .................................................................");
}
}
/* Print nodes at a given level */
void printGivenLevel(BinaryTreeNode root, int level)
{
if (root == null)
{
System.out.print("-- ");
return;
}
if (level == 1)
System.out.print(root.data +" ");
else if (level > 1)
{
printGivenLevel(root.left, level-1);
printGivenLevel(root.right, level-1);
}
}
@SuppressWarnings("resource")
public static void main(String[] args) throws IOException {
BufferedReader buffRead = null;
BinaryTree bt = new BinaryTree();
buffRead = new BufferedReader(new FileReader("src//input.txt"));
String line = buffRead.readLine();
while(line != null)
{
String[] splitStr = line.split("\s+");
if(splitStr[0].equals("insert"))
{
String[] data = splitStr[1].split(",");
System.out.print("Inserting : ");
for(int i=0; i < data.length; i++)
{
System.out.print(data[i] + " ");
bt.insert(Integer.parseInt(data[i]));
}
System.out.println();
}
else if(splitStr[0].equals("find"))
{
int num = Integer.parseInt(splitStr[1]);
if(bt.search(num))
{
System.out.println("Found: {" + num + ", " + (num + 0.9) + "}");
}
else
System.out.println("No Data Found");
}
else if(splitStr[0].equals("delete"))
{
int num = Integer.parseInt(splitStr[1]);
if(bt.search(num))
{
bt.deletedata(num);
System.out.println("Deleted : " + num);
}
else
System.out.println("Node not present in tree");
}
else if(splitStr[0].equals("traverse"))
{
if(splitStr[1].equals("1"))
{
System.out.print("Preorder traversal:");
bt.preorder();
System.out.println();
}
else if(splitStr[1].equals("2"))
{
System.out.print("Inorder traversal:");
bt.inorder();
System.out.println();
}
else if(splitStr[1].equals("3"))
{
System.out.print("Postorder traversal:");
bt.postorder();
System.out.println();
}
}
else if(splitStr[0].equals("min"))
{
int min = bt.minValue();
System.out.println("Min: {" + min + "," + (min + 0.9) + "}");
}
else if(splitStr[0].equals("max"))
{
int max = bt.maxValue();
System.out.println("Max: {" + max + "," + (max + 0.9) + "}");
}
else if(splitStr[0].equals("show"))
{
bt.show();
}
line = buffRead.readLine();
}
}
}
OUTPUT:
Inserting : 40 50 30 20 60 35 45 47
Found: {35, 35.9}
Deleted : 50
Preorder traversal:40 30 20 35 60 45 47
Inorder traversal:20 30 35 40 45 47 60
Postorder traversal:20 35 30 47 45 60 40
Min: {20,20.9}
Min: {60,60.9}
.................................................................
40
.................................................................
30 60
.................................................................
20 35 45 --
.................................................................
-- -- -- -- -- 47 --
.................................................................
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.