Узлы разбора в древовидной структуре Java в векторе строк

Question

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

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

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

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

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

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

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

поэтому узел 3 на левой стороне будет "root|node1|node2|node3" узел3 на правой стороне будет "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

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

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

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

Answer 2

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

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());
  }
}

ПРИМЕЧАНИЕ. Я не смог проверить этот код перед публикацией.