Обходить каждый уникальный путь (от корня до листа) в произвольной древовидной структуре

Question

У меня есть несколько списков:

A = ["a0", "a1"]       // the number of lists varies
B = ["b0", "b1", "b2"] // such as the number of elements in a list.
C = ["c1"]
D = ["d0", "d1"]

Я преобразую эту структуру в дерево:

             _____ROOT______
            /               \ 
       ___a0____        ____a1____
      /    |    \      /     |    \
    b0    b1    b2    b0    b1    b2
     |     |     |     |     |     |
    c1    c1    c1    c1    c1    c1
   / |   / |   / |   / |   / |   / |
  d0 d1 d0 d1 d0 d1 d0 d1 d0 d1 d0 d1

Я печатаю каждый уникальный путь в дереве (без корня):

a0 -> b0 -> c1 -> d0
a0 -> b0 -> c1 -> d1
a0 -> b1 -> c1 -> d0
...
a1 -> b2 -> c1 -> d1

Я делаю это, "уничтожая" само дерево, обходя его следующим образом:

public static void delete(Node node) {
  if (node.isLeaf() && !node.isRoot()) {
    Node parent = node.getParent();
    parent.removeChild(node);
    delete(parent);
  }
}

public static void traverse(Node node) {
  if (node.isRoot())
    System.out.println("---");
  else
    System.out.println(node.getName());

  if (node.isLeaf()) {    // I'm still working on
    if (!node.isRoot()) { // removing unnecessary checks
      delete(node);
      traverse(node.getRoot());
    }
  } else {
    Node child = node.firstChild();
    if (null != child)
      traverse(child);
  }
}      

traverse(Node) всегда печатает первый доступный путь дерева(от корня к листу), в то время как delete(Node) обрезает листья дерева, которое уже посещено traverse(Node).

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

Answer 1

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

Тогда (неоптимизированная версия)

void traverse (Node root) {
  // assume root != NULL
  traverse (root, new LinkedList<Node>());
}

private void traverse (Node root, LinkedList<Node> path) {
  path.add(root);
  if (root.isLeaf()) {
    print path;
  }
  else {
    for each node of root {
      traverse (node, new LinkedList<Node>(path));
    }
  }
}

Answer 2

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

Традиционный способ преобразовать это в простой DFS состоит в том, чтобы обойти ваше рекурсивное условие, в основном, изменить дочерний рекурсивный вызов на что-то вроде:

} else {
  for (Node child = node.firstChild(); node != null; node = node.nextChild()) {
      traverse(child);
  }
}

Это будет проходить через всех ваших детей, и вы можете в значительной степени удалить случай node.isLeaf, поскольку возврат выполняется автоматически для вас. Обратите внимание, что я создал функцию nextChild, поскольку не вижу, как она вызывается в вашем коде, но у вас должно быть что-то похожее или какой-то способ перебора дочерних элементов.

Альтернативным способом, который сохраняет большую часть структуры вашего существующего кода, будет сохранение отдельной структуры данных, которая содержит набор «посещенных» узлов, это может быть так же просто, как и набор строк, если все имена ваших узлов уникальный - вместо того, чтобы удалить узел, добавьте его в набор «посещенных», и в ваших условиях рекурсии не проверяйте на ноль, а скорее найдите первый не посещенный узел. Это, вероятно, более сложно, чем приведенное выше предложение, но может быть больше похоже на то, что у вас есть сейчас - и позволит избежать циклов в случае, если вам когда-либо понадобится сделать это на циклическом графе, а не на дереве.

Answer 3

Что-то, что я придумал, работая над печатью слов в TrieTree, которое можно легко адаптировать к другим типам деревьев или другим потребностям:

public void rootToLeaves() {
    HashMap<Integer, TrieNode> hashMap = new HashMap<Integer, TrieNode>();
    for(TrieNode trieNode : root.getChildren())
        rootToLeaves(trieNode, hashMap, 0);
}

private void rootToLeaves( TrieNode trieNode, HashMap<Integer, TrieNode> hashMap, int heightIndex ) {
    hashMap.put(heightIndex, trieNode);

    if( trieNode.isLeaf() )
        printValues(hashMap, heightIndex);
    else
        for( TrieNode childNode : trieNode.getChildren() )
            rootToLeaves( childNode, hashMap, heightIndex + 1 );
}

private void printValues(HashMap<Integer, TrieNode> hashMap, int heightIndex) {
    for(int index = 0; index <= heightIndex; index++)
        System.out.print(hashMap.get(index).getValue());
    System.out.println();
}

Это решение отлично справляется с управлением памятью (оно использует один HashMap, размер которого никогда не будет превышать высоту дерева) и предлагает большую гибкость (просто замените printValues ​​на все, что вам нужно).

ПРИМЕЧАНИЕ: Зная заранее высоту дерева, вы сможете использовать простой Array вместо Map.

Answer 4

1, найти листовой узел
2, Вверх по обходу от листового узла

public void printPath(N n) {
        if (n == null)
            return;
        if (n.left == null && n.right == null) {
            do {
                System.out.print(n.value);
                System.out.print(" ");
            } while ((n = n.parent) != null);
            System.out.println("");
            return;
        }
        printPath(n.left);
        printPath(n.right);
    }

printPath (корень);