从父/子节点的扁平列表构建层次结构对象

Question

我有一个嵌套层级的项列表，并尝试将此列表解析为实际对象层次结构。我正在使用修改过的先序树遍历来存储/遍历此列表，因此我拥有包括所有子节点按其"left"值排序的子集树。

例如，给定以下树:

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

我得到以下列表:

• Item A, Item A.1, Item A.2, Item A.2.2, Item B, Item B.1, Item C

(这是按照已修改的先序树设置中的"left"值顺序排列的)。

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

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

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

List<TreeObject> FlatToHeirarchy(List<TreeObject> 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

我不知道如何处理这个问题——如何跟踪父级，并能够处理更大的跳跃（例如，Item A.2.2 -> Item B）。

---

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

请记住，它们总是按层次顺序排列的（因为我在使用MPTT），因此给定的项目将始终是前一个项目的子项或同级项，或者至少与前一个项目共享父级。它永远不会出现在树的其他位置。

- gregmac

---

这是否意味着您在数据库中存储每个节点的parentId、left和right值？ - Chris Barry

Answer 1

这是我最终写的函数。我正在使用MPTT来存储对象，所以该列表按照“left”值的顺序排列，这基本上意味着父级始终在列表中任何给定项之前。换句话说，由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;
}

并且有一个简单的测试（在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版本：

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

- gregmac

---

ScottE：不，lookup是一个按GUID索引的字典。这可能有点令人困惑，但原因是lookup（item.PranteID）包含item.parentId的父列表，换句话说，这个项目的祖父。.item（item.parentId）包含此项所在的列表，并添加单个项作为同级项。 - gregmac

有人能修复这个例子吗？ - Daniel Little

抱歉，已更新为可用的示例。当我最初提出问题时，原始代码是VB，我认为转换为C#后它就失效了 - 而且我显然从未测试过它，真是我的错。再次道歉！ - gregmac

如果您有多个树，想要返回所有树，您该如何做呢？ - eugenekgn

@eugenekgn 我不确定你在问什么，但无论如何，你应该将其作为一个新问题提出（并包括说明该问题的示例代码）。 - gregmac

Answer 2

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

你只需要遍历一次列表中的所有项目，并将当前项目添加到其父项的子项列表中。在目标嵌套列表中仅保留没有父项的项目。

以下是一些伪代码：

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

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

这个问题看起来很难，但实际上并不是。很多人从错误的角度看待这个问题；您不必尝试填充每个子项列表，而是要从平面列表中删除子项，然后问题就变得简单了。

- Coincoin

---

这就是我不明白的部分。我猜想有一种好的方法可以拥有一个包含所有父级的堆栈，并在项比其父级更深时继续将其推入堆栈，或者在向上移动时弹出最后一个。我想避免的是多次循环列表并删除项目。 - gregmac

一旦你知道每个节点的父节点，你可以遍历列表一次。我更新了我的答案，并附上了一些伪代码。 - Coincoin

我知道父对象的ID，但是我没有对父对象本身的引用（当然不能通过搜索列表来获取）。 - gregmac

你的“扁平列表”长什么样子，那将极大地帮助理解你的答案...我不能猜测它包含什么或是什么意思。 - PositiveGuy

在一些编程语言中，比如C#，这种方法行不通，因为编译器会在运行时抛出异常，因为你修改了正在枚举的集合。 - pim

Answer 3

你应该使用像嵌套集这样的数据库存储架构。

[ https://zh.wikipedia.org/wiki/嵌套集 ]

- Vahid Alvandi

Answer 4

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

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

- Chris Barry

Answer 5

修正由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();
    }

- Paulo Vj

---

你测试过这个吗？我喜欢你的方法...我想自己在平面桌子上试一试。 - user3390927

Answer 6

这里有一个例子，希望能帮到你

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

}

- Rohan West

---

这几乎是我想做的相反的事情。我想要最终得到的是你在第15行展示的“nodes”变量中的结构。我从一个包含所有对象的List<TreeObject>开始，它们直接作为兄弟节点存在（例如，没有父/子关系）。 - gregmac