Objective: IN JAVA Write a program which creates a binary search tree of differe
ID: 3734771 • Letter: O
Question
Objective:
IN JAVA
Write a program which creates a binary search tree of different shapes from a file.
· The comparison is based on the shape’s area
· There are 3 shapes
o Rectangle
o Circle
o Right Triangle
· The file is tab delimited format goes as follows
o Rectangle side 1 side 2
o Circle radius
o Right Triangle side 1 side 2
· The binary search tree needs to have the following methods
o insert: inserts a new shape into the tree
o delete: deletes the shape instance. Keep in mind that in order for a shape to be equal it must have the same same type and area, but the sides can be interchangeable.
o print pre-order traversal: Print the data. Next explore the left subtree. Finally right explore subtree.
o print in-order traversal: Explore the left subtree. Print the data. Finally explore the right subtree.
o print post-order traversal: Explore the left subtree. Then explore the right subtree. Finally print out the data.
o max area: return the maximum area in the tree. Use the properties of the tree to make it efficient.
o delete areas greater than value: For a given value all shapes with an area that’s strictly greater than those values should be deleted. Use the principle of a binary search tree to help make it efficient.
· Finally write a test file that demonstrates THE POWER OF TREES!!! SHAPES!!! By reading a shape file.
FILE:
HINTS:
Inheritance and polymorphism makes this problem not so difficult, so interfaces and base classes are a good idea.
Yes there will be many different class files.
Recursion is your friend.
Example of Results:
Welcome to the shape tree tester!
Reading from file
Rectangle 5 4
Circle 4
Right Triangle 3 2
Rectangle 2 7
Circle 8
Right Triangle 5 6
Rectangle 9 2
Circle 2
Rectangle 5 5
Right Triangle 9 9
Circle 7
Not properly formatted line. Yes you should check for these. Not intentionally causing a kerfuffle
Rectangle 3 8
Circle 9
Right Triangle 2 2
Printing pre-order
Rectangle Side 1: 5.0 Side 2: 4.0 Area: 20.0
Right Triangle Side 1: 3.0 Side 2: 2.0 Area: 3.0
Right Triangle Side 1: 2.0 Side 2: 2.0 Area: 2.0
Rectangle Side 1: 2.0 Side 2: 7.0 Area: 14.0
Circle Radius: 2.0 Area: 12.566370614359172
Right Triangle Side 1: 5.0 Side 2: 6.0 Area: 15.0
Rectangle Side 1: 9.0 Side 2: 2.0 Area: 18.0
Circle Radius: 4.0 Area: 50.26548245743669
Rectangle Side 1: 5.0 Side 2: 5.0 Area: 25.0
Rectangle Side 1: 3.0 Side 2: 8.0 Area: 24.0
Right Triangle Side 1: 9.0 Side 2: 9.0 Area: 40.5
Circle Radius: 8.0 Area: 201.06192982974676
Circle Radius: 7.0 Area: 153.93804002589985
Circle Radius: 9.0 Area: 254.46900494077323
Printing in-order
Right Triangle Side 1: 2.0 Side 2: 2.0 Area: 2.0
Right Triangle Side 1: 3.0 Side 2: 2.0 Area: 3.0
Circle Radius: 2.0 Area: 12.566370614359172
Rectangle Side 1: 2.0 Side 2: 7.0 Area: 14.0
Right Triangle Side 1: 5.0 Side 2: 6.0 Area: 15.0
Rectangle Side 1: 9.0 Side 2: 2.0 Area: 18.0
Rectangle Side 1: 5.0 Side 2: 4.0 Area: 20.0
Rectangle Side 1: 3.0 Side 2: 8.0 Area: 24.0
Rectangle Side 1: 5.0 Side 2: 5.0 Area: 25.0
Right Triangle Side 1: 9.0 Side 2: 9.0 Area: 40.5
Circle Radius: 4.0 Area: 50.26548245743669
Circle Radius: 7.0 Area: 153.93804002589985
Circle Radius: 8.0 Area: 201.06192982974676
Circle Radius: 9.0 Area: 254.46900494077323
Printing post-order
Right Triangle Side 1: 2.0 Side 2: 2.0 Area: 2.0
Circle Radius: 2.0 Area: 12.566370614359172
Rectangle Side 1: 9.0 Side 2: 2.0 Area: 18.0
Right Triangle Side 1: 5.0 Side 2: 6.0 Area: 15.0
Rectangle Side 1: 2.0 Side 2: 7.0 Area: 14.0
Right Triangle Side 1: 3.0 Side 2: 2.0 Area: 3.0
Rectangle Side 1: 3.0 Side 2: 8.0 Area: 24.0
Right Triangle Side 1: 9.0 Side 2: 9.0 Area: 40.5
Rectangle Side 1: 5.0 Side 2: 5.0 Area: 25.0
Circle Radius: 7.0 Area: 153.93804002589985
Circle Radius: 9.0 Area: 254.46900494077323
Circle Radius: 8.0 Area: 201.06192982974676
Circle Radius: 4.0 Area: 50.26548245743669
Rectangle Side 1: 5.0 Side 2: 4.0 Area: 20.0
The max area is: 254.46900494077323
Deleting Rectangle Side 1: 2.0 Side 2: 7.0 Area: 14.0
Printing in-order
Right Triangle Side 1: 2.0 Side 2: 2.0 Area: 2.0
Right Triangle Side 1: 3.0 Side 2: 2.0 Area: 3.0
Circle Radius: 2.0 Area: 12.566370614359172
Right Triangle Side 1: 5.0 Side 2: 6.0 Area: 15.0
Rectangle Side 1: 9.0 Side 2: 2.0 Area: 18.0
Rectangle Side 1: 5.0 Side 2: 4.0 Area: 20.0
Rectangle Side 1: 3.0 Side 2: 8.0 Area: 24.0
Rectangle Side 1: 5.0 Side 2: 5.0 Area: 25.0
Right Triangle Side 1: 9.0 Side 2: 9.0 Area: 40.5
Circle Radius: 4.0 Area: 50.26548245743669
Circle Radius: 7.0 Area: 153.93804002589985
Circle Radius: 8.0 Area: 201.06192982974676
Circle Radius: 9.0 Area: 254.46900494077323
Deleting values larger than 30
Printing in order
Right Triangle Side 1: 2.0 Side 2: 2.0 Area: 2.0
Right Triangle Side 1: 3.0 Side 2: 2.0 Area: 3.0
Circle Radius: 2.0 Area: 12.566370614359172
Right Triangle Side 1: 5.0 Side 2: 6.0 Area: 15.0
Rectangle Side 1: 9.0 Side 2: 2.0 Area: 18.0
Rectangle Side 1: 5.0 Side 2: 4.0 Area: 20.0
Rectangle Side 1: 3.0 Side 2: 8.0 Area: 24.0
Rectangle Side 1: 5.0 Side 2: 5.0 Area: 25.0
Explanation / Answer
SourceCode:
class lNode {
lNode lLeft, lRight;
int side1,side2,radius;
String shapeType;
double area;
public lNode()
{
lLeft = null;
lRight = null;
shapeType="";
area = 0;
side1=side2=radius=0;
}
/*Parameterized Constructor*/
public lNode(double a,String st,int s1,int s2,int r)
{
lLeft = null;
lRight = null;
area = a;
shapeType=st;
side1=s1;
side2=s2;
radius=r;
}
/* Method to set the lLeft node */
public void setLeft(lNode n)
{
lLeft = n;
}
/* Method to set the lRight node */
public void setRight(lNode n)
{
lRight = n;
}
/* Method to get the lLeft node */
public lNode getLeft()
{
return lLeft;
}
/* Method to get the lRight node */
public lNode getRight()
{
return lRight;
}
/* Method to set the data */
public void setData(double d)
{
area = d;
}
/* Method to get the data */
public double getArea()
{
return area;
}
public String getShapeType(){
return shapeType;
}
public int getSide1(){
return side1;
}
public int getSide2(){
return side2;
}
public int getRadius(){
return radius;
}
}
class BinarySearchTree
{
private lNode root;
public BinarySearchTree()
{
root = null;
}
/* Method to check emptiness of tree */
public boolean isEmpty()
{
//Check for null
return root == null;
}
/* Method to insert the data */
public void insert(double area,String shapeType,int side1,int side2,int radius)
{
// Data insertion
root = insert(root, area,shapeType,side1,side2,radius);
}
/* Method to insert the data */
private lNode insert(lNode node, double area,String shapeType,int side1,int side2,int radius)
{
if (node == null)
// new node
node = new lNode(area,shapeType,side1,side2,radius);
else
{
if (area <= node.getArea())
node.lLeft = insert(node.lLeft, area,shapeType,side1,side2,radius);
else
node.lRight = insert(node.lRight, area,shapeType,side1,side2,radius);
}
return node;
}
/* Method for inorder traversal */
public void inorder()
{
//Inorder
inorder(root);
}
private void inorder(lNode r)
{
// Recursive
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getShapeType()+" ");
if(r.getShapeType().equals("Rectangle")||r.getShapeType().equals("Right Triangle")){
System.out.print(" Side 1: "+(double)r.getSide1()+" Side 2: "+(double)r.getSide2()+" ");
}
if(r.getShapeType().equals("Circle")){
System.out.print(" Radius: "+(double)r.getRadius()+" ");
}
System.out.print("Area: "+r.getArea() +" ");
inorder(r.getRight());
}
}
/* Method for traversing in preorder */
public void preorder()
{
//Preorder
preorder(root);
}
private void preorder(lNode r)
{
// Recursive
if (r != null)
{
System.out.print(r.getShapeType()+" ");
if(r.getShapeType().equals("Rectangle")||r.getShapeType().equals("Right Triangle")){
System.out.print(" Side 1: "+(double)r.getSide1()+" Side 2: "+(double)r.getSide2()+" ");
}
if(r.getShapeType().equals("Circle")){
System.out.print(" Radius: "+(double)r.getRadius()+" ");
}
System.out.print("Area: "+r.getArea() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Method for traversing in postorder */
public void postorder()
{
// Postorder
postorder(root);
}
private void postorder(lNode r)
{
//Recursive
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getShapeType()+" ");
if(r.getShapeType().equals("Rectangle")||r.getShapeType().equals("Right Triangle")){
System.out.print(" Side 1: "+(double)r.getSide1()+" Side 2: "+(double)r.getSide2()+" ");
}
if(r.getShapeType().equals("Circle")){
System.out.print(" Radius: "+(double)r.getRadius()+" ");
}
System.out.print("Area: "+r.getArea() +" ");
}
}
}
class BSTDriver:-
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class BSTDriver {
public static void main(String[] args)
{
File file=new File("d:\data.txt");
Scanner fs=null;
String shapeType;
int side1,side2,radius;
try {
fs = new Scanner(file);
} catch (FileNotFoundException e) {
e.printStackTrace();
}
/* Create object of the Binary Search Tree */
BinarySearchTree bst = new BinarySearchTree();
System.out.println("Reading from file");
while(fs.hasNext()){
shapeType=fs.next();
if(shapeType.equals("Rectangle")){
side1=fs.nextInt();
side2=fs.nextInt();
System.out.println("Rectangle "+side1+" "+side2);
bst.insert(side1*side2,"Rectangle",side1,side2,0);
}
if(shapeType.equals("Right")){
fs.next();
side1=fs.nextInt();
side2=fs.nextInt();
System.out.println("Right Triangle "+side1+" "+side2 );
bst.insert(0.5*side1*side2,"Right Triangle",side1,side2,0);
}
if(shapeType.equals("Circle")){
radius=fs.nextInt();
System.out.println("Circle "+radius);
bst.insert(3.1412*radius*radius,"Circle",0,0,radius);
}
}
System.out.println("");
System.out.println("Printing Post order : ");
bst.postorder();
System.out.println("");
System.out.println("Printing Pre order : ");
bst.preorder();
System.out.println("");
System.out.println("Printing In order : ");
bst.inorder();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.