재귀가 아닌 이진, 비 정렬 트리 검색을 사용하여 C#을 lambas

Question

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


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

1) 당신은 어떻게 발견되지 않는 경우는 특정 값 (또는 null로의 TreeNode를 반환하는 재귀 람다 식) 값이 고유 한 가정을 작성합니다? 물론 # 1은 # 2를 사용하여 대답 할 수 있지만 중복이 없다면 더 효율적인 방법이있을 것이라고 생각합니다.

2) 값이 고유하지 않고 대신 일치 목록을 반환한다고 가정합니다.

Answer 1

편집 : : 코드를 수정했는데 실제로 두 코드 조각을 모두 컴파일하고 테스트했지만 VS에서 수정하기 전에 버전에 붙여 넣었어야합니다. 미안합니다.

단위 테스트를 포함하여 코드가 Subversion 인 리포지토리를 추가하여 단위 테스트를 포함하여 이제는 예상대로 작동하려면 here이며 사용자 이름과 암호를 모두 '손님'으로 따옴표없이 로그인하십시오. 이처럼

---

:

1 : 여기에 함정이 람다 또는 재귀 될 대리자를 들어, 변수를 선언 할 필요가 있다는 것을 처음

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

주 찾기 먼저 실제 대리자를 할당하기 전에 알려진 값을 사용합니다. 그렇지 않으면 컴파일러는 값이 주어지기 전에 변수를 사용하고 있다고 불평 할 것입니다.

2 : 트릭은 단지 각 수준에서 노드를 수집하기 위해 여기에 모든

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