Parent-Child Tree in Java-CodePudding

I was trying to implement a class Node to build a tree of Nodes. Basically, each Node can have children, so if I specify multiple nodes I can build a tree out of it. As an example:

node1 (the root) has node2 and node3 as children
node2 has node4 and node5 as children

The problem I am having problems to solve is to build this tree and find all children of a given element (in this case node1 would have 4 children, since it has node2 and node3 in the first place, and node2 has 2 children, so in total 4). Does anyone have any suggestion?

CodePudding user response：

Here is some sample code that could help (explanation below):

Main class:

class Main {
  public static void main(String[] args) {
    Node v1 = new Node(1);
    Node v2 = new Node(2);
    Node v3 = new Node(3);
    Node v4 = new Node(4);
    Node v5 = new Node(5);
    v1.addChild(v2);
    v1.addChild(v3);
    v2.addChild(v4);
    v2.addChild(v5);
    v1.printChildren();
  }
}

Node class:

import java.util.*;
class Node{
  private int val;
  private ArrayList<Node> children = new ArrayList<Node>();
  public Node(int v){
    val = v;
  }
  public void addChild (Node c){
    children.add(c);
  }
  public void printChildren(){
    if (children.size() != 0){
      System.out.print("Children of Node "   getValue()   ": ");
      for(Node c: children){
        System.out.print("Node "   c.getValue()   " ");
      }
      System.out.println();
      for(Node c: children){
        c.printChildren();
      }
    }
  }
  public int getValue(){
    return val;
  }
}

Output:

Children of Node 1: Node 2 Node 3 
Children of Node 2: Node 4 Node 5

Ok so in our node class, let's say each node will have an integer value, val. That is our first private instance variable. Second, each node will have a list of children nodes, children.

When we first declare our nodes, they will have integer values, as shown in our constructor.

After we define our nodes, we can add some nodes as children to other nodes (v2 and v3 are children to v1, and v4 and v5 are children to v2).

Now we need to print them. We will use a recursive approach for this. If the node we are printing the children of has children (the length of our children ArrayList is nonzero), then we will first iterate through that list, and print out the children of our current node. Afterwards, we again iterate through each child and use the same method (recursion) to print out the children of that node.

I hope this helped! Please let me know if you need any further help or clarification :)

CodePudding user response：

For your requirement, depth-first or breadth-first will fit to find children of the tree/node. There are already tons of discussions around these algorithms. For instance:

Breadth First Search and Depth First Search

You are already thinking on right direction related to its DataStructure. One thing I would suggest use java generics so that it can support multiple data-type base on need.

class Node<T> {
    
    T value;
    List<T> children;
    
    Node(T t) {
        this.value = t;
        children = new ArrayList<T>();
    }
    
    void addChild(T child) {
        children.add(child);
    }
}