如何从一个扁平的结构构建一棵树？

Question

我有一堆对象，它们以扁平的结构存在。这些对象有一个“ID”和一个“ParentID”属性，因此它们可以组成树形结构。它们没有特定的顺序。

每个“ParentID”属性不一定与结构中的“ID”匹配。因此，这些对象可能会形成多棵树。

我应该如何处理这些对象以创建结果树？

我需要创建这些树，然后按正确的顺序将数据插入数据库。

没有循环引用。当ParentID == null或者ParentID在其他对象中找不到时，一个节点就是根节点。

- Costo

---

“Create”是什么意思？在UI中呈现？以XML或数据库的层次结构方式存储？ - D'Arcy Rittich

如何定义没有父节点的节点（即根节点）。ParentID为null？ParentID = 0？我假设没有循环引用，对吗？ - Jason Punyon

我觉得这个问题很不错。 - nes1983

请查看此文章：http://www.scip.be/index.php?Page=ArticlesNET23&Lang=NL - ebram khalil

Answer 1

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

在C#中：

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

- Mehrdad Afshari

---

那是什么语言？（我认为是C#） - Jason S

这个算法的时间复杂度（用非正式符号表示）为O（3N），而O（1N）的解决方案可以通过为未遍历的父节点实例化部分节点，或者为非实例化父节点的子节点保留第二个查找表轻松实现。对于大多数实际应用程序可能并不重要，但在处理大型数据集时可能会很重要。 - Andrew Hanlon

@AndrewHanlon也许你应该发布0(1N)的解答。 - Ced

@Ced Martin Schmidt的下面的答案非常接近我实现的方式。可以看到，它使用了一个循环和其余的哈希表操作。 - Andrew Hanlon

O(3N)只是O(N)的一种表示方式 ;) - JakeWilson801

我该如何利用这个来生成类似于这个的东西 https://github.com/jakezatecky/react-checkbox-tree/blob/master/examples/src/js/FilterExample.js - Silly Volley

Answer 2

以下是一个简单的 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);

- Eugene

---

尝试将这种方法转换为C#。 - hakan

我意识到如果id从1001这样的大数字开始，那么我们会得到索引越界异常... - hakan

提示：使用 console.log(JSON.stringify(root, null, 2)); 来美化输出结果。 - aloisdg

如果节点未按父级id排序，则此操作将失败。 - AaA

Answer 3

根据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;
}

- Martin Schmidt

---

不错，这基本上就是我所暗示的方法。但是我会只使用一个伪根节点（ID=0且父节点为null），并删除自引用要求。 - Andrew Hanlon

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

@plauriola 确实，谢谢，我已经添加了这个。另一种选择是只需删除 Parent 属性，因为它对于核心算法并不必要。 - Martin Schmidt

由于我找不到一个实现 O(n) 解法的 npm 模块，因此我创建了以下这个（已进行单元测试，代码覆盖率达到100％，仅0.5 kb大小并包含类型定义）。也许它能帮助某些人：https://www.npmjs.com/package/performant-array-to-tree。 - Philip Stanislaus

Answer 4

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)

产生：

    {
        "1": {
            "4": {
                "10": {}, 
                "11": {
                    "16": {}, 
                    "17": {
                        "24": {}, 
                        "25": {}
                    }
                }
            }, 
            "5": {
                "8": {}, 
                "9": {
                    "20": {}, 
                    "12": {
                        "22": {}, 
                        "23": {
                            "2": {}, 
                            "27": {}, 
                            "26": {}
                        }
                    }, 
                    "21": {}, 
                    "7": {}
                }
            }
        }
    }

- minkwe

---

你好。我该如何在输出中添加另一个属性？例如名称，父ID。 - simple guy

迄今为止最优雅的！ - ccpizza

@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) - ccpizza

Answer 5

这是一个返回一个根元素或根元素数组的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)

- nu11ptr

---

这个问题已经有7年的历史，且已经有被投票和接受的答案。如果你认为你有更好的解决方案，最好在你的代码中加入一些解释。 - Jordi Nebot

这种方法适用于无序数据类型。 - Cody C

Answer 6

这里是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;
    }
}

- Vimal Bhatt

---

你应该解释一下代码背后的想法。 - Ziad Akiki

这只是之前答案的Java翻译。 - Vimal Bhatt

Answer 7

我在这里找到了一份很棒的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);

- codeBelt

---

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

Answer 8

对于任何对Eugene的解决方案感兴趣且需要C#版本的人，请注意node_list被视为一个map，因此请使用Dictionary代替。

请记住，只有在table按照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]);
}

Node 的定义如下。

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

- Joel Malone

---

它太老了，但列表项8 new Node { parent_id = 7, id = 9 }， 阻止了 node_list.Add(item.id, item); 完成，因为键不能重复；这是一个打字错误；所以，不要使用 id = 9，而是使用 id = 8。 - Marcelo Scofano Diniz

已解决。感谢@MarceloScofano！ - Joel Malone

看起来对于随机节点顺序会失败。（例如，当根节点在最后时） - Disappointed

Answer 9

我根据 @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;
  }
}

- HuBeZa

---

投票者，请评论。我很乐意知道我做错了什么。 - HuBeZa

Answer 10

大多数答案都假设您想在数据库之外完成此操作。如果您的树相对静态，只需要将树映射到数据库中，您可能希望考虑在数据库端使用嵌套集表示法。请查看Joe Celko的书籍（或这里获取Celko的概述）。

如果已经与Oracle数据库绑定，请查看他们的CONNECT BY以进行直接SQL方法。

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

- SQLHack