태그 보관물: trees

trees

재귀를 사용하지 않고 나무를 횡단하는 방법은 무엇입니까? 작업을 수행해야합니다. 순회는 이와 같이 작동합니다. private

메모리 노드 트리가 매우 커서 트리를 통과해야합니다. 각 자식 노드의 반환 값을 부모 노드로 전달합니다. 모든 노드가 루트 노드까지 데이터 버블을 가질 때까지이 작업을 수행해야합니다.

순회는 이와 같이 작동합니다.

private Data Execute(Node pNode)
{
    Data[] values = new Data[pNode.Children.Count];
    for(int i=0; i < pNode.Children.Count; i++)
    {
        values[i] = Execute(pNode.Children[i]);  // recursive
    }
    return pNode.Process(values);
}

public void Start(Node pRoot)
{
    Data result = Execute(pRoot);
}

이것은 잘 작동하지만 호출 스택이 노드 트리의 크기를 제한한다고 걱정됩니다.

재귀 호출을하지 않도록 코드를 어떻게 다시 작성할 수 Execute있습니까?

답변

다음은 재귀를 사용하지 않는 범용 트리 순회 구현입니다.

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

귀하의 경우 다음과 같이 호출 할 수 있습니다.

IEnumerable<Node> allNodes = Traverse(pRoot, node => node.Children);

깊이 대신 검색을 위해 먼저 호흡 Queue대신 a Stack를 사용하십시오 . PriorityQueue최상의 첫 검색을 위해를 사용하십시오 .

답변

사전에 나무 깊이에 대한 추정치가 있다면 사례가 스택 크기를 조정하는 것으로 충분합니까? 버전 2.0 이후의 C #에서는 새 스레드를 시작할 때마다 가능합니다. 여기를 참조하십시오.

http://www.atalasoft.com/cs/blogs/rickm/archive/2008/04/22/increasing-the-size-of-your-stack-net-memory-management-part-3.aspx

그렇게하면 더 복잡한 것을 구현하지 않고도 재귀 코드를 유지할 수 있습니다. 물론 자신의 스택으로 비 재귀 솔루션을 만드는 것이 시간과 메모리 효율성이 더 높을 수 있지만 코드가 지금처럼 간단하지 않을 것이라고 확신합니다.

답변

재귀를 사용하지 않고 트리 형태로 데이터 구조를 순회 할 수 없습니다. 언어에서 제공하는 스택 프레임 및 함수 호출을 사용하지 않으면 기본적으로 자체 스택 및 함수 호출을 프로그래밍해야합니다. 가능성 당신이 그것을 어떻게 관리하는 내 컴파일러 작가가 프로그램을 실행할 것이라는 시스템에서보다 더 효율적인 방법으로 방식으로 언어.

따라서 자원 제한에 대한 두려움으로 인해 재귀를 피하는 것은 일반적으로 잘못된 것입니다. 확실히, 조기 리소스 최적화는 항상 잘못 안내되지만,이 경우 메모리 사용량이 병목 상태인지 측정하고 확인하더라도 시스템 수준을 떨어 뜨리지 않으면 서 향상시킬 수 없을 것입니다. 컴파일러 라이터.

답변