遍歷樹時查找節點

Question

我想實現一種方法，使我能夠在樹中查找節點。我這樣做的方式是遞歸地使用全局變量來知道何時停止。

我有類：

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;    
} 

而我現在所擁有的方法是：

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); 
     } 

    } 

我用的查找方法是喜歡的方式：

// 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); 

所以我的問題是我該如何使這種方法更優雅。我會想方法的簽名看起來像：

public Node FindNode(Node rootNode); 

我認爲這是冗餘我在做什麼，並有可能創造方法的更好的方法。或者也許我可以改變Node類，這樣我就可以用linq查詢來實現同樣的功能。

Answer 1

我會做這種方式：

寫一個實例方法來產生一個節點的子樹（你可以把它的擴展，如果你不控制Node類）：

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

然後，你可以找到與節點LINQ的一點：

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

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

Answer 2

考慮製作類似LINQ的API：拆分「查找」和「動作」部分以簡化操作。您可能甚至不需要任何特殊的「Act」部分的自定義代碼，現有的LINQ將會這樣做。

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

根據您的需求，你既可以走整棵樹一次，並檢查各節點來實現凡，或慵懶反覆做正確。對於懶惰的迭代，你需要某種記住當前位置的結構（即訪問節點的堆棧和子節點的索引）。

注意：請避免使用全局變量。即在你當前的代碼中，只需從Find函數返回true/false，並在返回true時停止迭代將是更好的方法。

Answer 3

您可以使用使用Linq其他的答案，或者你可以使用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

如果linq的答案和我一樣困惑，那麼我將如何用簡單的遞歸來實現。首先注意它的深度，如果這對您的模型更有意義，您可能需要先將其更改爲寬度。

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

您可以使用遞歸使用深度優先搜索（不需要一個全局變量來判斷何時終止）：

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; 
} 

或者，如果你希望避免遞歸，你可以完成同樣的事情非遞歸用棧：

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

遞歸，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); 
    } 

而調用代碼：

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