如何有效地从平面结构中构建树？

G

Guido Preite

将对象的 ID 存储在映射到特定对象的哈希表中。枚举所有对象并找到它们的父对象（如果存在）并相应地更新其父指针。

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}

那是什么语言？（我认为它是 C#）

该算法是（非正式表示法）O(3N)，其中 O(1N) 解决方案很容易通过为非“遍历”父级实例化部分节点或通过为非实例化的子级保留辅助查找表来实现父母。对于大多数现实世界的用途来说可能并不重要，但它在大型数据集上可能很重要。

@AndrewHanlon 也许您应该发布 0(1N) 的 sol

@Ced Martin Schmidt 在下面的回答非常接近我将如何实现它。可以看出，它使用单个循环，其余的是哈希表操作。

O(3N) 只是 O(N) ;)

M

Morgoth

这是一个简单的 JavaScript 算法，用于将平面表解析为 N 次运行的父/子树结构：

var table = [
    {parent_id: 0, id: 1, children: []},
    {parent_id: 0, id: 2, children: []},
    {parent_id: 0, id: 3, children: []},
    {parent_id: 1, id: 4, children: []},
    {parent_id: 1, id: 5, children: []},
    {parent_id: 1, id: 6, children: []},
    {parent_id: 2, id: 7, children: []},
    {parent_id: 7, id: 8, children: []},
    {parent_id: 8, id: 9, children: []},
    {parent_id: 3, id: 10, children: []}
];

var root = {id:0, parent_id: null, children: []};
var node_list = { 0 : root};

for (var i = 0; i < table.length; i++) {
    node_list[table[i].id] = table[i];
    node_list[table[i].parent_id].children.push(node_list[table[i].id]);
}

console.log(root);

试图将这种方法转换为 C#。

意识到如果 id 从像 1001 这样的大的东西开始，那么我们会得到索引超出范围的异常......

提示：使用 console.log(JSON.stringify(root, null, 2)); 漂亮地打印输出。

如果节点未按父 ID 排序，这将失败

M

Morgoth

根据 Mehrdad Afshari 的回答和 Andrew Hanlon 对加速的评论，这是我的看法。

与原始任务的重要区别：根节点的 ID==parentID。

class MyObject
{   // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject Source { get; set; }
}

List<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    var lookup = new Dictionary<int, Node>();
    var rootNodes = new List<Node>();

    foreach (var item in actualObjects)
    {
        // add us to lookup
        Node ourNode;
        if (lookup.TryGetValue(item.ID, out ourNode))
        {   // was already found as a parent - register the actual object
            ourNode.Source = item;
        }
        else
        {
            ourNode = new Node() { Source = item };
            lookup.Add(item.ID, ourNode);
        }

        // hook into parent
        if (item.ParentID == item.ID)
        {   // is a root node
            rootNodes.Add(ourNode);
        }
        else
        {   // is a child row - so we have a parent
            Node parentNode;
            if (!lookup.TryGetValue(item.ParentID, out parentNode))
            {   // unknown parent, construct preliminary parent
                parentNode = new Node();
                lookup.Add(item.ParentID, parentNode);
            }
            parentNode.Children.Add(ourNode);
            ourNode.Parent = parentNode;
        }
    }

    return rootNodes;
}

很好，这基本上就是我所暗示的方法。但是，我将只使用一个伪根节点（ID = 0 和 null Parent）并删除自引用要求。

此示例中唯一缺少的是将 Parent 字段分配给每个子节点。为此，我们只需要在将子项添加到其父集合后设置父字段。像这样： parentNode.Children.Add(ourNode); ourNode.Parent = 父节点；

@plauriola 是的，谢谢，我添加了这个。另一种方法是仅删除 Parent 属性，核心算法不需要。

由于我找不到实现 O(n) 解决方案的 npm 模块，因此我创建了以下模块（单元测试，100% 代码覆盖率，大小只有 0.5 kb 并且包括类型。也许它可以帮助某人：npmjs.com/package/performant-array-to-tree

d

dmvianna

Python解决方案

    def subtree(node, relationships):
        return {
            v: subtree(v, relationships) 
            for v in [x[0] for x in relationships if x[1] == node]
        }

