Разбор узлов в структуре Java дерево в векторе строк

Question

У меня есть структура данных, которая выглядит как этот

private String name; 
private ArrayList<Node> children; 
private String parent=""; 

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

В другом месте в моей программе, я узел называется «корень», который содержит всю структуру дерева данных ,

Концептуально это выглядит как этот

         root 
            / \ 
            /  \ 
            node1  node2 
           /   \ 
           /   \ 
           node2   node3 
           /
          /
          node3 

Как вы можете видеть, узлы могут иметь такое же имя. Это предназначено. Я хочу создать строку для каждого узла, который содержит свое имя, плюс его линия и сохранить их в векторе.

такой узел 3 на левой стороне будет "root|node1|node2|node3" node3 на RHS будут "root|node2|node3" узел1 бы "root|node1" т.д.

У меня есть способ итерации по структуре узла для печати каждого узла, но я «Мне трудно установить каждого родителя, как в, я не могу понять, как это сделать. Любая помощь будет фантастической, поскольку все, что я пробовал до сих пор, не удалось. Важно отметить, что дерево не обязательно является двоичным деревом, я просто использую его для примера.

Вот код, который я использую для печати каждого узла дерева. Надеюсь, это будет легко настроить.

public void print() { 
     LinkedList<Node> open = new LinkedList<Node>(); 
     LinkedList<Node> closed = new LinkedList<Node>(); 

     open.add(this); 

     while(!open.isEmpty()) { 
      Node currentNode = open.removeFirst(); 
      System.out.println(currentNode.getName()); 

      ArrayList<Node> children = currentNode.getChildren(); 
      closed.add(currentNode); 

      for(int i = 0; i < children.size(); i++) { 
       Node current = children.get(i); 
       open.addLast(current); 
      } 
     } 
    } 

Спасибо, ребята.

Answer 1

кажется, что было бы проще добавить родителя при его создании, но если у вас есть дерево и вы хотите добавить родителя к каждому узлу, вы можете использовать рекурсию. я хотел бы попробовать что-то вроде

addParent(root, ""); 

public void addParent(Node node, String parent) { 
    node.setParent(parent); 

    // if this node has children iterate through them 
    // and call addParent with current node name. 
    for(Node childNode : node.getChildren()) { 
     addParent(childNode, node.getName()); 
    } 
} 

Примечание: Я не был в состоянии проверить этот код, прежде чем отправлять.

Answer 2

Я предполагаю, что у вас уже созданы эти узлы, и они были созданы с детьми, но без родителя? Похоже, есть несколько вариантов:

1. При создании детей, установить родитель (я думаю, что вы на самом деле не имеете контроля над этим, потому что вы задаете этот вопрос) так ...
2. Вместо вектора, возможно, используйте некоторый тип Карты, где вы можете установить ключ как линию. Затем, когда вы перебираете узлы, выполните некоторую строчную настройку, чтобы удалить имя текущего узла, и вы остаетесь с родительским родословным.
3. Связано с №2, не используйте карту (и сохраняйте вектор) и продолжайте выполнять манипуляции с строкой, но затем вам придется перебирать каждый узел в векторе, чтобы искать родителя по его линии.

Надеется, что это помогает, и, надеюсь, я правильно -Dave