将扁平的集合转换为分层集合的递归方法？

Question

我在这个问题上卡了几天，希望能得到一些想法或帮助解决它。 我有一组对象。

 public class Hierarchy
{
    public Hierarchy(string iD, string name, int level, string parentID, string topParent)
    {
        ID = iD;
        Name = name;
        Level = level;
        ParentID = parentID;
        Children = new HashSet<Hierarchy>();
    }
    public string ID { get; set; }
    public string Name{ get; set; }
    public int Level { get; set; }
    public string ParentID { get; set; }
    public ICollection<Hierarchy> Children { get; set; }
}

我从实体中得到的 Linq 查询数据是:

ID      Name     Level ParentID
295152  name1    1     null
12345   child1   2     295152
54321   child2   2     295152
44444   child1a  3     12345
33333   child1b  3     12345
22222   child2a  3     54321
22221   child2b  3     54321
22002   child2c  3     54321
20001   child2a2 4     22222
20101   child2b2 4     22222

这些数据可能会延伸到未知的深度（我只展示了4个级别）。 最终，我将拥有一个层次结构对象，其中包含多个子对象，这些子对象又可以有多个子对象的集合......等等...... 始终只有一个顶级对象。

我尽可能在此项目中使用Linq。

显然，这需要某种递归方法，但我卡住了。任何想法或帮助将不胜感激。

TIA

- John S

Answer 1

实际上，迭代解决方案可能更容易。以下是步骤：

1. 根据节点的id将所有节点哈希到字典中
2. 第二次循环，将每个节点添加到其父节点的子列表中

看起来像这样：

Hierarchy CreateTree(IEnumerable<Hierarchy> Nodes)
{
    var idToNode = Nodes.ToDictionary(n => n.ID, n => n);

    Hierarchy root;
    foreach (var n in Nodes)
    {
        if (n.ID == null)
        {
            if (root != null)
            {
                //there are multiple roots in the data
            }
            root = n;
            continue;
        }

        Hierarchy parent;
        if (!idToNode.TryGetValue(n.ID, parent))
        {
            //Parent doesn't exist, orphaned entry
        }

        parent.Children.Add(n);
    }

    if (root == null)
    {
        //There was no root element
    }
    return root;
}

你的数据格式可能存在一些明显的错误情况。如何处理这些错误取决于你。

通常情况下，总会有一个迭代解法和一个递归解法。具体问题会影响哪种解法更容易实现。

- Chris Pitman

---

我非常喜欢你的回答和描述。我希望我能够给出两个答案。 - John S

你好，感谢你的解决方案。我尝试使用你的CreateTree方法，但是我遇到了一个引用问题。我在这里公开了它 https://stackoverflow.com/questions/54747804/why-sometimes-2-objects-reference-the-same-but-not-always - Florian

Answer 2

您可以尝试使用这个递归函数：

void PopulateChildren(Hierarchy root, ICollection<Hierarchy> source)
{
    foreach (var hierarchy in source.Where(h => h.ParentID == root.ParentID))
    {
        root.Children.Add(hierarchy);
        PopulateChildren(root, source);
    }
}

您可以像这样使用它：

ICollection<Hierarchy> hierarchies = new List<Hierarchy>(); // source

// Get root
var root = hierarchies.Single(h => h.Level == 1);

// Populate children recursively
PopulateChildren(root, hierarchies);

- OJ Raqueño

---

需要进行轻微修改才能使其工作。在对PopulateChildren的内部调用中，需要传递层次结构作为“根”，因为在这个级别上它是“根”。然后一切都运行得非常好。 - John S

这说明了在某些问题中递归和迭代之间的权衡：这个递归解法是O(n^2)，而迭代解法是O(n)。 - Chris Pitman