먼저 나무를 걸으십시오.

Question

링크 된 트리의 모든 노드를 방문하는 가장 좋은 방법은 (모든 노드는 부모와 모든 자식에 대한 참조를 가지며, 루트 노드는 부모로 null을가집니다), 어떤 노드도 방문하기 전에는 방문하지 않습니다. 그 조상들? 브라우니는 비 재귀 적입니다.

Answer 1

의사 코드 :

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 루프에 암시 적이며 그 중 하나의 인스턴스 만 있습니다.
• "스택"은 논리로 제동하지 않고 다음 "프레임"을 목록의 아무 곳에서나 가져올 수있는 목록으로 사용할 수 있습니다. 루트 노드에서 시작하고, 단지 당신이 이미 방문한 노드의 부모/자녀를 방문하는 경우

Answer 2

루트 (레벨 0)에서 노드 목록을 작성하고 각 노드를 차례로 반복하고 부모 노드가 우리가 현재보고있는 노드 인 직접 자식을 찾습니다 (레벨 1). 레벨 0은 반복 레벨 1로 이동하고, 방문하지 않은 노드가 없을 때까지 계속됩니다.

Answer 3

노드 집합을 사용하십시오. 집합의 루트를 시작합니다. 그런 다음 루프에서 집합에서 노드를 당겨서 방문한 다음 하위 노드를 집합에 넣습니다. 세트가 비어 있으면 완료됩니다. 의사에서

Answer 4

: 당신은 전순 주사를 찾고

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

Answer 5

. 나는 당신이 대기열로 비 재귀 적으로 그것을 할 수 있다고 생각한다. 의사 코드의 경우 :

빈 대기열을 만든 다음 루트 노드를 누릅니다.

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

Answer 6

Breadth First Search

Answer 7

, 당신은 조상을 방문하시기 이전 노드를 방문하도록 트리를 탐색 할 수있는 방법이 없습니다.

깊이 우선 (재귀/스택 기반), 너비 우선 (대기열 기반), 깊이 제한, 또는 순서가 지정되지 않은 집합에서 꺼내기 만하면 작동합니다.

"최상의"방법은 트리에 따라 다릅니다. 넓이는 가지가 거의없는 매우 큰 나무에서 먼저 잘 작동합니다. 깊이가 많은 것은 가지가 많은 나무에서 먼저 잘 작동합니다.

노드에는 실제로 부모에 대한 포인터가 있으므로 상수 메모리 알고리즘도 있지만 속도는 훨씬 느립니다.

Answer 8

모든 하위 링크와 상위 링크가있는 경우 비 재귀 알고리즘은 다소 단순합니다. 너는 나무가 있다는 것을 잊어라. 그것이 각 부모 - 자식 링크가 한 교차점에서 다른 교차점으로의 일반적인 양방향 회랑 인 관례 라 ​​생각하십시오. 모든 미로를 걷기 위해해야 ​​할 일은 각 교차점에서 왼쪽에있는 다음 복도로 넘어지는 것입니다. (또는 왼쪽면의 벽에 항상 손을 대고 미로를 걷는다고 생각하십시오). 루트 교차점에서 시작하여 (어떤 방향 으로든 움직이는 경우) 아이들 앞에서 항상 부모님을 방문하는 전체 트리를 걸을 것입니다. 이 경우 각 "회랑"은 한 방향과 다른 방향으로 두 번 이동하며 각 "교차로"(노드)는 많은 복도가 합류 할 때까지 여러 번 방문됩니다.

Answer 9

공간의 복잡성이 종종 특정 검색 알고리즘의 단점이기 때문에 폭 넓은 첫 번째 검색에 동의하지 않습니다. 아마도 반복적 인 심화 알고리즘을 사용하는 것이 이러한 유형의 사용에 대한 더 나은 대안이며 폭 넓은 첫 번째 검색과 동일한 유형의 탐색을 포함합니다. 폭경 우선 검색에서 프린지를 다루는 데는 사소한 차이가 있지만, (의사) 코드를 작성하기는 너무 어렵지 않습니다.

참조 : 없음 스택, 일정한 공간 : 여기 http://en.wikipedia.org/wiki/Iterative_deepening

Answer 10

는 진정으로 비 재귀 방법입니다. 이 파이썬 코드는 각 노드가 아이의 목록이 포함되어 있다고 가정하고 '인덱스'기능 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 

나는 그것이까지 연마 할 수있는 확신 약간, 더 간결하고 읽기 쉬워졌습니다. 그러나 그것은 요지입니다.