从父/子的平面列表构建层次结构对象

I have a list of items in a hierarchy, and I'm attempting to parse this list out into an actual hierarchy of objects. I'm using modified pre-order tree traversal to store/iterate through this list, and so what I have is a subset of the tree, including all children, ordered by their "left" value.

我有一个层次结构中的项目列表，我正在尝试将此列表解析为实际的对象层次结构。我正在使用修改的预订树遍历来存储/遍历此列表，因此我所拥有的是树的子集，包括所有子节点，按其“左”值排序。

For example, given the tree:

例如，给定树：

• Item A
  • Item A.1
  • 项目A.1
  • Item A.2
    • Item A.2.2
    • 项目A.2.2
  • 项目A.2项目A.2.2
• 项目A项目A.1项目A.2项目A.2.2
• Item B
  • Item B.1
  • 项目B.1
• 项目B项目B.1
• Item C
• 项目C.

I get the list:

我得到了清单：

• Item A, Item A.1, Item A.2, Item A.2.2, Item B, Item B.1, Item C
• 项目A，项目A.1，项目A.2，项目A.2.2，项目B，项目B.1，项目C.

(This is in order of the "left" value from the modified pre-order tree setup).

（这是来自修改的预订树设置的“左”值的顺序）。

What I want to do is parse this into objects that contain the actual structure of the tree, eg:

我想要做的是将其解析为包含树的实际结构的对象，例如：

Class TreeObject {
    String Name;
    Guid ID; 
    Guid ParentID;
    List<TreeObject> Children;
}

The flat list is returned as a List of TreeObjects - and each TreeObject has properties for ID, ParentID, Left, and Right. What I'm looking for is a function:

平面列表作为TreeObjects列表返回 - 每个TreeObject都具有ID，ParentID，Left和Right属性。我正在寻找的是一个功能：

List<TreeObject> FlatToHeirarchy(List<TreeObject> list); 

which takes the flat list in, and returns a nested list.

获取平面列表，并返回嵌套列表。

In other words:

换一种说法：

List<TreeObject> flatSet = LoadTreeObjectsFromDatabase(); 
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2

I'm at a loss how to do this - keeping track of parents, and being able to deal with a bigger jump (eg, Item A.2.2 -> Item B).

我不知道如何做到这一点 - 跟踪父母，并能够处理更大的跳跃（例如，项目A.2.2 - >项目B）。

---

Edit: I'm looking for a non-brute-force solution here (eg, not looping several times, moving items into child nodes, until there are only the top-level parents left). I'm guessing there is an elegant method that can loop once, and just place items as needed.

编辑：我在这里寻找一个非暴力解决方案（例如，不循环几次，将项目移动到子节点，直到只剩下*父级）。我猜测有一个优雅的方法可以循环一次，只需根据需要放置项目。

Remember, they are always in a hierarchal order (since I'm using MPTT), so a given item is going to always be a child or sibling of the previous item, or at least share a parent with the previous item. It is never going to come somewhere else in the tree.

请记住，它们总是处于层级顺序（因为我使用MPTT），因此给定项目将始终是前一项目的子项或兄弟项目，或者至少与前一项目共享父项。它永远不会来到树的其他地方。

5 个解决方案

#1

Here's the function I ended up writing. I'm using MPTT to store objects, so the list is in order of the 'left' value, which basically means the parent always comes before any given item in the list. In other words, the item referenced by item.ParentID has always already been added (except in the case of top-level or root nodes).

这是我最后写的功能。我正在使用MPTT存储对象，因此列表按“左”值的顺序排列，这基本上意味着父对象始终位于列表中的任何给定项之前。换句话说，item.ParentID引用的项始终已添加（*或根节点除外）。

public class TreeObject
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
    public IList<TreeObject> Children { get; set; } = new List<TreeObject>();
}

public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list)
{
    // hashtable lookup that allows us to grab references to containers based on id
    var lookup = new Dictionary<int, TreeObject>();
    // actual nested collection to return
    var nested = new List<TreeObject>();

    foreach (TreeObject item in list)
    {
        if (lookup.ContainsKey(item.ParentId))
        {
            // add to the parent's child list 
            lookup[item.ParentId].Children.Add(item);
        }
        else
        {
            // no parent added yet (or this is the first time)
            nested.Add(item);
        }
        lookup.Add(item.Id, item);
    }

    return nested;
}

and a simple test (that works in LinqPad):

和一个简单的测试（在LinqPad中工作）：

