java - 从展平 DFS 结构创建递归结构

Question

问题

我有以下树:

      2
     / \
    3   5
   /   / \ 
  6   4   1

以下列方式和顺序表示:

id    parent
------------
2     null
3     2
6     3
5     2
4     5
1     5

目的:

在O(n)中以递归结构存储这棵展平树(O(n*log(n))是可以接受的，但不是很好)(我知道如何在< strong>O(n^2)，但我以该 DFS 顺序存储数据以便能够以更有效的方式“解析”它)。例如:

class R {
    int id;
    List<R> children;
}

在 JSON 格式中看起来像这样:

{
    id: 2,
    children: [
            {
                id: 3,
                children: { ... }             
            },
            {
                id: 5,
                children: { ... }
            }
    ]
}

我如何做到这一点？编程语言并不重要，因为我可以用 Java 翻译它。

---

Java代码:

R r = new R();
Map<Long, Line> map = createMap2();
List<Line> vals = new ArrayList<Line>(map.values());
r.id = vals.get(0).id;
vals.remove(0);
r.children = createResource(vals, r.id);
...
private static List<R> createResource(List<Line> l, Long pid) {
    List<R> lr = new ArrayList<R>();
    if ( l.size() > 0 ) {           
        Long id = l.get(0).id;
        Long p = l.get(0).pid;
        l.remove(0);
        if ( pid.equals(p) ) {
            R r = new R();
            r.id = id;
            r.children = createResource(l, id);
            lr.add(r);
        }
        else {
            return createResource(l, pid);   // of course, this is not ok
        }
    }
    return lr;
}

上面代码中的问题是递归结构(类R)中只存储了2、3和6。我想在那个递归结构(R 对象)中存储整个展平树结构(许多 Line 对象)，而不仅仅是一些节点。

P.S.:问题被简化了。我对特定的解决方案不感兴趣，因为涉及的领域很多，条目也有数千条。我也对能够在最坏情况下(不同种类的树)正常工作的解决方案感兴趣，因为这是用户的保证。

Answer 1

像这样的事情呢？在第一遍中，将 parent 散列为他们 child 的数组并确定根；在第二个中，从根开始，为它的每个 child 插入一个新对象，以及它自己的 child 等等:

以你的例子为例，第一遍会产生

parent_hash = {2:[3,5], 3:[6], 5:[4,1]}
root = 2

第二遍会是这样的:

object 2 -> object 3 -> object 6
         -> object 5 -> object 4
                     -> object 1
done