例如：

    # (child, parent) pairs where -1 means no parent    
    flat_tree = [
         (1, -1),
         (4, 1),
         (10, 4),
         (11, 4),
         (16, 11),
         (17, 11),
         (24, 17),
         (25, 17),
         (5, 1),
         (8, 5),
         (9, 5),
         (7, 9),
         (12, 9),
         (22, 12),
         (23, 12),
         (2, 23),
         (26, 23),
         (27, 23),
         (20, 9),
         (21, 9)
        ]
    
    subtree(-1, flat_tree)

产生：

你好。如何在输出中添加另一个属性？ IE。姓名，父母ID

迄今为止最优雅的！

@simpleguy：如果您需要更多控制，可以展开列表理解，例如：

def recurse(id, pages): for row in rows: if row['id'] == id: print(f'''{row['id']}:{row['parent_id']} {row['path']} {row['title']}''') recurse(row['id'], rows)

n

nu11ptr

返回一个根或一组根的 JS 版本，每个根都将具有包含相关子项的 Children 数组属性。不依赖于有序输入，相当紧凑，并且不使用递归。享受！

// creates a tree from a flat set of hierarchically related data
var MiracleGrow = function(treeData, key, parentKey)
{
    var keys = [];
    treeData.map(function(x){
        x.Children = [];
        keys.push(x[key]);
    });
    var roots = treeData.filter(function(x){return keys.indexOf(x[parentKey])==-1});
    var nodes = [];
    roots.map(function(x){nodes.push(x)});
    while(nodes.length > 0)
    {

        var node = nodes.pop();
        var children =  treeData.filter(function(x){return x[parentKey] == node[key]});
        children.map(function(x){
            node.Children.push(x);
            nodes.push(x)
        });
    }
    if (roots.length==1) return roots[0];
    return roots;
}


// demo/test data
var treeData = [

    {id:9, name:'Led Zep', parent:null},
    {id:10, name:'Jimmy', parent:9},
    {id:11, name:'Robert', parent:9},
    {id:12, name:'John', parent:9},

    {id:8, name:'Elec Gtr Strings', parent:5},
    {id:1, name:'Rush', parent:null},
    {id:2, name:'Alex', parent:1},
    {id:3, name:'Geddy', parent:1},
    {id:4, name:'Neil', parent:1},
    {id:5, name:'Gibson Les Paul', parent:2},
    {id:6, name:'Pearl Kit', parent:4},
    {id:7, name:'Rickenbacker', parent:3},

    {id:100, name:'Santa', parent:99},
    {id:101, name:'Elf', parent:100},

];
var root = MiracleGrow(treeData, "id", "parent")
console.log(root)

这个问题已有 7 年历史，并且已经有一个投票和接受的答案。如果您认为您有更好的解决方案，最好为您的代码添加一些解释。

这种方法适用于这种无序类型的数据。

c

codeBelt

在这里找到了一个很棒的 JavaScript 版本：http://oskarhane.com/create-a-nested-array-recursively-in-javascript/

假设你有一个这样的数组：

const models = [
    {id: 1, title: 'hello', parent: 0},
    {id: 2, title: 'hello', parent: 0},
    {id: 3, title: 'hello', parent: 1},
    {id: 4, title: 'hello', parent: 3},
    {id: 5, title: 'hello', parent: 4},
    {id: 6, title: 'hello', parent: 4},
    {id: 7, title: 'hello', parent: 3},
    {id: 8, title: 'hello', parent: 2}
];

你想让对象像这样嵌套：

const nestedStructure = [
    {
        id: 1, title: 'hello', parent: 0, children: [
            {
                id: 3, title: 'hello', parent: 1, children: [
                    {
                        id: 4, title: 'hello', parent: 3, children: [
                            {id: 5, title: 'hello', parent: 4},
                            {id: 6, title: 'hello', parent: 4}
                        ]
                    },
                    {id: 7, title: 'hello', parent: 3}
                ]
            }
        ]
    },
    {
        id: 2, title: 'hello', parent: 0, children: [
            {id: 8, title: 'hello', parent: 2}
        ]
    }
];

这是一个使它发生的递归函数。

