Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.0k views
in Technique[技术] by (71.8m points)

c# - Depth-first flattened collection of an object hierarchy using LINQ

I have an object hierarchy (MasterNode -> ChildNodes) where master and child nodes are of the same type, and there are only two levels (top level and children) like this ('A' is parent of D,E and F, 'B' is parent of G, etc)

A--+
|  D
|  E
|  F
|
B--+
|  G
|
C--+
   H
   I

Suppose I have a MasterNodes as an IEnumerable of the parent objects (A,B,C) and given a parent object X I can get an IEnumerable of its children by X.children

I know that I can enumerate all of the leaf (child nodes) with the SelectMany method or by using

from parent in Masternodes
from child in parent.children
select child

This will give me this sequence:

[D,E,F,G,H,I]

,but this is not what I am asking for.

What is the LINQ query to get a depth-first sequence of the objects in the MasterNodes collection? (return first parent then all of its children then next parent then all of its children etc etc)

The expected result should be a sequence like this:

[A,D,E,F,B,G,C,H,I]

UPDATE:

I am asking for pure .NET ready LINQ. I know that I can define my own methods to do things, but I want something that is based only on the framework provided methods.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

If you have a class like below

public class Node
{
    public string Name;
    public List<Node> Children = new List<Node>();
}

your linq would be

 Func<IEnumerable<Node>, IEnumerable<Node>> Flatten = null;
 Flatten = coll => coll.SelectMany(n=>n.Concat(Flatten(n.Children)));

Test Code:

Node[] roots = new Node[]{ new Node(){Name="A"},new Node(){Name="B"},new Node(){Name="C"} };
roots[0].Children.Add(new Node(){Name="D"});
roots[0].Children.Add(new Node(){Name="E"});
roots[0].Children.Add(new Node(){Name="F"});

roots[1].Children.Add(new Node(){Name="G"});

roots[2].Children.Add(new Node(){Name="H"});
roots[2].Children.Add(new Node(){Name="I"});

Func<IEnumerable<Node>, IEnumerable<Node>> Flatten = null;
Flatten = coll => coll.SelectMany(n=>n.Concat(Flatten(n.Children)));

var result = String.Join(",",Flatten(roots).Select(x=>x.Name));

Console.WriteLine(result);

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...