[알고리즘] 트리 순회(Tree Traversal)

 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회(tree traversal)라고 한다.

 

 선형 자료 구조(stack, queue 등)는 순차적으로 요소에 접근하지만, 트리 구조는 계층적 구조라는 특징을 갖고 있기 때문에 모든 노드를 순회하기 위해서는 다른 방식을 사용해야 한다.

 

 트리를 순회하는 방법은 크게 전위 순회, 중위 순회, 후위 순회가 있으며, 노드를 방문하는 순서에 의해 결정된다.

 

 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽으로 한다.

 

 

 

 

전위 순회(preorder traversal)

 전위 순회는 다음과 같은 방법으로 진행한다.

 

1. 루트 또는 서브트리의 루트 노드를 방문한다.
2. 왼쪽 서브 트리를 방문한다.
3. 오른쪽 서브 트리를 방문한다.

방문 순서 : 1 -> 2 -> 4 -> 5 -> 3

 

 

 

 

중위 순회(inorder traversal)

중위 순회는 다음과 같은 방법으로 진행한다.

 

1. 왼쪽 서브 트리를 방문한다.
2. 루트 또는 서브 트리의 루트 노드를 방문한다.
3. 오른쪽 서브 트리를 방문한다.

방문 순서 : 4 -> 2 -> 5 -> 1 -> 3

 

 

 

 

후위순회(postorder traversal)

후위 순회는 다음과 같은 방법으로 진행한다.

 

1. 왼쪽 서브 트리를 방문한다.
2. 오른쪽 서브 트리를 방문한다.
3. 루트 또는 서브 트리의 루트 노드를 방문한다.

방문 순서 : 4 -> 5 -> 2 -> 1 -> 3