function getNestedChildren(models, parentId) {
    const nestedTreeStructure = [];
    const length = models.length;

    for (let i = 0; i < length; i++) { // for-loop for perf reasons, huge difference in ie11
        const model = models[i];

        if (model.parent == parentId) {
            const children = getNestedChildren(models, model.id);

            if (children.length > 0) {
                model.children = children;
            }

            nestedTreeStructure.push(model);
        }
    }

    return nestedTreeStructure;
}

用法：

const models = [
    {id: 1, title: 'hello', parent: 0},
    {id: 2, title: 'hello', parent: 0},
    {id: 3, title: 'hello', parent: 1},
    {id: 4, title: 'hello', parent: 3},
    {id: 5, title: 'hello', parent: 4},
    {id: 6, title: 'hello', parent: 4},
    {id: 7, title: 'hello', parent: 3},
    {id: 8, title: 'hello', parent: 2}
];
const nestedStructure = getNestedChildren(models, 0);

对于每个 parentId 它都在循环整个模型 - 这不是 O(N^2) 吗？

V

Vimal Bhatt

这是 Mehrdad Afshari 的答案的 java 解决方案。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Tree {

    Iterator<Node> buildTreeAndGetRoots(List<MyObject> actualObjects) {
        Map<Integer, Node> lookup = new HashMap<>();
        actualObjects.forEach(x -> lookup.put(x.id, new Node(x)));
        //foreach (var item in lookup.Values)
        lookup.values().forEach(item ->
                {
                    Node proposedParent;
                    if (lookup.containsKey(item.associatedObject.parentId)) {
                        proposedParent = lookup.get(item.associatedObject.parentId);
                        item.parent = proposedParent;
                        proposedParent.children.add(item);
                    }
                }
        );
        //return lookup.values.Where(x =>x.Parent ==null);
        return lookup.values().stream().filter(x -> x.parent == null).iterator();
    }

}

class MyObject { // The actual object
    public int parentId;
    public int id;
}

class Node {
    public List<Node> children = new ArrayList<Node>();
    public Node parent;
    public MyObject associatedObject;

    public Node(MyObject associatedObject) {
        this.associatedObject = associatedObject;
    }
}

您应该解释一下代码背后的想法。

这只是早期答案的Java翻译

J

Joel Malone

对于任何对 Eugene 解决方案的 C# 版本感兴趣的人，请注意 node_list 作为地图访问，因此请改用 Dictionary。

请记住，此解决方案仅在表按 parent_id 排序时才有效。

var table = new[]
{
    new Node { parent_id = 0, id = 1 },
    new Node { parent_id = 0, id = 2 },
    new Node { parent_id = 0, id = 3 },
    new Node { parent_id = 1, id = 4 },
    new Node { parent_id = 1, id = 5 },
    new Node { parent_id = 1, id = 6 },
    new Node { parent_id = 2, id = 7 },
    new Node { parent_id = 7, id = 8 },
    new Node { parent_id = 8, id = 9 },
    new Node { parent_id = 3, id = 10 },
};

var root = new Node { id = 0 };
var node_list = new Dictionary<int, Node>{
    { 0, root }
};

foreach (var item in table)
{
    node_list.Add(item.id, item);
    node_list[item.parent_id].children.Add(node_list[item.id]);
}

节点定义如下。

class Node
{
    public int id { get; set; }
    public int parent_id { get; set; }
    public List<Node> children = new List<Node>();
}

它太旧了，但列表项 8 new Node { parent_id = 7, id = 9 }, 阻止 node_list.Add(item.id, item); 完成，因为 Key 不能重复；这是一个错字；因此，输入 id = 8 而不是 id = 9

固定的。谢谢@MarceloScofano！

看起来它会因随机节点顺序而失败。（例如，当根节点将在最后时）

A

Arithmomaniac

我根据@Mehrdad Afshari 的回答用 C# 写了一个通用的解决方案：

void Example(List<MyObject> actualObjects)
{
  List<TreeNode<MyObject>> treeRoots = actualObjects.BuildTree(obj => obj.ID, obj => obj.ParentID, -1);
}

public class TreeNode<T>
{
  public TreeNode(T value)
  {
    Value = value;
    Children = new List<TreeNode<T>>();
  }

