遞歸非二進制，非排序樹搜索使用C＃lambas

Question

class TreeNode 
{ 
    public string Value { get; set;} 
    public Collection<TreeNode> Nodes { get; set;} 


    public TreeNode() 
    { 
     Nodes = new Collection<TreeNode>(); 
    } 
} 

1）你怎麼會寫假設值是唯一的遞歸lambda表達式與特定值（或空返回樹節點，如果沒有找到）？當然＃1可以用＃2來回答，但我想如果你知道沒有重複的話可能會有更高效的方式。

2）假設值不是唯一的，而是現在返回一個匹配列表？

Answer 1

編輯：更正了代碼，實際上我編譯和測試了這兩個代碼段，但是我在修復它們之前必須粘貼到VS中。對於那個很抱歉。

我已經添加了一個Subversion存儲庫代碼，包括單元測試，以確保它現在按預期工作，是here，使用用戶名和密碼作爲'guest'登錄，沒有引號。

---

像這樣：

：查找第一

Func<TreeNode, String, TreeNode> findNode = null; // satisfy recursion re-use 
findNode = (n, value) => 
{ 
    if (n == null) return n; 
    if (n.Value == value) return n; 
    foreach (var subNode in n.Nodes) 
    { 
     TreeNode foundNode = findNode(subNode, value); 
     if (foundNode != null) return foundNode; 
    } 
    return null; 
}; 

請注意，這裏的陷阱是，對於一個拉姆達或者是遞歸的一個代表，你需要聲明的變量首先，使用已知的值，在將實際委託分配給它之前。否則編譯器會抱怨你在給定值之前使用了一個變量。

：找到所有

Func<TreeNode, String, List<TreeNode>> findNodes = null; 
findNodes = (n, value) => 
{ 
    var result = new List<TreeNode>(); 
    if (n == null) return result; 
    if (n.Value == value) result.Add(n); 
    foreach (var subNode in n.Nodes) 
    { 
     result.AddRange(findNodes(subNode, value)); 
    } 
    return result; 
}; 

訣竅是在這裏只是收集了每個級別上的節點，並聚集向上。

Answer 2

這個怎麼樣..

public class Node<T> where T:IComparable 
{ 
    public T Value { get; set; } 

    public IList<Node<T>> Children { get; set; } 

    public override string ToString() 
    { 
     return Value.ToString(); 
    } 

    public static Func<T, Node<T>, Node<T>> GetFindFirstFunc() 
    { 
     Func<T, Node<T>,Node<T>> func = null; 
     func = (value,currentNode) => 
      { 
       if (currentNode.Value.CompareTo(value) == 0) 
       { 
        return currentNode; 
       } 
       if (currentNode.Children != null) 
       { 
        foreach (var child in currentNode.Children) 
        {        
         var result = func(value, child); 
         if (result != null) 
         { 
          //found the first match, pass that out as the return value as the call stack unwinds 
          return result; 
         } 
        } 
       } 
       return null; 
      }; 
     return func; 
    } 

    public static Func<T, Node<T>, IEnumerable<Node<T>>> GetFindAllFunc() 
    { 
     Func<T, Node<T>, IEnumerable<Node<T>>> func = null; 
     List<Node<T>> matches = new List<Node<T>>(); 
     func = (value, currentNode) => 
     { 
      //capture the matches List<Node<T>> in a closure so that we don't re-create it recursively every time. 
      if (currentNode.Value.CompareTo(value) == 0) 
      { 
       matches.Add(currentNode); 
      } 
      if (currentNode.Children != null) 
      { 
       //process all nodes 
       foreach (var child in currentNode.Children) 
       { 
        func(value, child); 
       } 
      } 
      return matches; 
     }; 
     return func; 
    }  
} 

下面是調用代碼：

static void Main(string[] args) 
    { 
     Node<int> rootNode = new Node<int> 
     { 
      Value = 1, 
      Children = new List<Node<int>> 
      { 
       new Node<int> 
       { Value = 2, 
           Children = new List<Node<int>> 
           { 
            new Node<int>{ Value = 7}, 
            new Node<int>{ Value = 4}                
           } 
       }, 
       new Node<int> 
       { Value = 5, 
           Children = new List<Node<int>> 
           { 
            new Node<int>{ Value = 6}, 
            new Node<int>{ Value = 7}                
           } 
       } 
      } 
     }; 


     Func<int, Node<int>, Node<int>> findFirst = Node<int>.GetFindFirstFunc(); 
     var firstValue = findFirst(7, rootNode);   



     Func<int, Node<int>, IEnumerable<Node<int>>> findAll = Node<int>.GetFindAllFunc(); 
     var allvalues = findAll(7, rootNode);   
    }