Preorder 운행법

Preorder traversal(전위 순회)은 이진 트리에서 가장 일반적으로 사용되는 트리 순회 방법 중 하나입니다. Preorder traversal은 다음과 같이 루트 노드를 방문한 후, 왼쪽 서브트리를 순회하고 오른쪽 서브트리를 순회하는 방식으로 구현됩니다.

1. 현재 노드를 출력
2. 왼쪽 서브트리를 전위 순회
3. 오른쪽 서브트리를 전위 순회

이 방법은 루트 노드에서 시작하여 전체 트리를 방문하고, 각 노드를 한 번씩만 방문하기 때문에 O(n) 시간 복잡도를 갖습니다. Preorder traversal은 이진 트리에서 깊이 우선 탐색(depth-first search) 알고리즘을 구현할 때 유용하게 사용됩니다.

 

Preorder traversal은 이진 트리의 루트를 먼저 방문하고, 왼쪽 서브트리를 재귀적으로 방문한 후, 오른쪽 서브트리를 재귀적으로 방문하는 방법입니다.

예를 들어, 다음과 같은 이진 트리가 있다고 가정해봅시다.

      A
    /   \
   B     C
  / \     \
 D   E     F

Preorder traversal을 수행하면, A -> B -> D -> E -> C -> F 순서로 노드를 방문합니다. 구체적으로는 다음과 같은 과정을 거칩니다.

1. A를 방문합니다.
2. A의 왼쪽 서브트리인 B를 재귀적으로 방문합니다.
   - B를 방문합니다.
   - B의 왼쪽 서브트리인 D를 재귀적으로 방문합니다.
     - D를 방문합니다.
   - B의 오른쪽 서브트리인 E를 재귀적으로 방문합니다.
     - E를 방문합니다.
3. A의 오른쪽 서브트리인 C를 재귀적으로 방문합니다.
   - C를 방문합니다.
   - C의 오른쪽 서브트리인 F를 재귀적으로 방문합니다.
     - F를 방문합니다.

따라서 이 이진 트리의 Preorder traversal 결과는 A -> B -> D -> E -> C -> F 입니다.