I have a Node class used to represent a tree structure. Within this class, I’ve defined a print method that should yield the following output:
data --a (1024) --b (256) ----ba (100) ------baa (500) ------bac (25) ----bc (150) ----bd (125) ----be (75) --c (35) ----cb (30) ----ce (50)
This is how I’ve written my print method:
public void print(String name) {
Node node = this.find(name);
System.out.println(node.name);
if (node.childrensCount != 0) {
for (int i = 0; i < node.childrensCount; i++) {
Node children = node.childrens[i];
System.out.println("--" + children.name + " (" + children.value + ")");
if (children.childrensCount != 0) {
for (int j = 0; j < children.childrensCount; j++) {
Node grandChildren = children.childrens[j];
System.out.println("----" + grandChildren.name + " (" + grandChildren.value + ")");
if (grandChildren.childrensCount != 0) {
for (int k = 0; k < grandChildren.childrensCount; k++) {
Node greatGrandChildren = grandChildren.childrens[k];
System.out.println("------" + greatGrandChildren.name + " (" + greatGrandChildren.value + ")");
}
}
}
}
}
}
}
This is also the Node class implementation to better help you in understanding the scenario:
public class Node {
int value;
String name;
Node parent;
int childrensCount;
Node[] childrens = new Node[100];
public Node(int value, String name) {
this.value = value;
this.name = name;
this.childrensCount = 0;
}
public Node(String name) {
this.name = name;
}
public void addChildren(Node node)
{
this.childrens[childrensCount] = node;
childrensCount++;
}
public void setParent(Node parent)
{
this.parent = parent;
}
public boolean hasParent(){
return this.parent != null;
}
public int sumValue(){
int sum = 0;
sum += this.value;
for (int i = 0; i < childrensCount; i++) {
sum += childrens[i].value;
}
return sum;
}
}
I think my code is quite dirty and can be improved. I’d like to define a recursive method but I still don’t understand how recursion works. Could someone help me with that?
Advertisement
Answer
To define a recursive method, you first need to identify your base cases and recursive cases. In this scenario, the base case is when the node passed for the printing is null while the recursive case is when there are still children to be printed.
Since I understand that your program might be a school exercise, I’ll avoid discussing what could be or could be not a better implementation of your Node class. Definitely, using a List data structure from the Collections framework would have been a better choice instead of a fixed array of 100 elements, but I think your teacher would like to keep things simple at the beginning and you most likely haven’t covered the Collections framework yet since you said you’re still struggling with recursion (which is totally fine, we all have to start somewhere!). So, I’ll leave your class implementation exactly how it is. I will just add few methods and some tweaks.
Here, I’ve implemented a solution to show you how your recursive print could work. Bear in mind that I’ve split the print implementation in two methods only to make its invocation easier for the client. In fact, a client should not be aware nor bothered with the internal implementation details of something to make it work.
//Test class
public class Test {
public static void main(String[] args) {
Node root = new Node(1, "test1", new Node[]{
new Node(2, "test2", new Node[]{
new Node(5, "test6", new Node[]{})
}),
new Node(3, "test3", new Node[]{
new Node(6, "test6", new Node[]{}),
new Node(7, "test7", new Node[]{
new Node(8, "test8", new Node[]{})
})
}),
new Node(4, "test4", new Node[]{})
});
root.print();
}
}
class Node {
int value;
String name;
Node parent;
int childrenCount;
Node[] children = new Node[100];
public Node(int value, String name) {
this.value = value;
this.name = name;
this.childrenCount = 0;
}
//Added second constructor only to ease the test
public Node(int value, String name, Node[] children) {
this.value = value;
this.name = name;
this.children = children;
this.childrenCount = getNumChildren(children);
}
public Node(String name) {
this.name = name;
}
//Fixed possible exception when added more than 100 elements
public boolean addChildren(Node node) {
if (childrenCount == this.children.length) {
return false;
}
this.children[childrenCount++] = node;
return true;
}
public void setParent(Node parent) {
this.parent = parent;
}
public boolean hasParent() {
return this.parent != null;
}
public int sumValue() {
int sum = 0;
sum += this.value;
for (int i = 0; i < childrenCount; i++) {
sum += children[i].value;
}
return sum;
}
//small utility method only to compute the effective number of children when an array is passed within the new constructor
public static int getNumChildren(Node[] children) {
int num = 0;
while (num < children.length && children[num] != null) {
num++;
}
return num;
}
//print method invoked by the client of the class
public void print() {
printRec(this, 0);
}
//recursive print
private void printRec(Node n, int numCall) {
//identifying the base case
if (n == null) {
return;
}
//Printing as many dahses as the depth of the current child node
for (int i = 1; i <= numCall; i++) {
System.out.print("--");
}
//printing the node info
System.out.println(n.name + " (" + n.value + ")");
//recursively invoking the print method for each child
for (int i = 0; i < n.childrenCount; i++) {
printRec(n.children[i], numCall + 1);
}
}
}
Here I just wanted to add a couple of side notes:
children is already the plural form of child. You don’t need to call your array childrens.
Your previous implementation of the add method could have raised an ArraIndexOutOfBoundsException, if you had added more than 100 elements. Usually, when an operation could fail, the method should return a boolean to tell the client whether the operation succeeded or not.