  public T Value { get; private set; }
  public List<TreeNode<T>> Children { get; private set; }
}

public static class TreeExtensions
{
  public static List<TreeNode<TValue>> BuildTree<TKey, TValue>(this IEnumerable<TValue> objects, Func<TValue, TKey> keySelector, Func<TValue, TKey> parentKeySelector, TKey defaultKey = default(TKey))
  {
    var roots = new List<TreeNode<TValue>>();
    var allNodes = objects.Select(overrideValue => new TreeNode<TValue>(overrideValue)).ToArray();
    var nodesByRowId = allNodes.ToDictionary(node => keySelector(node.Value));

    foreach (var currentNode in allNodes)
    {
      TKey parentKey = parentKeySelector(currentNode.Value);
      if (Equals(parentKey, defaultKey))
      {
        roots.Add(currentNode);
      }
      else
      {
        nodesByRowId[parentKey].Children.Add(currentNode);
      }
    }

    return roots;
  }
}

否决票，请发表评论。我会很高兴知道我做错了什么。

H

Henrik Paul

在我看来这个问题很模糊，我可能会创建一个从 ID 到实际对象的映射。在伪java中（我没有检查它是否工作/编译），它可能是这样的：

Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>();

for (FlatObject object: flatStructure) {
    flatObjectMap.put(object.ID, object);
}

并查找每个父母：

private FlatObject getParent(FlatObject object) {
    getRealObject(object.ParentID);
}

private FlatObject getRealObject(ID objectID) {
    flatObjectMap.get(objectID);
}

通过重用 getRealObject(ID) 并从对象映射到对象集合（或它们的 ID），您也可以得到一个父->子映射。

n

nes1983

假设 Dictionary 类似于 TreeMap，我可以在 4 行代码和 O(n log n) 时间内完成此操作。

dict := Dictionary new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | (dict at: each parent) addChild: each].
root := dict at: nil.

编辑：好的，现在我读到一些 parentID 是假的，所以忘记上面的，然后这样做：

dict := Dictionary new.
dict at: nil put: OrderedCollection new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | 
    (dict at: each parent ifAbsent: [dict at: nil]) 
          add: each].
roots := dict at: nil.

佚

佚名

大多数答案都假设您希望在数据库之外执行此操作。如果您的树本质上是相对静态的，并且您只需要以某种方式将树映射到数据库中，您可能需要考虑在数据库端使用嵌套集表示。查看 Joe Celko 的书籍（或 here 了解 Celko 的概述）。

如果仍然绑定到 Oracle dbs，请查看他们的 CONNECT BY 以获得直接的 SQL 方法。

无论使用哪种方法，您都可以在将数据加载到数据库之前完全跳过树的映射。只是想我会提供这个作为替代方案，它可能完全不适合您的特定需求。原始问题的整个“正确顺序”部分在某种程度上暗示您出于某种原因需要数据库中的“正确”顺序？这也可能促使我去处理那里的树木。

A

Aske B.

这与提问者所寻找的并不完全相同，但我很难理解这里提供的措辞模棱两可的答案，我仍然认为这个答案符合标题。

我的答案是将平面结构映射到直接在对象上的树，其中您所拥有的只是每个对象上的 ParentID。 ParentID 是 null 或 0（如果它是根）。与提问者相反，我假设所有有效的 ParentID 都指向列表中的其他内容：

var rootNodes = new List<DTIntranetMenuItem>();
var dictIntranetMenuItems = new Dictionary<long, DTIntranetMenuItem>();

//Convert the flat database items to the DTO's,
//that has a list of children instead of a ParentID.
foreach (var efIntranetMenuItem in flatIntranetMenuItems) //List<tblIntranetMenuItem>
{
    //Automapper (nuget)
    DTIntranetMenuItem intranetMenuItem =
                                   Mapper.Map<DTIntranetMenuItem>(efIntranetMenuItem);
    intranetMenuItem.Children = new List<DTIntranetMenuItem>();
    dictIntranetMenuItems.Add(efIntranetMenuItem.ID, intranetMenuItem);
}

