Tìm nút khi đi ngang qua cây

Question

Tôi muốn triển khai phương pháp cho phép tôi tìm nút trong cây. Cách tôi làm điều đó là đệ quy bằng cách sử dụng các biến toàn cầu để biết khi nào nên dừng lại.

Tôi có lớp:

class Node // represents a node in the tree 
{ 
    // constructor 
    public Node() { 
      Children = new List<Node>(); 
    } 

    public List<Node> Children; 
    public string Name; 
    public string Content;    
} 

Và phương pháp tôi có ngay bây giờ là:

private bool IsNodeFound = false; // global variable that I use to decide when to stop 

    // method to find a particular node in the tree 
    private void Find(Node node, string stringToFind, Action<Node> foundNode) 
    { 
     if(IsNodeFound) 
      return; 

     if (node.Content.Contains(stringToFind)){ 
      foundNode(node); 
      IsNodeFound =true;    
     } 

     foreach (var child in node.Children) 
     { 
      if (child.Content.Contains(stringToFind)){ 
       foundNode(node); 
       IsNodeFound =true;    
      } 

      Find(child, stringToFind, foundNode); 
     } 

    } 

và cách tôi sử dụng Find phương pháp là như sau:

// root is a node that contain children and those children also contain children 
    // root is the "root" of the tree 
    IsNodeFound =false; 
    Node nodeToFind = null; 
    Find(root, "some string to look for", (x)=> nodeToFind=x); 

Vì vậy, câu hỏi của tôi là làm thế nào tôi có thể làm cho phương pháp này thanh lịch hơn. Tôi sẽ giống như chữ ký của phương thức để trông giống như:

public Node FindNode(Node rootNode); 

Tôi nghĩ rằng đó là thừa những gì tôi đang làm và có lẽ là cách tốt hơn để tạo phương pháp đó. Hoặc có lẽ tôi có thể thay đổi lớp Node để tôi có thể đạt được điều tương tự với truy vấn LINQ.

Answer 1

tôi sẽ làm điều đó theo cách này:

Viết một phương pháp dụ để tạo ra một cây con của một nút (bạn có thể làm cho nó một phần mở rộng nếu bạn không kiểm soát lớp Node):

public IEnumerable<Node> GetNodeAndDescendants() // Note that this method is lazy 
{ 
    return new[] { this } 
      .Concat(Children.SelectMany(child => child.GetNodeAndDescendants()));  
} 

Sau đó, bạn chỉ có thể tìm thấy các nút với một chút LINQ:

var foundNode = rootNode.GetNodeAndDescendants() 
         .FirstOrDefault(node => node.Content.Contains(stringToFind)); 

if(foundNode != null) 
{ 
    DoSomething(foundNode); 
} 

Answer 2

Cân nhắc tạo API giống LINQ: chia các phần "Tìm" và "Hành động" để làm cho nó trở nên đơn giản. Bạn thậm chí có thể không cần bất kỳ mã tùy chỉnh đặc biệt nào cho phần "Hành động", LINQ hiện tại sẽ làm.

public IEnumerable<Node> Where(Func<Node, bool> condition); 

Tùy thuộc vào nhu cầu của bạn, bạn có thể đi bộ toàn bộ cây một lần và kiểm tra từng nút để triển khai ở đâu hoặc làm đúng với lặp lại lười biếng. Để lặp lại lười biếng, bạn sẽ cần một số loại cấu trúc ghi nhớ vị trí hiện tại (nghĩa là ngăn xếp các nút truy cập và chỉ mục của con).

Lưu ý: vui lòng tránh sử dụng các biến toàn cục. I E. trong mã hiện tại của bạn chỉ đơn giản là trả về true/false từ hàm Find và dừng lặp lại khi true được trả về sẽ là cách tiếp cận tốt hơn.

Answer 3

bạn có thể sử dụng một trong những câu trả lời khác mà sử dụng LINQ, hoặc bạn có thể sử dụng một cơ chế tìm kiếm theo chiều sâu sử dụng rec ursion:

public Node Find(string stringToFind) 
{ 
    // find the string, starting with the current instance 
    return Find(this, stringToFind); 
} 

// Search for a string in the specified node and all of its children 
public Node Find(Node node, string stringToFind) 
{ 
    if (node.Content.Contains(stringToFind)) 
     return node; 

    foreach (var child in node.Children) 
    { 
     var result = Find(child, stringToFind); 
     if (result != null) 
      return result; 
    } 

    return null; 
} 

Answer 4

Nếu LINQ trả lời nhầm lẫn với bạn, đây là cách tôi sẽ làm điều đó với đệ quy đơn giản. Lưu ý nó là chiều sâu đầu tiên, bạn có thể muốn thay đổi nó thành chiều rộng đầu tiên nếu điều đó có ý nghĩa hơn cho mô hình của bạn.

public Node FindNode(Node rootNode) 
{ 
    if (rootNode.Content.Contains(stringToFind)) 
     return rootNode; 

    foreach (Node node in rootNode.Children) 
    { 
     if (node.Content.Contains(stringToFind)) 
      return node; 
     else 
      return FindNode(node); 
    } 

    return null; 
} 

Answer 5

Bạn có thể sử dụng một tìm kiếm theo chiều sâu sử dụng đệ quy (không cần cho một biến toàn cầu để biết khi nào chấm dứt):

Node FindNode1(Node rootNode, string stringToFind) { 
    if(rootNode.Content == stringToFind) return rootNode; 
    foreach(var child in rootNode.Children) { 
     var n = FindNode1(child, stringToFind); 
     if(n != null) return n; 
    } 
    return null; 
} 

Hoặc, nếu bạn muốn tránh đệ quy, bạn có thể thực hiện được điều tương tự không đệ quy với một chồng:

Node FindNode2(Node rootNode, string stringToFind) { 
    var stack = new Stack<Node>(new[] { rootNode }); 
    while(stack.Any()) { 
     var n = stack.Pop(); 
     if(n.Content == stringToFind) return n; 
     foreach(var child in n.Children) stack.Push(child); 
    } 
    return null; 
} 

Answer 6

Đệ quy và PLINQ

private Node Find(Node node, Func<Node, bool> predicate) 
    { 
     if (predicate(node)) 
      return node; 

     foreach (var n in node.Children.AsParallel()) 
     { 
      var found = Find(n, predicate); 
      if (found != default(Node)) 
       return found; 
     } 
     return default(Node); 
    } 

Và mã gọi:

 var found = Find(root, (n) => n.Content.Contains("3")); 
    if (found != default(Node)) 
     Console.Write("found '{0}'", found.Name); 
    else Console.Write("not found");