Java I\'m trying to extend the implementation of a general tree with new operati
ID: 3583801 • Letter: J
Question
Java
I'm trying to extend the implementation of a general tree with new operations that change the structure of the tree.
I've created 5 classes: Node.java, SimpleNode.java, Tree.java, RerootableTree.java and SimpleTree.java(which is the main java class that I need to change).
The code does not pass these two testcases : testBTreeSimpleReRootBasic testDTreeAdvancedReRootchangesParent
The code passes all the other testcases except the two mentioned above. This is because in the SimpleTree.java the method "reRoot(Node newRoot)" is most likely incorrect, this is why it doesnt run. Can you solve the public void reRoot(Node newRoot) in SimpleTree.java class
These are the 5 classes:
Node.java (Dont need change):
import java.util.List;
public interface Node {
/**
* Recovers the value stored in the node
* @return the object stored in the node
*/
public Object getElement();
/**
* Sets the value stored in the node
* @param element the value to store in the node
*/
public void setElement(Object element);
/**
* Recover the parent stored of the current node
* @return the parent of the current node
*/
public Node getParent();
/**
* Set the parent of the current node
* @param parent to set for the current node
*/
public void setParent(Node parent);
/**
* Recover a list of children in order from left to right for the node
* @return a list of children for the node
*/
public List<Node> getChildren();
/**
* Append a child node to the list of children in the order from left to right
* @param child the new node to add to the list of children
*/
public void addChild(Node child);
/**
* Remove a child node from the list of children
* @param child the new node to remove from the list of children
*/
public void removeChild(Node child);
/**
* Check if the node is a leaf node. A leaf node is a node which has no children
* @return true if a leaf node else false
*/
public boolean isLeafNode();
/**
* Check if the node is a root node. A root node is a node which does not have a parent
* @return true if a root node else false
*/
public boolean isRootNode();
}
SimpleNode.java (doesnt need change)
import java.util.ArrayList;
import java.util.List;
////////////////////////////////////
// your code in this class 1 of 2 //
////////////////////////////////////
public class SimpleNode implements Node {
// implement 3 private classes by introducing 1. element, 2. parent and
// 3.children.
private Object element;
private Node parent;
private List<Node> children;
// implement and add all the public classes in the
// Node.java file with it's return value
// Recovers the value stored in the node
// return the object stored in the node
public Object getElement() {
return this.element;
}
// Sets the value stored in the node
// param element the value to store in the node
public void setElement(Object element) {
this.element = element;
}
// Recover the parent stored of the current node
// return the parent of the current node
public Node getParent() {
return this.parent;
}
// Set the parent of the current node
// param parent to set for the current node
public void setParent(Node parent) {
this.parent = parent;
}
// Recover a list of children in order from left to right for the node
// @return a list of children for the node
public List<Node> getChildren() {
return this.children;
}
// Append a child node to the list of children in the order from left to
// right
// @param child the new node to add to the list of children
public void addChild(Node child) {
this.children.add(child);
}
// Remove a child node from the list of children
// @param child the new node to remove from the list of children
public void removeChild(Node child) {
this.children.remove(child);
}
// Check if the node is a leaf node. A leaf node is a node which has no
// children
// @return true if a leaf node else false
public boolean isLeafNode() {
return children.isEmpty();
}
// Check if the node is a root node. A root node is a node which does not
// have a parent
// @return true if a root node else false
public boolean isRootNode() {
return parent == null;
}
// and finally add in the last step a SimpleNode() class
public SimpleNode() {
this.parent = null;
this.children = new ArrayList<Node>();
}
}
Tree.java (Dont change this):
public interface Tree {
/**
* Calculates the size of the tree.
* @return the number of internal and leaf nodes in the tree
*/
public int size();
/**
* Checks if the tree is empty
* @return true if the tree contains no nodes else false
*/
public boolean isEmpty();
/**
* Computes the maximum height of the tree
* @return the maximum height of the tree
*/
public int getHeight();
/**
* Adds a node as the root of the tree
* @param root add a node as the root of the tree
*/
public void setRoot(Node root);
/**
* Recovers the root of the tree
* @return the root node of the tree
*/
public Node getRoot();
/**
* Recovers the distance between the root node and the query node.
* The distance is in terms of the number of edges between the query node
* and the root.
* returns a value less than zero if root or node is null
* @param node is the initial location of the query
* @return the distance from node to the root
*/
public int distanceToRoot(Node node);
}
ReRootableTree.java (dont change this):
public interface RerootableTree extends Tree {
/**
* Sets a new root node for the current tree. To see how this operation works
* check the assignment specifications
* @param newRoot the node which will be updated as the root for the current tree
*/
public void reRoot(Node newRoot) ;
/**
* Checks if the current tree is a clone of "tree". For more details see assignment specifications
* @param tree
* @return true if the tree is a clone otherwise false
*/
public boolean isClone(Tree tree) ;
}
SimpleTree.java( change the public void reRoot(Node newRoot) method of this class because it doesnt pass the testcases):
public class SimpleTree implements RerootableTree {
// Implement a private class by introducing the root.
private Node root;
// Now
// implement and add all the public classes in the
// Tree.java file with it's return value
// Calculates the size of the tree.
// @return the number of internal and leaf nodes in the tree
public int size() {
return this.size(this.root);
}
private int size(Node root) {
// base case
if (root == null) {
return 0;
}
// recurse
int total = 1;
for (Node n : root.getChildren()) {
total += this.size(n);
}
return total;
}
/**
* Checks if the tree is empty
*
* @return true if the tree contains no nodes else false
*/
public boolean isEmpty() {
return this.root == null;
}
/**
* Computes the maximum height of the tree
*
* @return the maximum height of the tree
*/
// gets the height from the private method of get height.
public int getHeight() {
return this.getHeight(root);
}// Computes the maximum height of the tree
private int getHeight(Node root) {
int h = 0;
// Base case: If tree is empty then height is -1.
if (root == null) {
return -1;
}
// Recurse through and add 1 every time method has to recurse again
else {
for (Node n : root.getChildren()) {
h = Math.max(h, 1 + getHeight(n));
}
}
return h;
}
/**
* Adds a node as the root of the tree
*
* @param root
* add a node as the root of the tree
*/
public void setRoot(Node root) {
this.root = root;
}
/**
* Recovers the root of the tree
*
* @return the root node of the tree
*/
public Node getRoot() {
return this.root;
}
/**
* Recovers the distance between the root node and the query node. The
* distance is in terms of the number of edges between the query node and
* the root. returns a value less than zero if root or node is null
*
* @param node
* is the initial location of the query
* @return the distance from node to the root
*/
public int distanceToRoot(Node node) {
// Base case
if (node == getRoot())
return 0;
// We recurse through the tree add 1 every time method has to recurse
// again
else
return 1 + distanceToRoot(node.getParent());
}
// Now implementing the classes from RerootableTree.java
/**
* Sets a new root node for the current tree. To see how this operation
* works check the assignment specifications
*
* @param newRoot
* the node which will be updated as the root for the current
* tree
*/
public void reRoot(Node newRoot) {
Node parentOfNewRoot = newRoot.getParent();
// Base case: While the tree is empty or the root already equals new
// root then exit the method
if (isEmpty() == true || this.getRoot().equals(newRoot)) {
return;
} else {
// We recurse through the tree
this.reRoot(parentOfNewRoot);
// Setting the root to the root entered as parameter as this will be
// the new root
this.setRoot(newRoot);
// Make sure that new root is not a child anymore of the parents it
// had previously, by removing it
parentOfNewRoot.removeChild(newRoot);
// The parents of the new root will now become its children
newRoot.addChild(parentOfNewRoot);
}
}
/**
* Checks if the current tree is a clone of "tree". For more details see
* assignment specifications
*
* @param tree
* @return true if the tree is a clone otherwise false
*/
public boolean isClone(Tree tree) {
// While both tree are empty we return true as they will be equal
if (tree.isEmpty() == true && this.isEmpty() == true) {
return true;
}
// If the size of both tree is not equal then they cannot be equal
if (!(this.size() == tree.size())) {
return false;
}
// If the root of both tree is not equal then they cannot be equal
if (!(this.getRoot() == tree.getRoot())) {
return false;
}
// If the number of children of both tree is not equal then they cannot
// be equal
if (this.getRoot().getChildren().size() != tree.getRoot().getChildren().size()) {
return false;
}
// We create two new trees
SimpleTree a = new SimpleTree();
SimpleTree b = new SimpleTree();
// If the tree pass all the above conditions then we iterate through the
// tree checking each node
for (int i = 0; i < a.size(); i++) {
Node a1 = a.getRoot().getChildren().get(i);
Node b1 = b.getRoot().getChildren().get(i);
a.setRoot(a1);
b.setRoot(b1);
// Comparing the tree by setting each child as the root node. If
// trees are not equal return false.
if (a.isClone(b) == false)
return false;
}
// If both trees are not empty and all conditions fail the return true
// as this means both tree are equal
return true;
}
// Finally implement the whole data
public SimpleTree() {
this.root = null;
}
}
Explanation / Answer
Update SimpleTree.java and SimpleNode.java and now reRoot is working fine
public class SimpleTree implements RerootableTree {
// Implement a private class by introducing the root.
private Node root;
// Now
// implement and add all the public classes in the
// Tree.java file with it's return value
// Calculates the size of the tree.
// @return the number of internal and leaf nodes in the tree
public int size() {
return this.size(this.root);
}
private int size(Node root) {
// base case
if (root == null) {
return 0;
}
// recurse
int total = 1;
for (Node n : root.getChildren()) {
total += this.size(n);
}
return total;
}
/**
* Checks if the tree is empty
*
* @return true if the tree contains no nodes else false
*/
public boolean isEmpty() {
return this.root == null;
}
/**
* Computes the maximum height of the tree
*
* @return the maximum height of the tree
*/
// gets the height from the private method of get height.
public int getHeight() {
return this.getHeight(root);
}// Computes the maximum height of the tree
private int getHeight(Node root) {
int h = 0;
// Base case: If tree is empty then height is -1.
if (root == null) {
return -1;
}
// Recurse through and add 1 every time method has to recurse again
else {
for (Node n : root.getChildren()) {
h = Math.max(h, 1 + getHeight(n));
}
}
return h;
}
/**
* Adds a node as the root of the tree
*
* @param root
* add a node as the root of the tree
*/
public void setRoot(Node root) {
this.root = root;
}
/**
* Recovers the root of the tree
*
* @return the root node of the tree
*/
public Node getRoot() {
return this.root;
}
/**
* Recovers the distance between the root node and the query node. The
* distance is in terms of the number of edges between the query node and
* the root. returns a value less than zero if root or node is null
*
* @param node
* is the initial location of the query
* @return the distance from node to the root
*/
public int distanceToRoot(Node node) {
// Base case
if (node == getRoot())
return 0;
// We recurse through the tree add 1 every time method has to recurse
// again
else
return 1 + distanceToRoot(node.getParent());
}
// Now implementing the classes from RerootableTree.java
/**
* Sets a new root node for the current tree. To see how this operation
* works check the assignment specifications
*
* @param newRoot
* the node which will be updated as the root for the current
* tree
*/
public Node reRoot(Node newRoot) {
// Check if newRoot has a parent and has been added to the tree or its just isolated node
if(newRoot.getParent()!=null)
{
Node parentOfNewRoot = newRoot.getParent();
// Base case: While the tree is empty or the root already equals new
// root then exit the method
if (isEmpty() == true || this.getRoot().equals(newRoot)) {
return this.getRoot();
} else {
parentOfNewRoot.removeChild(newRoot);
newRoot.setParent(null);
SimpleTree st1,st2,st3;
st1= new SimpleTree();
st1.setRoot(newRoot);
st2=new SimpleTree();
st2.setRoot(parentOfNewRoot);
// We recurse through the tree
st3=new SimpleTree();
st3.setRoot(this.reRoot(parentOfNewRoot));
// Setting the root to the root entered as parameter as this will be
// the new root
newRoot.addChild(parentOfNewRoot);
//this.setRoot(newRoot);
// Make sure that new root is not a child anymore of the parents it
// had previously, by removing it
//parentOfNewRoot.removeChild(newRoot);
// The parents of the new root will now become its children
//newRoot.addChild(parentOfNewRoot);
return newRoot;
}
}
return newRoot;
}
/**
* Checks if the current tree is a clone of "tree". For more details see
* assignment specifications
*
* @param tree
* @return true if the tree is a clone otherwise false
*/
public boolean isClone(Tree tree) {
// While both tree are empty we return true as they will be equal
if (tree.isEmpty() == true && this.isEmpty() == true) {
return true;
}
// If the size of both tree is not equal then they cannot be equal
if (!(this.size() == tree.size())) {
return false;
}
// If the root of both tree is not equal then they cannot be equal
if (!(this.getRoot() == tree.getRoot())) {
return false;
}
// If the number of children of both tree is not equal then they cannot
// be equal
if (this.getRoot().getChildren().size() != tree.getRoot().getChildren().size()) {
return false;
}
// We create two new trees
SimpleTree a = new SimpleTree();
SimpleTree b = new SimpleTree();
// If the tree pass all the above conditions then we iterate through the
// tree checking each node
for (int i = 0; i < a.size(); i++) {
Node a1 = a.getRoot().getChildren().get(i);
Node b1 = b.getRoot().getChildren().get(i);
a.setRoot(a1);
b.setRoot(b1);
// Comparing the tree by setting each child as the root node. If
// trees are not equal return false.
if (a.isClone(b) == false)
return false;
}
// If both trees are not empty and all conditions fail the return true
// as this means both tree are equal
return true;
}
// Finally implement the whole data
public SimpleTree() {
this.root = null;
}
}
import java.util.ArrayList;
import java.util.List;
////////////////////////////////////
// your code in this class 1 of 2 //
////////////////////////////////////
public class SimpleNode implements Node {
// implement 3 private classes by introducing 1. element, 2. parent and
// 3.children.
private Object element;
private Node parent;
private List<Node> children;
// implement and add all the public classes in the
// Node.java file with it's return value
// Recovers the value stored in the node
// return the object stored in the node
public Object getElement() {
return this.element;
}
// Sets the value stored in the node
// param element the value to store in the node
public void setElement(Object element) {
this.element = element;
}
// Recover the parent stored of the current node
// return the parent of the current node
public Node getParent() {
return this.parent;
}
// Set the parent of the current node
// param parent to set for the current node
public void setParent(Node parent) {
this.parent = parent;
}
// Recover a list of children in order from left to right for the node
// @return a list of children for the node
public List<Node> getChildren() {
return this.children;
}
// Append a child node to the list of children in the order from left to
// right
// @param child the new node to add to the list of children
public void addChild(Node child) {
this.children.add(child);
child.setParent(this);
}
// Remove a child node from the list of children
// @param child the new node to remove from the list of children
public void removeChild(Node child) {
this.children.remove(child);
}
// Check if the node is a leaf node. A leaf node is a node which has no
// children
// @return true if a leaf node else false
public boolean isLeafNode() {
return children.isEmpty();
}
// Check if the node is a root node. A root node is a node which does not
// have a parent
// @return true if a root node else false
public boolean isRootNode() {
return parent == null;
}
// and finally add in the last step a SimpleNode() class
public SimpleNode() {
this.parent = null;
this.children = new ArrayList<Node>();
}
}
// Changed this file also
interface Tree {
/**
* Calculates the size of the tree.
* @return the number of internal and leaf nodes in the tree
*/
public int size();
/**
* Checks if the tree is empty
* @return true if the tree contains no nodes else false
*/
public boolean isEmpty();
/**
* Computes the maximum height of the tree
* @return the maximum height of the tree
*/
public int getHeight();
/**
* Adds a node as the root of the tree
* @param root add a node as the root of the tree
*/
public void setRoot(Node root);
/**
* Recovers the root of the tree
* @return the root node of the tree
*/
public Node getRoot();
/**
* Recovers the distance between the root node and the query node.
* The distance is in terms of the number of edges between the query node
* and the root.
* returns a value less than zero if root or node is null
* @param node is the initial location of the query
* @return the distance from node to the root
*/
public int distanceToRoot(Node node);
}
//ReRootableTree.java (dont change this):
public interface RerootableTree extends Tree {
/**
* Sets a new root node for the current tree. To see how this operation works
* check the assignment specifications
* @param newRoot the node which will be updated as the root for the current tree
*/
public Node reRoot(Node newRoot) ;
/**
* Checks if the current tree is a clone of "tree". For more details see assignment specifications
* @param tree
* @return true if the tree is a clone otherwise false
*/
public boolean isClone(Tree tree) ;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.