foreach (var efIntranetMenuItem in flatIntranetMenuItems)
{
    //Getting the equivalent object of the converted ones
    DTIntranetMenuItem intranetMenuItem = dictIntranetMenuItems[efIntranetMenuItem.ID];

    if (efIntranetMenuItem.ParentID == null || efIntranetMenuItem.ParentID <= 0)
    {
        rootNodes.Add(intranetMenuItem);
    }
    else
    {
        var parent = dictIntranetMenuItems[efIntranetMenuItem.ParentID.Value];
        parent.Children.Add(intranetMenuItem);
        //intranetMenuItem.Parent = parent;
    }
}
return rootNodes;

j

joegiralt

这是一个红宝石实现：

它将按属性名称或方法调用的结果进行分类。

CatalogGenerator = ->(depth) do
  if depth != 0
    ->(hash, key) do
      hash[key] = Hash.new(&CatalogGenerator[depth - 1])
    end
  else
    ->(hash, key) do
      hash[key] = []
    end
  end
end

def catalog(collection, root_name: :root, by:)
  method_names = [*by]
  log = Hash.new(&CatalogGenerator[method_names.length])
  tree = collection.each_with_object(log) do |item, catalog|
    path = method_names.map { |method_name| item.public_send(method_name)}.unshift(root_name.to_sym)
  catalog.dig(*path) << item
  end
  tree.with_indifferent_access