void Main()
{
    var list = new List<TreeObject>() {
        new TreeObject() { Id = 1, ParentId = 0, Name = "A" },
        new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" },
        new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" },
        new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" },
        new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" }
    };

    FlatToHierarchy(list).Dump();
}

Results:

结果：

Since I'm updating this 5 years later, here's a recursive LINQ version:

自从我5年后更新这个，这是一个递归的LINQ版本：

public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) {
    return (from i in list 
            where i.ParentId == parentId 
            select new TreeObject {
                Id = i.Id, 
                ParentId = i.ParentId,
                Name = i.Name,
                Children = FlatToHierarchy(list, i.Id)
            }).ToList();
}

#2

I assume you already know the parent of all items.

我假设你已经知道所有项目的父项。

All you need to do is to iterate through all item of the list once and add the current item to its parent's children list. Only keep the items without parents in the target nested list.

您需要做的就是遍历列表中的所有项目并将当前项目添加到其父项的子项列表中。仅将没有父项的项目保留在目标嵌套列表中。

Here is some pseudo code:

这是一些伪代码：

foreach Item item in flatlist
   if item.Parent != null
      Add item to item.Parent.ChildrenList
      Remove item from flatlist
   end if
end for

As for getting the parents, from what I can see in your example, you might need to parse the name and build a stack as you advance in the list.

至于获取父母，从我在您的示例中看到的内容，您可能需要解析名称并在列表中前进时构建堆栈。

This problems looks hard but it really isn't. A lot of people see this problem from the wrong angle; you must not try to populate every children list but rather get rid of the children items from the flat list, then it becomes easy.

这个问题看起来很难，但事实并非如此。很多人从错误的角度看待这个问题;你不能试图填充每个子列表，而是从平面列表中删除子项，然后它变得容易。

#3

Alternative version that compiles normally, I wasn't sure if there was a problem with the code above.

正常编译的替代版本，我不确定上面的代码是否有问题。

private List<Page> FlatToHierarchy(List<Page> list) {
      // hashtable lookup that allows us to grab references to the parent containers, based on id
        Dictionary<int, Page> lookup = new Dictionary<int, Page>();
      // actual nested collection to return
      List<Page> nested = new List<Page>();

      foreach(Page item in list) {
        if (lookup.ContainsKey(item.parentId)) {
          // add to the parent's child list 
          lookup[item.parentId].children.Add(item); //add item to parent's childs list
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        } else {
          // no parent added yet (or this is the first time)
          nested.Add(item);     //add item directly to nested list                
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        }
      }
    return nested;
    }

#4

Here is an example, hope this helps

这是一个例子，希望这会有所帮助

class Program
{
    static void Main(string[] args)
    {
        TreeObject a  = new TreeObject() { Name = "Item A" };
        a.Children.Add( new TreeObject() { Name = "Item A.1" });
        a.Children.Add( new TreeObject() { Name = "Item A.2" });

        TreeObject b = new TreeObject() { Name = "Item B" };
        b.Children.Add(new TreeObject() { Name = "Item B.1" });
        b.Children.Add(new TreeObject() { Name = "Item B.2" });

        TreeObject c = new TreeObject() { Name = "Item C" };

        List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c });

        string list = BuildList(nodes);
        Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C

        List<TreeObject> newlist = new List<TreeObject>();
        TreeObject temp = null;

        foreach (string s in list.Split(','))
        {
            if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length)
            {
                temp = new TreeObject() { Name = s };
                newlist.Add(temp);
            }
            else
            {
                temp.Children.Add(new TreeObject() { Name = s });
            }                              
        }

        Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
    }

    static string BuildList(List<TreeObject> nodes)
    {
        StringBuilder output = new StringBuilder();
        BuildList(output, nodes);
        return output.Remove(output.Length - 1, 1).ToString();
    }

    static void BuildList(StringBuilder output, List<TreeObject> nodes)
    {
        foreach (var node in nodes)
        {
            output.AppendFormat("{0},", node.Name);
            BuildList(output, node.Children);
        }
    }
}

public class TreeObject
{
    private List<TreeObject> _children = new List<TreeObject>();

    public string Name { get; set; }
    public Guid Id { get; set; }
    public List<TreeObject> Children { get { return _children; } }
}

}

}

#5

Correcting the example given by gregmac

更正gregmac给出的示例

IList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId)
    {
        var q = (from i in list
                where i.parent_id == parentId
                select new
                {
                    id = i.id,
                    parent_id = i.parent_id,
                    kks = i.kks,
                    nome = i.nome
                }).ToList();
        return q.Select(x => new TreeObject
            {
                children = FlatToHierarchy(list, x.id)
            }).ToList();
    }