반전 수심 먼저 검색 또는 예약 주문 탐색

Question

의 나는,이 같은 높이 2의 완전한 바이너리 그래프 있다고 가정 해 봅시다 : 2로 0에서 1까지의 가장자리와 0 거기

  0 
    1  2 
    3  4 5  6 

1 3, 1 내지 4, 2 내지 5, 및 2 내지 6 일 수있다.

노드 (node)를 프리 - 엠 퍼시스 처리를 수행함으로써 깊이 우선 탐색 순서 (0, 1, 3, 4, 2, 5, 6) 순서 탐색.

선행 순회, 순회 순회 또는 순서 순회에서 역으로 알고리즘을 얻는 방법은 비교적 간단합니다. 각 레벨에서 처음부터 오른쪽으로 이동 한 다음 왼쪽으로 이동하면됩니다. (0, 2, 6, 5, 1, 4, 3)?

나는 상당한 금액을 둘러 보았고 적용 가능한 것을 찾지 못했습니다.

N.B. 왜 내가 원하는지 궁금해하는 경우 DFS를 기반으로하는 검색 알고리즘을 사용하므로 그래프의 왼쪽에있는 노드가 오른쪽의 노드보다 더 빨리 발견됩니다. 나는 평범한 왼쪽에서 오른쪽으로 dfs를, 다른 하나를 오른쪽에서 왼쪽으로 뒤집어서 병렬 프로세스를 실행하는 것에 대해 생각하고있다.

Answer 1

DFS에서 왼쪽 잎에 재귀 함수를 호출하고 할 수 없을 때까지 계속 수행 한 다음 오른쪽 리프에서 한 레벨 위로 올린 다음 왼쪽에서 계속 호출하면 계속 남겨 둡니다 하위.

대신 왼쪽으로 오른쪽과 모든 오른쪽으로 왼쪽으로 전환 한 다음 모든 오른쪽 잎을 가로 지르고 더 이상 오른쪽 잎을 통과 할 수없는 경우 왼쪽 잎을 가로 질러 이동할 수 있습니다.