从树顺序创建的树创建平面列表 [英] Create flat list from tree ordered by the tree order
问题描述
我正在使用C＃，我正在寻找一种简单的方法来获取代表一棵树的列表，并将该树平展为具有与树中相同顺序的列表。
I'm working on C# and i'm looking for a simple way to take a list that represent a tree and flat the tree to a list with the same order as in the tree.
我每个节点有4个属性：
* ID
* ParentID，
* Seq
*名称
I have 4 properties per node:
* ID
* ParentID,
* Seq
* Name
public class MyNode
{
public int ID{get;set;}
public int ParentID{get;set;}
public int SeqID{get;set;}
public string Name{get;set;}
}
我有MyNode的集合：
And i have a collection of MyNode:
List<MyNode> FlatListOfNodes{get;set;}
我正在寻找看起来像这样的东西：
FlatListOfNodes.OrderBy（something）.DoAnotherThing1（somthing）... 。
I'm looking for something that will look like this:
FlatListOfNodes.OrderBy(something).DoAnotherThing1(somthing)....
将按照树中的相同顺序对列表进行排序。
that will order the list in the same order that is in the tree.
例如，如果有这棵树：
-- Parent1
-- Child 1.1
-- Child 1.2
-- grandson 1.2.1
-- grandson 1.2.2
-- grandson 1.2.3
-- Child 1.3
-- Parent2
-- Child 2.1
-- Child 2.2
-- grandson 2.2.1
-- grandson 2.2.2
-- grandson 2.2.3
-- Child 2.3
-- grandson 2.3.1
-- grandson 2.3.2
我想用相同的顺序在平面列表中表示它。
I want to represent it in a flat list by the same order.
在此示例中：
- Parent1的ID = 32，ParentID =- 1，SeqID = 1，Name = Parent1
- Child1.2有ID = 412，ParentID = 32，SeqID = 2，Name = Child1.2
- 孙子1.2.1的ID = 231，ParentID = 412，SeqID = 1，Name =孙子1.2.1
- Parent2的ID = 345，ParentID = -1，SeqID = 2，Name = Parent2
- Child2.3，ID为785，ParentID = 345，SeqID = 3，Name = Child 2.3
- 孙子2.3.1将具有ID = 854，ParentID = 785，SeqID = 1，名称=孙子2.3.1
- Parent1 have ID=32, ParentID=-1,SeqID=1,Name="Parent1"
- Child1.2 have ID=412, ParentID=32,SeqID=2, Name="Child1.2"
- Grandson 1.2.1 have ID=231, ParentID=412, SeqID=1, Name="grandson 1.2.1"
- Parent2 will have ID=345,ParentID=-1,SeqID=2,Name="Parent2"
- Child2.3 with have ID=785, ParentID=345, SeqID=3, Name="Child 2.3"
- Grandson 2.3.1 will have ID=854, ParentID=785, SeqID=1, Name= "grandson 2.3.1"
最好的方法是什么？
是否可以用linq来完成它？
谢谢！
推荐答案
您的树可以概括为 m-ary树。鉴于此，可以通过对该树执行深度优先遍历（DFT）来计算平面列表。我怀疑这将是最快的，因为LINQ不假定您的数据结构具有任何确定的结构。 这是一篇关于二叉搜索树的DFT的快速文章-对于M元树的DFT是对该概念的抽象。
Your tree can be generalized as an m-ary tree. Given that, your flat list can be calculated by performing a depth first traversal (DFT) of that tree. I suspect that will be fastest as LINQ does not assume your data structure has any definite structure. Here's a quick article on DFT for binary search trees - DFT for m-ary trees is an abstraction on that concept.
您的任何状态变量似乎都不自然排序。您必须想出一些方法来断开孩子之间的联系（例如，为什么在Parent2之前先访问Parent1-一些比较器告诉算法首先访问Parent1）。比较可以基于诸如生成顺序之类的简单操作（例如，最老的孩子优先）。如下面的评论中所述，对SeqID进行比较以选择下一个要聚焦的焦点节点。
There seems to be no natural ordering of any of your state variables. You'll have to come up with some ways of breaking ties between children (e.g. why is Parent1 visited before Parent2 - some comparator told the algorithm to visit Parent1 first). The comparison could be based on something as simple as order of generation (e.g. oldest child first). As is mentioned in a comment below, compare on SeqID to select the next focus node to recurse on.
这篇关于从树顺序创建的树创建平面列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
