Về mặt chức năng đi qua một cây trong C#

Question

Xem xét các phương pháp khuyến nông sau trong C#, Traverse:

IEnumerable<T> Traverse<T>(this IEnumerable<T> source, 
           Func<T, IEnumerable<T>> fnRecurse); 

Phương pháp này cho phép một để recurse thông qua một cây theo quy định của T và bất cứ chức năng gây T để trở subnodes của nó.

Bây giờ xem xét việc thực hiện sau đây của T:

class Node 
{ 
    public string Name; 
    public List<Node> Children; 
} 

Mục tiêu của tôi là để viết hàm ngắn nhất có thể mà sẽ trả về một IEnumerable chứa các đường dẫn đầy đủ cho tất cả các nút trong cây này. Một cái gì đó như:

var node = GetParentNode(); 
return node.Traverse(node => node.Children) 
      .Select(node => GetParentName(node) + ":" + node.Name); 

Rõ ràng, việc thêm thuộc tính Gốc vào Nút làm cho vấn đề trở nên tầm thường. Thay vào đó, tôi muốn xây dựng các chuỗi phụ huynh của tôi bên trong một functor bằng cách nào đó. Tôi không nghĩ rằng điều này sẽ là quá khó trong C + + nhưng tôi không thấy làm thế nào để làm điều đó trong C#. Bất kỳ ý tưởng?

Answer 1

Tôi nghĩ mẹo không đơn giản là không chuyển xuống loại Node. Thay vào đó, hãy chuyển xuống số Node và đó là đường dẫn đủ điều kiện. Ví dụ:

var node = GetTheStartNode(); 
var start = new { Path = node.Name; Node = node }; 
var paths = 
    start 
    .Traverse(x => x.Node.Children.Select(
     c => new { .Path = x.Path + ":" c.Name; .Node=c)) 
    .Select(x => x.Path); 

Answer 2

Tôi không nghĩ bạn có thể tránh tìm kiếm cây cho đến khi bạn tìm thấy nút bạn đang tìm kiếm mà không lưu trữ một con trỏ mẹ.

Bạn sẽ bắt đầu từ gốc. Kiểm tra nút hiện tại cho phù hợp. Nếu nó là một trận đấu, hãy trả lại nút hoặc chỉ tên (như một danh sách của một phần tử này). Nếu không, nếu đây là nút lá, trả về null. Nếu không phải là một chiếc lá, thì đó là con cái và nếu các con trả lại giá trị không null, hãy thêm nút hiện tại vào danh sách của bạn và trả về nó.

Trả về cuộc gọi ban đầu, null có nghĩa là không tìm thấy kết quả phù hợp. Nếu không, bạn sẽ có danh sách các nút theo thứ tự.

Answer 3

rõ ràng và giải pháp tái sử dụng nhất:

Tạo một phương pháp chung mà liệt kê tất cả pathes thể:

static IEnumerable<IEnumerable<T>> ComputePaths<T>(T Root, Func<T, IEnumerable<T>> Children) { 
    yield return new[] { Root }; 
    foreach (var Child in Children(Root)) 
     foreach (var ChildPath in ComputePaths(Child, Children)) 
      yield return new[] { Root }.Concat(ChildPath);    
} 

Kết quả là liệt kê có thể dễ dàng chuyển đổi thành chuỗi đại diện của bạn.

// All paths 
    var Paths = ComputePaths(Test, x => x.Children); 

    // Compute string representation 
    var StrPaths = from p in Paths select string.Join(":", p.Select(t => t.Name).ToArray()); 

    foreach(var p in StrPaths) 
     Console.WriteLine(p);