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?
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 guess that your program might be a school exercise, I'll avoid discussing what could be a better implementation of your Node class. Surely, using a List from the Collections framework would have been a better choice rather than a fixed array of 100 elements, but I guess that your teacher wanted to keep things simple, or you might have not covered the Collections framework yet.
Anyway, here I've attached a solution to show how your recursive print could work. Bear in mind that I've split the print implementation into two methods, only to make its invocation easier for the client. In fact, a client of your code should not be aware, nor be bothered, with the internal implementation details to use your code.
//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 to compute the effective number of children
// when an array is passed to 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 added a couple of side notes:
children is already the plural of child. You don't need to call your array childrens.
Your implementation of the add method could throw an ArraIndexOutOfBoundsException, if more than 100 elements were added. Usually, when an operation could fail, the method should return a boolean to tell the client whether the operation succeeded or not.