Shape Tree in JAVA PLEASE HAVE COMMENTS IN CODE Objective: Write a program which
ID: 3680610 • Letter: S
Question
Shape Tree in JAVA
PLEASE HAVE COMMENTS IN CODE
Objective:
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.
The shape file is a text file that is exactly as below:
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
public class BinaryTree {
Node root;
public void addNode(int key, String name) {
// Create a new Node and initialize it
Node newNode = new Node(key, name);
// If there is no root this becomes root
if (root == null) {
root = newNode;
} else {
// Set root as the Node we will start
// with as we traverse the tree
Node focusNode = root;
// Future parent for our new Node
Node parent;
while (true) {
// root is the top parent so we start
// there
parent = focusNode;
// Check if the new node should go on
// the left side of the parent node
if (key < focusNode.key) {
// Switch focus to the left child
focusNode = focusNode.leftChild;
// If the left child has no children
if (focusNode == null) {
// then place the new node on the left of it
parent.leftChild = newNode;
return; // All Done
}
} else { // If we get here put the node on the right
focusNode = focusNode.rightChild;
// If the right child has no children
if (focusNode == null) {
// then place the new node on the right of it
parent.rightChild = newNode;
return; // All Done
}
}
}
}
}
// All nodes are visited in ascending order
// Recursion is used to go to one node and
// then go to its child nodes and so forth
public void inOrderTraverseTree(Node focusNode) {
if (focusNode != null) {
// Traverse the left node
inOrderTraverseTree(focusNode.leftChild);
// Visit the currently focused on node
System.out.println(focusNode);
// Traverse the right node
inOrderTraverseTree(focusNode.rightChild);
}
}
public void preorderTraverseTree(Node focusNode) {
if (focusNode != null) {
System.out.println(focusNode);
preorderTraverseTree(focusNode.leftChild);
preorderTraverseTree(focusNode.rightChild);
}
}
public void postOrderTraverseTree(Node focusNode) {
if (focusNode != null) {
postOrderTraverseTree(focusNode.leftChild);
postOrderTraverseTree(focusNode.rightChild);
System.out.println(focusNode);
}
}
public Node findNode(int key) {
// Start at the top of the tree
Node focusNode = root;
// While we haven't found the Node
// keep looking
while (focusNode.key != key) {
// If we should search to the left
if (key < focusNode.key) {
// Shift the focus Node to the left child
focusNode = focusNode.leftChild;
} else {
// Shift the focus Node to the right child
focusNode = focusNode.rightChild;
}
// The node wasn't found
if (focusNode == null)
return null;
}
return focusNode;
}
public static void main(String[] args) {
BinaryTree theTree = new BinaryTree();
theTree.addNode(50, "Boss");
theTree.addNode(25, "Vice President");
theTree.addNode(15, "Office Manager");
theTree.addNode(30, "Secretary");
theTree.addNode(75, "Sales Manager");
theTree.addNode(85, "Salesman 1");
// Different ways to traverse binary trees
// theTree.inOrderTraverseTree(theTree.root);
// theTree.preorderTraverseTree(theTree.root);
// theTree.postOrderTraverseTree(theTree.root);
// Find the node with key 75
System.out.println(" Node with the key 75");
System.out.println(theTree.findNode(75));
}
}
class Node {
int key;
String name;
Node leftChild;
Node rightChild;
Node(int key, String name) {
this.key = key;
this.name = name;
}
public String toString() {
return name + " has the key " + key;
/*
* return name + " has the key " + key + " Left Child: " + leftChild +
* " Right Child: " + rightChild + " ";
*/
}
}
note-the above cose is for binary search tree in java, this code can help to solve the given query.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.