C에서 n-ary 트리를 접는 방법

Question

n-ary Tree 데이터 구조를 폴드하고 싶습니다.
내가 일하는 해결책을 마련하기 위해 관리 (배는 집계는 Linq에에 일명입니다) :

public static R Aggregate<T, R>(T node, 
      Func<T, IEnumerable<T>> getChildren, 
     Func<T, IEnumerable<R>, R> aggregator) 
{ 
    var childResults = getChildren(node) 
         .Select(c => Aggregate(c, getChildren, aggregator)); 

    return aggregator(node, childResults); 
} 

getChildren가 주어진 노드의 자식을 얻는 방법을 정의하는 FUNC이다. 잎 노드에 대해 빈 IEnumerable을 반환해야합니다.
aggregator은 현재 노드와 그 노드의 결과를 사용하여 노드를 처리하는 방법을 정의합니다.

는

이 솔루션은 작동하는 것 같다하지만 몇 가지 문제가 있습니다

• 알고리즘 재귀되고, 그것은 깊은 나무의 스택을 날려 버리겠다.
  스택 오버플로를 방지하기 위해 함수를 다시 작성할 수 있습니까?

• 알고리즘은 게으르지 만 일종의 알고리즘입니다.
  예 : aggregator이 자식 노드의 결과 만 Enumerable.First을 사용하는 경우 트리의 가장 왼쪽 분기 만 통과합니다. 그러나 Enumerable.Last을 사용하면 계산에 가장 오른쪽 분기 만 필요한 경우에도 전체 트리가 통과됩니다.
  알고리즘을 실제로 게으르게 만들 수 있습니까?

F # 솔루션 환영하지만 C#을 선호합니다. 당신은 스택을 저장하려면 먼저 폭 대신에 깊이 제 1 스위치의, 나무를 통과, 또는 당신의 정확한 요구 사항 일부 트리 탐색 기법 적절한 때

Answer 1

• 당신은 지출 메모리를 가지고있다.

• "적절하게"게으르게 만들기 위해 트래버스에서 수집 자의 연결을 해제하십시오. 게으른 순회를 먼저 구축하고 (원하는 순서대로) 수집기로 전달하십시오.

또한 게으름에 대한 걱정과 관련하여 인터페이스 선택에 대해 확신하지 못합니다. Enumerable.First와 Enumerable.Last는 공급자 (getChildren)의 변경에 따라 동일한 트리에 대해 서로 다른 결과를 산출하므로 왜 게으름을 생각합니까? 그래서 order/traversal scheme (깊이 우선부터 너비까지)은 어 그리 게이터에 고유 한 것이어야하고, 트리 형태로 고정되어야한다고 생각하십니까? 외부 매개 변수가 아닌가?

Answer 2

당신은이 소요되는 스택 공간을 피하기 위해 오히려 재귀보다 명시 적 스택을 사용하여 트리를 탐색 할 수 있습니다

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source 
    , Func<T, IEnumerable<T>> childrenSelector) 
{ 
    var stack = new Stack<T>(source); 
    while (stack.Any()) 
    { 
     var next = stack.Pop(); 
     yield return next; 
     foreach (var child in childrenSelector(next)) 
      stack.Push(child); 
    } 
} 

당신은 다음을 호출 할 때 단순히 아이의 선택을 조정할 수 있습니다 "뒤로"통과하려면 오히려 대신 First의 Last를 호출하는 대신 :

원래 트리를 구축

Traverse(root, node => nodes.Reverse());