I have a function, the function is printing a node like this, it look like file directory structure
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 my code for this function
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 ")");
}
}
}
}
}
}
}
I'll include the Node Object maybe it'll help to understand it,
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 the code is very dirty, I want to add a recursive function but I still don't understand how to do it, do u guys have some advice on how to tidy it? thanks in advance
CodePudding user response：
You can do it using recursion. Rather than try to reconstruct your data in all its complexity I created a simple example using my own node class.
class MyNode {
String name;
List<MyNode> nodeList;
public MyNode(String name) {
this.name = name;
}
public MyNode setNodeList(List<MyNode> list) {
nodeList = list;
return this;
}
@Override
public String toString() {
return name;
}
public List<MyNode> getNodeList() {
return nodeList;
}
}
MyNode m = new MyNode("a");
List<MyNode> list1 =
List.of(new MyNode("aaa"), new MyNode("aab"),
new MyNode("aac"), new MyNode("aad"));
List<MyNode> list2 = List.of(new MyNode("aba"),
new MyNode("abb"), new MyNode("abc"));
List<MyNode> list3 = List.of(new MyNode("aca"),
new MyNode("acb"), new MyNode("acc"));
List<MyNode> list4 = List.of(new MyNode("ada"),
new MyNode("adb"), new MyNode("adc"));
List<MyNode> mainlist = List.of(new MyNode("aa").setNodeList(list1),
new MyNode("ab").setNodeList(list2), new MyNode("ac").setNodeList(list3), new MyNode("ad").setNodeList(list4));
m.setNodeList(mainlist);
print(m,1);
prints
--a
----aa
------aaa
------aab
------aac
------aad
----ab
------aba
------abb
------abc
----ac
------aca
------acb
------acc
----ad
------ada
------adb
------adc
- this works by having the print method calling itself and adjusting the indentation level.
- The current node and level are printed.
- if that node's list is non-null, then the print method is called for each node in the list and the process repeated, updating the level.
- upon each return, the method starts where it left off as it continues to call itself and return.
- This is a common process for walking thru hie-rarchical data sets and will work with an indeterminate amount of levels.
public static void print(MyNode node, int level) {
System.out.println("-".repeat(level*2) node);
if (node.getNodeList() != null) {
for (MyNode n : node.getNodeList()) {
print(n, level 1);
}
}
}
I recommend you read up on recursive processes. In some cases you can also return values as you traverse the hierarchy.
CodePudding user response：
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.