Печать всех путей в дереве (не только для узлов)

Question

Итак, как бы вы напечатали все пути в дереве. Здесь условие состоит в том, что мы не только хотим, чтобы пути начинались с корня или путей в поддереве.

Например:

 2 
    /\ 
    8 10 
    /\ /
5 6 11 

Так что программа должна возвращать:

2-8 
2-10 
2-8-5 
2-8-6 
8-5 
8-6 
2-10-11 
10-11 
5-8-2-10-11 
5-8-2-10 
and so on... 

Один из подходов состоит в нахождении LCA между каждой отдельной пары узлов, а затем распечатать путь от LCA к обоим узлов (обратное в левом поддереве и в порядке справа поддерева). Но сложность здесь была бы O (n^3). Есть ли более эффективное решение?

Answer 1

Если вы заинтересованы только в результате, не в Алгоритм, создать узлы и отношения в Neo4j с

merge (n2:node{n:2})-[:down]->(n8:node{n:8})-[:down]->(:node{n:5}) 
merge (n2)-[:down]->(:node{n:10})-[:down]->(:node{n:11}) 
merge (n8)-[:down]->(:node{n:6}) 

затем запрос

match p=(a)-[r:down *]-(b) return nodes(p) 

Answer 2

Предполагая, что вы дерево имеет различные узлы, вы могут:

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

2. Передайте эту карту по значению каждому узлу. Вы можете иметь функцию, как:

   void printAllPaths(node *proot, map<int, vector<int> > m) 
   

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

   а) Для каждого к из множества ключей

   б) Добавить п в вектор значений k.

   c) Печатать все ключи, за которыми следуют их векторы значений.

   d) Также вставьте новый ключ как n в карту с пустым вектором в качестве значения.

Примечание: Если дерево имеет совмещенных узлов Вы MultiMap поможет вам следить. C++ STL хорошо послужит вам в этом случае.