end

 students = [#<Student:0x007f891d0b4818 id: 33999, status: "on_hold", tenant_id: 95>,
 #<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b42c8 id: 37220, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b4020 id: 3444, status: "ready_for_match", tenant_id: 15>,
 #<Student:0x007f8931d5ab58 id: 25166, status: "in_partnership", tenant_id: 10>]

catalog students, by: [:tenant_id, :status]

# this would out put the following
{"root"=>
  {95=>
    {"on_hold"=>
      [#<Student:0x007f891d0b4818
        id: 33999,
        status: "on_hold",
        tenant_id: 95>]},
   6=>
    {"on_hold"=>
      [#<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
       #<Student:0x007f891d0b42c8
        id: 37220,
        status: "on_hold",
        tenant_id: 6>]},
   15=>
    {"ready_for_match"=>
      [#<Student:0x007f891d0b4020
        id: 3444,
        status: "ready_for_match",
        tenant_id: 15>]},
   10=>
    {"in_partnership"=>
      [#<Student:0x007f8931d5ab58
        id: 25166,
        status: "in_partnership",
        tenant_id: 10>]}}}

H

Hirurg103

接受的答案对我来说看起来太复杂了，所以我添加了它的 Ruby 和 NodeJS 版本

假设平面节点列表具有以下结构：

nodes = [
  { id: 7, parent_id: 1 },
  ...
] # ruby

nodes = [
  { id: 7, parentId: 1 },
  ...
] # nodeJS

将上面的平面列表结构变成树的函数如下所示

对于红宝石：

def to_tree(nodes)

  nodes.each do |node|

    parent = nodes.find { |another| another[:id] == node[:parent_id] }
    next unless parent

    node[:parent] = parent
    parent[:children] ||= []
    parent[:children] << node

  end

  nodes.select { |node| node[:parent].nil? }

end

对于 NodeJS：

const toTree = (nodes) => {

  nodes.forEach((node) => {

    const parent = nodes.find((another) => another.id == node.parentId)
    if(parent == null) return;

    node.parent = parent;
    parent.children = parent.children || [];
    parent.children = parent.children.concat(node);

  });

  return nodes.filter((node) => node.parent == null)

};

我认为 null 的检查需要用于 undefined

NodeJS 中的 @Ullauri null == undefined => true

O

Omry Yadan

一种优雅的方法是将列表中的项目表示为字符串，其中包含一个点分隔的父列表，最后是一个值：

server.port=90
server.hostname=localhost
client.serverport=90
client.database.port=1234
client.database.host=localhost

当组装一棵树时，你最终会得到类似的东西：

server:
  port: 90
  hostname: localhost
client:
  serverport=1234
  database:
    port: 1234
    host: localhost

我有一个从命令行参数（列表）实现此覆盖配置（树）的 configuration library。将单个项目添加到树 is here 的列表中的算法。

R

Robert Elwell

您是否只使用这些属性？如果没有，最好创建一个子节点数组，您可以在其中循环遍历所有这些对象以构建此类属性。从那里，选择有子节点但没有父节点的节点，然后从上到下迭代地构建你的树。

A

Aldom Michael

爪哇版

// node
@Data
public class Node {
    private Long id;
    private Long parentId;
    private String name;
    private List<Node> children = new ArrayList<>();
}

// flat list to tree
List<Node> nodes = new ArrayList();// load nodes from db or network
Map<Long, Node> nodeMap = new HashMap();
nodes.forEach(node -> {
  if (!nodeMap.containsKey(node.getId)) nodeMap.put(node.getId, node);
  if (nodeMap.containsKey(node.getParentId)) {
    Node parent = nodeMap.get(node.getParentId);
    node.setParentId(parent.getId());
    parent.getChildren().add(node);
  }
});

// tree node
List<Node> treeNode = nodeMap .values().stream().filter(n -> n.getParentId() == null).collect(Collectors.toList());

J

João Paraná

请参阅下面带有简单测试程序的完整 Java 8+ 解决方案。

这是对接受多个根的@“Vimal Bhatt”版本进行修改的解决方案

package tree;

import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Stream;

public class Tree {
    
    private <T> void swap(T[] input, int a, int b) {
        T tmp = input[a];
        input[a] = input[b];
        input[b] = tmp;
    }
    
    public static void main(String[] args) {
        Random r = new Random(8);

        MyObject[] myObjects = new MyObject[]{
                new MyObject(6, 3),
                new MyObject(7, 5),
                new MyObject(8, 0),
                new MyObject(1, 0),
                new MyObject(15, 12),
                new MyObject(12, 0),
                new MyObject(3, 5),
                new MyObject(4, 3),
                new MyObject(5, 2),
                new MyObject(2, 1),
                new MyObject(21, 8),
                new MyObject(9, 1)
        };
        
        Tree t = new Tree();
        // cinco trocas arbitrarias de posição
        for (int i = 0; i < 5; i++) {
            int a = r.nextInt(7) + 1;
            int b = r.nextInt(7) + 1;
            t.swap(myObjects, a, b);
        }
        System.out.println("The list have " + myObjects.length + " objects");
        for (MyObject o: myObjects) {
            System.out.print(" " + o);
        }
        Iterator<Node> iterator = t.buildTreeAndGetRoots(Arrays.asList(myObjects));
        int counter = 0;
        System.out.println("");
        while (iterator.hasNext()) {
            Node obj = iterator.next();
            System.out.println(++counter + "\t" + obj.associatedObject.id + "\t-> " + obj.associatedObject.parentId);
        }
    }

    Iterator<Node> buildTreeAndGetRoots(List<MyObject> actualObjects) {
        Node root = null;
        Map<Integer, Node> lookup = new HashMap<>();
        actualObjects.forEach(x -> lookup.put(x.id, new Node(x)));

        Stream<Node> roots = actualObjects.stream()
                .filter(x -> x.parentId == 0)
                .map(x -> new Node(x));
        Consumer<Node> nodeConsumer = item -> {
            Node proposedParent;
            if (lookup.containsKey(item.associatedObject.parentId)) {
                proposedParent = lookup.get(item.associatedObject.parentId);
                item.parent = proposedParent;
                proposedParent.children.add(item);
            }
        };
        lookup.values().forEach(nodeConsumer);
        Stream<Node> s2 = lookup.values().stream().filter(e -> e.associatedObject.parentId != 0);
        return Stream.concat(roots, s2).iterator();
    }
}

class MyObject { // The actual object
    public int parentId;
    public int id;

    MyObject(int id, int parent) {
        this.parentId = parent;
        this.id = id;
    }

    @Override
    public String toString() {
        return "{ " +
                "parent: " + parentId +
                ", id: " + id +
                " }" ;
    }
}

class Node {
    public List<Node> children = new ArrayList<Node>();
    public Node parent;
    public MyObject associatedObject;

    public Node(MyObject associatedObject) {
        this.associatedObject = associatedObject;
    }
}

g

golopot

此解决方案与所选答案相同，但在 JavaScript 中：

/**
 * @param {{id: any, parentId: any}[]} nodes
 */
function arrayToTree(nodes) {
  const map = new Map(nodes.map((x) => [x.id, { key: x.id, children: [] }]));
  for (const n of nodes) {
    if (n.parentId) {
      map.get(n.parentId)?.children?.push(map.get(n.id));
    }
  }
  return nodes.filter((x) => x.parentId === null).map((x) => map.get(x.id));
}

l

luqmansen

利用指针的 Golang 解决方案。由于每次迭代基本上都会指向同一个对象，导致 N 空间和时间复杂度

https://go.dev/play/p/lrPBTawy7Su

func TestCommentTree(t *testing.T) {
    var listRaw = `[{"id":5,"parentPostID":0,"parentID":null,"authorID":1,"content":"asadas","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":9,"parentPostID":0,"parentID":5,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":10,"parentPostID":0,"parentID":9,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":11,"parentPostID":0,"parentID":5,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":12,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":13,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":14,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":15,"parentPostID":0,"parentID":12,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":16,"parentPostID":0,"parentID":11,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":17,"parentPostID":0,"parentID":16,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":18,"parentPostID":0,"parentID":17,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":19,"parentPostID":0,"parentID":18,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"}]`
    
    type Comment struct {
        ID uint64 `db:"id" json:"id"`

        ParentPostID uint64 `db:"parent_post_id" json:"parentPostID"`
        ParentID     *int   `db:"parent_id" json:"parentID"` // allow nullable on lvl 0 comment
        AuthorID     uint64 `db:"author_id" json:"authorID"`
        Content      string `db:"content" json:"content"`

        Replies []*Comment `json:"replies"`

        CreatedAt time.Time `db:"created_at" json:"createdAt"`
        UpdatedAt time.Time `db:"updated_at" json:"updatedAt"`
    }

    var c []*Comment
    err := json.Unmarshal([]byte(listRaw), &c)
    if err != nil {
        panic(err)
    }

    node := make(map[uint64]*Comment)
    for _, v := range c {
        node[v.ID] = v
    }
    for _, comm := range node {
        if comm.ParentID == nil {
            continue
        }

        parent := node[uint64(*comm.ParentID)]
        if parent == nil {
            panic(fmt.Sprintf("parent nil %d", *comm.ParentID))
        }
        if parent.Replies == nil {
            parent.Replies = make([]*Comment, 0)
            parent.Replies = append(parent.Replies, comm)
        } else {
            parent.Replies = append(parent.Replies, comm)
        }

    }

    res := make([]*Comment, 0)
    for _, comm := range node {
        if comm.ParentID != nil {
            continue
        }
        res = append(res, comm)
    }

    s, _ := json.MarshalIndent(res, "", "\t")
    fmt.Println(string(s))
}

M

Mr. Polywhirl

基于 Euguene's answer，这是一种函数式方法。如果项目未预先排序，nodeList 将不会让父项准备好添加子项。

这是一个没有预排序的示例（使用 OOP）：

类节点 { 构造函数 ({ id, parentId }) { this.id = id; this.parentId = parentId; this.children = []; } }; const buildTree = (items) => { const root = new Node({ id: 0, parentId: null }), nodeList = { 0 : root }; items.forEach(({ id, parentId }) => { if (!nodeList[id]) { nodeList[id] = new Node({ id, parentId }); } else { nodeList[id].parentId = parentId; } if (!nodeList[parentId]) { nodeList[parentId] = new Node({ id: parentId }); } nodeList[parentId].children.push(nodeList[id]); });返回根； }; const items = [ { id: 10, parentId: 3 }, { id: 8, parentId: 7 }, { id: 6, parentId: 1 }, { id: 4, parentId: 1 }, { id: 2, parentId : 0 }, { id: 9, parentId: 8 }, { id: 7, parentId: 2 }, { id: 5, parentId: 1 }, { id: 3, parentId: 0 }, { id: 1, parentId : 0 }, ];常量树 = buildTree(items);控制台.日志（树）； .as-console-wrapper { top: 0;最大高度：100%！重要； }

如何有效地从平面结构中构建树？

关注公众号

想领先一步获取最新的外包任务吗？

相似问题

平台

支持

联系我们