How would I implement the following count method, given the following class spec
ID: 3725368 • Letter: H
Question
How would I implement the following count method, given the following class specs?
public class IntTree {
private class Node {
private int data;
private Node firstChild;
private Node sibling;
private Node parent;
private Node (int d, Node f, Node s, Node p) {
data = d;
firstChild = f;
sibling = s;
parent = p;
}
}
private Node root;
public IntTree(int d) {
//create a one node tree
root = addNode(root, d);
}
private Node addNode(Node currNode, int value) {
//Add a Node to the tree
if(currNode == null) {
return new Node(value, null, null, null);
}
if(value < currNode.data) {
currNode.firstChild = addNode(currNode.firstChild, value);
}
else if(value > currNode.data) {
currNode.sibling = addNode(currNode.sibling, value);
}
return currNode;
}
//IMPLEMENT COUNT METHOD
public int count(int d) {
//return the number of times d appears in the tree
//the implementation must be recursive
}
}
Explanation / Answer
public class IntTree { private class Node { private int data; private Node firstChild; private Node sibling; private Node parent; private Node (int d, Node f, Node s, Node p) { data = d; firstChild = f; sibling = s; parent = p; } } private Node root; public IntTree(int d) { //create a one node tree root = addNode(root, d); } private Node addNode(Node currNode, int value) { //Add a Node to the tree if(currNode == null) { return new Node(value, null, null, null); } if(value currNode.data) { currNode.sibling = addNode(currNode.sibling, value); } return currNode; } //IMPLEMENT COUNT METHOD public int count(int d) { //return the number of times d appears in the tree //the implementation must be recursive return countHelper(root, d); } private int countHelper(Node node, int d) { if(node == null) { return 0; } else { return (node.data == d ? 1 : 0) + countHelper(node.firstChild, d) + countHelper(node.sibling, d); } } }Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.