Создание дочерних узлов с использованием рекурсии

Question

Я пытаюсь создать иерархию из плоских данных. У меня есть следующий Node определение:

public class Node { 
     public String name; 
     public List<Node> children = new ArrayList<>(); 
    } 

Учитывая эти данные: [Person,Manager,Hourly,New], где дерево должно быть как:

Person 
    |--Manager 
     |--Hourly 
      |--New 

Я попытался следующие:

public void run() 
    { 
     List<List<String>> objects = new ArrayList<>(); 

     String[] str = {"Person","Manager","Hourly","New"}; 
     objects.add(Arrays.asList(str)) ; 

     String[] str2 = {"Person","Manager","Salary"}; 
     objects.add(Arrays.asList(str2)) ; 

     String[] str3 = {"Person","Manager","Salary", "New"}; 
     objects.add(Arrays.asList(str3)) ; 

     // Create a Node with the sequence 
     myNode = new Node(); 
     createNode(objects.get(0), 0, myNode, myNode); 
     LOG.debug(myNode.name); 
} 

И мой createNode способ:

public Node createNode(List<String> seq, Integer start, Node parentNode, Node childNode) 
    { 
     // do something and return a Node? 
    } 

Но концептуально я не понимаю, как поддерживать структуру, если Java возвращается по значению. Что я могу добавить к createNode, так что я могу добавить Manager-> Hourly-> Новую иерархии в детстве Person

Answer 1

Вам не нужен оба типа Node обратного иNode аргумента для вашего метода.

Вот один из способов сделать это:

//in run() 
myNode = new Node(); 
myNode.name = "Root"; 
createNode(objects.get(0), 0, myNode, myNode); 



public void createNode(List<String> seq, Integer start, Node parentNode) 
{ 
    Node childNode = new Node(); 
    childNode.name = seq[start]; 
    parentNode.children.Add(childNode); 
    createNode(seq, start+1, childNode); 
} 

Вам не нужно возвращать ничего из createNode() - поскольку у вас есть parentNode как переменные, вы можете добавить вещи к своему children члену. Вызов createNode() будет рекурсивно добавлять дочерние узлы, следуя за строкой массива до конца.

Другой способ сделать это так:

public Node createNode(List<String> seq, Integer start) 
{ 
    if (start >= seq.Length) { 
     return null; 
    } 
    Node node = new Node(); 
    node.name = seq[start]; 
    node.children.Add(createNode(seq, start+1); 

    return node; 
} 

В этом случае вам не нужно проходить в node ссылки на все; вызов createNode() будет генерировать новый объект узла, рекурсивно заполнить его дерево children и вернуть вновь созданную структуру узла.

Answer 2

Как я вижу, ваша дефиниция узла несколько похожа на список смежности на графике. В целевом узле добавить связанный узел в список, связанный с целевым узлом. Это верно для каждого узла, принадлежащего всем узлам.

Для каждого объекта, принадлежащего массиву объектов (параметр массива) в методе createNode, вам необходимо создать объект Node. просто передайте массив строк и узел таежа. Итерируйте список и создайте узел. Добавьте узел в список.

Чтобы избежать дублирования при создании узла, добавьте их на карту. Ключ к карте должен быть строкой, а значением должен быть объект Node. Перед созданием объекта узла просто попробуйте получить объект с карты, сделайте объект только в том случае, если объект не найден на карте (в таком случае создайте и добавьте его на карту). Если объект найден не на карте, мы сами не воссоздаем его.