나무 걷기, 부모가 먼저

StackOverflow https://stackoverflow.com/questions/1616332

  •  06-07-2019
  •  | 
  •  

문제

연결된 트리의 모든 노드를 방문하여(모든 노드에는 상위 및 모든 하위 노드에 대한 참조가 있고 루트 노드에는 상위 노드가 null임) 상위 노드 이전에 노드를 방문하지 않는 가장 좋은 방법은 무엇입니까?비재귀적 브라우니 포인트.

도움이 되었습니까?

해결책

의사 코드 :

NodesToVisit = some stack or some list
NodesToVisit.Push(RootNode)

While NodesToVisit.Length > 0
{
   CurNode = NodesToVisit.Pop()
   For each Child C in CurNode
        NodesToVisit.Push(C)
   Visit(CurNode) (i.e. do whatever needs to be done)
}

편집하다: 재귀입니까?
기술적으로 정확 하고이 게시물의 Andreyt와 다른 사람들이 지적한 바와 같이,이 접근법은 다음과 같습니다. 의 형태 CPU 스택 대신에 명시 적으로 관리되는 스택이 사용되는 재귀 알고리즘과 while 루프 수준에서 재귀가 발생하는 곳입니다. 이것은 재귀 구현과 다릅니다 그 자체 미묘하지만 중요한 방법으로 :

  • "변수"만 스택에 밀려 나옵니다. 스택에는 "스택 프레임"과 관련 리턴 주소가 없으며 유일한 "반환 주소"는 while 루프에 암시되어 있으며 하나의 인스턴스 만 있습니다.
  • "스택"은 로직을 제동하지 않고 다음 "프레임"을 목록의 어느 곳에서나 가져갈 수있는 목록으로 사용할 수 있습니다.

다른 팁

당신은 선주문 횡단을 찾고 있습니다. 나는 당신이 대기열로 반복적으로 할 수 있다고 생각합니다. 의사 코드에서 :

빈 큐를 만들고 루트 노드를 밀어 넣으십시오.

while nonempty(q)
  node = pop(q)
  visit(node)
  foreach child(node)
    push(q,child)

모든 하위 항목과 상위 항목에 대한 링크가 있는 경우 비재귀 알고리즘은 매우 간단합니다.당신에게 나무가 있다는 사실을 잊어버리세요.각 부모-자식 링크가 한 교차점에서 다른 교차점으로 이어지는 일반적인 양방향 복도인 미로라고 생각하세요.미로 전체를 걷기 위해 해야 할 일은 각 교차로에서 왼쪽에 있는 다음 복도로 들어가는 것뿐입니다.(또는 왼손이 항상 왼쪽 벽에 닿은 채로 미로를 걷는다고 생각하십시오.)루트 교차점에서 시작하여 어느 방향으로든 이동하면 항상 자식보다 먼저 부모를 방문하여 전체 트리를 걷게 됩니다.이 경우 각 "복도"는 두 번(한 방향과 다른 방향으로) 이동하며, 각 "교차점"(노드)은 합류하는 "복도" 수만큼 방문하게 됩니다.

노드 세트를 사용하십시오. 세트에 루트를 넣어 시작하십시오. 그런 다음 루프에서 세트에서 노드를 꺼내서 방문한 다음 어린이를 세트에 넣습니다. 세트가 비어 있으면 완료됩니다.

의사 코드에서 :

currentList = list( root )
nextList = list()
while currentList.count > 0:
    foreach node in currentList:
        nextList.add(node.children)
    currentList = nextList

루트 노드에서 시작하여 이미 방문한 노드의 부모/자녀 만 방문하면 절대 안돼 조상을 방문하기 전에 노드를 방문하도록 나무를 가로 지르십시오.

모든 종류의 횡단, 깊이 (재귀/스택 기반), 너비 먼저 (대기열 기반), 깊이 제한 또는 정렬되지 않은 세트에서 꺼내는 것이 작동합니다.

"가장 좋은"방법은 트리에 따라 다릅니다. 너비는 먼저 가지가 거의없는 매우 키 큰 나무에 잘 작동합니다. 깊이는 먼저 많은 가지가있는 나무에 잘 작동합니다.

노드에는 실제로 부모에게 포인터가 있기 때문에 일정한 메모리 알고리즘도 있지만 훨씬 느립니다.

공간 복잡성이 종종 특정 검색 알고리즘의 골이이기 때문에 폭이 넓은 첫 번째 검색에 동의하지 않습니다. 아마도 반복 심화 알고리즘을 사용하는 것은 이러한 유형의 사용을위한 더 나은 대안이며, 폭이 넓은 첫 번째 검색과 동일한 유형의 트래버스를 다룹니다. 폭이 먼저 검색에서 프린지를 다루는 데 약간의 차이가 있지만 (의사) 코드를 너무 어렵지 않아야합니다.

참조:http://en.wikipedia.org/wiki/iterative_deepening

여기에 있습니다 진심으로 비수체 적 접근 : 스택 없음, 일정한 공간. 이 파이썬 코드는 각 노드가 어린이 목록을 포함하고 노드 객체가 평등을 정의하지 않으므로 '인덱스'함수가 ID를 비교하도록 가정합니다.

def walkTree(root, visit_func):
    cur  = root
    nextChildIndex = 0

    while True:
        visit_func(cur)

        while nextChildIndex >= len(cur.children) and cur is not root:
            nextChildIndex = cur.parent.children.index(cur) + 1
            cur  = cur.parent

        if nextChildIndex >= len(cur.children):
            break

        cur = cur.children[nextChildIndex]
        nextChildIndex = 0

나는 그것이 약간 세련되고, 간결하고 읽기 쉬운 것을 쉽게 만들 수 있다고 확신하지만, 그것이 요점입니다.

루트 (레벨 0)에 노드 목록을 구축하고, 각 노드를 차례로 반복하고 직접 어린이를 찾으십시오 (부모 노드는 현재보고있는 노드입니다) (레벨 1) (레벨 0으로 끝나면 1) 레벨 1 등을 반복하는 것 등으로, 나머지 방문되지 않은 노드가 없을 때까지.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top