从父/子平列表建设层次对象 [英] Building hierarchy objects from flat list of parent/child

问题描述

我有一个层次的项目清单，而我试图分析此名单出到对象的实际的层次结构。我使用修改pre-为了树遍历存储/遍历这个列表，所以我有什么是树，包括所有的孩子，订购他们的左值的子集。

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.

例如，给出的树：

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

        我得到的名单：

        • 在项目A，项目A.1，A.2项，项目A.2.2，项目B，项目B.1，C项

        （这是为了从修改pre阶树设置的左的值）。

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

        平列表返回TreeObjects的列表 - 每个的TreeObject具有ID，PARENTID，左，右属性。我正在寻找的是一个功能：

        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:

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

        这需要平坦的列表中，并返回一个嵌套列表。

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

        在换句话说：

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

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

        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).

        ---

        编辑：我在寻找一个非强力解决方案在这里（例如，不循环几次，移动项目到子节点，直到只剩下顶层的父母左）。我猜有一个优雅的方法，它可以循环一次，并根据需要只放置物品。

        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.

        记住，他们总是在一个层次顺序（因为我使用MPTT），因此给定的项目将始终是previous项目的子女或兄弟姐妹，或者至少是分享与父母previous项目。它是永远不会来了别的地方，在树上。

        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存储对象，所以列表是为了'左'的价值，这基本上意味着父母总是列表中的任何项目之前。换句话说，由item.ParentID引用的项一直已添加（除在顶层或根节点的情况下）。

        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).

        编辑：固定的编译错误，我们对此深感抱歉。我添加了一个例子，更新为使用int代替的Guid只是为了提高可读性，但它的工作原理是一样的。

        fixed compile errors, sorry about that. I added an example and updated to use Int instead of Guid just for readability, but it works the same.

        public class TreeObject {
            public Guid Id { get; set; }
            public Guid ParentId { get; set; }
            public string Name;
            public IList<TreeObject> Children { get; set; }
        
            public TreeObject() {
                Children = new List<TreeObject>();
            }
        }
        
        
        public List<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
            List<TreeObject> 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;
        }
        

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

        and a simple test (that works in 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();
        }
        

        结果：

        

        因为我更新这5年过去了，这里是一个递归LINQ版本：

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

        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,
                        Children = FlatToHierarchy(list, i.Id)
                    }).ToList();
        }
        

        这篇关于从父/子平列表建设层次对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！