使用多個根節點展開IEnumerable並選擇Id屬性

我有以下層次結構，我需要將其平鋪並選擇所有Id s。我試過使用SelectMany()這樣的.SelectMany(node => node.Children).Select(node => node.Id)。這將導致列表3,5,6。是否有可能使用Linq獲得完整列表1,2,3,4,5,6,7？使用多個根節點展開IEnumerable並選擇Id屬性

節點（ID = 1）
節點（ID = 2）
- 節點（ID = 3）
節點（ID = 4）
- 節點（同上= 5）
- 節點（Id = 6）
  - 節點（Id = 7）

來源

2014-01-18 Marcus

孩子節點的子類型？ –

@SergeyBerezovskiy不，Node和Child是同一類型的。我更新了我的問題，使其更加清晰。 – Marcus

[使用LINQ搜索樹]（http://stackoverflow.com/questions/7062882/searching-a-tree-using-linq）應該讓你知道該怎麼做。 – Dirk

您可以使用下面的擴展方法壓扁層次結構（見下文答案更新替代扁平化算法）：

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector) 
{ 
    foreach (var item in source) 
    { 
     yield return item; 

     var children = childrenSelector(item); 
     if (children == null) 
      continue; 

     foreach (var child in children.Flatten(childrenSelector)) 
      yield return child;     
    } 
}

我需要孩子選擇和遞歸得到孩子。然後將投射很簡單：

var result = nodes.Flatten(n => n.Children).Select(n => n.Id);

假定你有以下節點類：

public class Node 
{  
    public Node(int id, params Node[] children) 
    { 
     Id = id; 
     if (children.Any()) 
      Children = new List<Node>(children); 
    } 

    public int Id { get; set; } 
    public List<Node> Children { get; set; } 
}

與樣品層次

然後：

List<Node> nodes = new List<Node> { 
    new Node(1), 
    new Node(2, new Node(3)), 
    new Node(4, new Node(5), 
       new Node(6, new Node(7))) 
};

輸出將是：

1, 2, 3, 4, 5, 6, 7

UPDATE：您可以拼合層次不遞歸的使用情況（更好的性能）：

public static IEnumerable<T> Flatten<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> childrenSelector) 
{ 
    Queue<T> queue = new Queue<T>(); 
    foreach (var item in source) 
     queue.Enqueue(item); 

    while (queue.Any()) 
    { 
     T item = queue.Dequeue(); 
     yield return item; 
     var children = childrenSelector(item); 
     if (children == null) 
      continue; 

     foreach (var child in children) 
      queue.Enqueue(child); 
    } 
}

來源

2014-01-18 12:48:47

我認爲你的非遞歸版本首先進行廣度遍歷，這可能或可能不重要，但應該注意。（這將導致1,2,4,3,5,6,7） –

@SteveRuble先將其更改爲深度與將「隊列」更改爲「堆棧」一樣微不足道。將其更改爲優先隊列與將其更改爲優先隊列一樣微不足道。 – Servy

容易。

Func<IEnumerable<Node>, IEnumerable<int>> flatten = null; 
flatten = ns => 
{ 
    return ns.Select(n => n.Id) 
     .Concat(ns.SelectMany(n => flatten(n.Children))); 
};

來源

2014-01-18 12:49:34 Enigmativity

您可以拼合與擴展方法層次：

public static IEnumerable<Node> Flatten(this IEnumerable<Node> source) 
{ 
    if(source == null) 
    throw new ArgumentNullException("source"); 

    return FlattenIterator(source); 
} 

private static IEnumerable<Node> FlattenIterator(IEnumerable<Node> source) 
{ 
    foreach(var node in source) 
    { 
    yield return node; 
    foreach(var child in node.Children.Flatten()) 
    { 
     yield return child; 
    } 
    } 
}

然後你可以選擇這樣的ID：

var ids = source.Flatten().Select(n => n.Id);

來源

2014-01-18 12:50:01

使用多個根節點展開IEnumerable並選擇Id屬性

回答

相關問題