*In java please* Objective: Write a program which creates a binary search tree o
ID: 645542 • Letter: #
Question
*In java please*
Objective:
Write a program which creates a binary search tree of different shapes from a file.
The comparison is based on the shapes 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 thats 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.
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
class Node:-
class Node {
Node left, right;
int side1,side2,radius;
String shapeType;
double area;
/*Constructor*/
public Node()
{
left = null;
right = null;
shapeType="";
area = 0;
side1=side2=radius=0;
}
/*Parameterized Constructor*/
public Node(double a,String st,int s1,int s2,int r)
{
left = null;
right = null;
area = a;
shapeType=st;
side1=s1;
side2=s2;
radius=r;
}
/* Method to set the left node */
public void setLeft(Node n)
{
left = n;
}
/* Method to set the right node */
public void setRight(Node n)
{
right = n;
}
/* Method to get the left node */
public Node getLeft()
{
return left;
}
/* Method to get the right node */
public Node getRight()
{
return right;
}
/* Method to set the data to node */
public void setData(double d)
{
area = d;
}
/* Method to get the data from node */
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:-
class BinarySearchTree
{
private Node root;
/* Constructor*/
public BinarySearchTree()
{
root = null;
}
/* Method to check if the tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Method to insert the data */
public void insert(double area,String shapeType,int side1,int side2,int radius)
{
root = insert(root, area,shapeType,side1,side2,radius);
}
/* Method to insert the data recursively */
private Node insert(Node node, double area,String shapeType,int side1,int side2,int radius)
{
if (node == null)
node = new Node(area,shapeType,side1,side2,radius);
else
{
if (area <= node.getArea())
node.left = insert(node.left, area,shapeType,side1,side2,radius);
else
node.right = insert(node.right, area,shapeType,side1,side2,radius);
}
return node;
}
/* Method for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(Node r)
{
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 preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(Node r)
{
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 postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(Node r)
{
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);
}
}
/*Display the tree*/
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.