[알고리즘] Tree Traversal

Traversal 이란

트리의 노드들을 지정된 순서대로 방문하는 것이다.

• 전위 순회 (Preorder Traversal)
• 중위 순회 (Inorder Traversal)
• 후위 순회 (Postorder Traversal)
• Level Traversal

위와 같이 여러 종류의 순회가 있는데 각각 방문하는 순서(?)가 다르다.

전위 순회 (Preorder Traversal)

1. 루트 노드를 방문한다.
2. 왼쪽 서브트리를 전위 순회한다.
3. 오른쪽 서브트리를 전위 순회한다.

중위 순회 (Inorder Traversal)

1. 왼쪽 서브트리를 중위 순회한다.
2. 루트 노드를 방문한다.
3. 오른쪽 서브트리를 중위 순회한다.

후위 순회 (Postorder Traversal)

1. 왼쪽 서브트리를 후위 순회한다.
2. 오른쪽 서브트리를 후위 순회한다.
3. 루트 노드를 방문한다.

정리

이걸 그냥 단순 암기하려고 하면 은근히 필요할 때 기억이 안나서
나는 이렇게 생각한다.

기본적으로 좌->우 방향인데 루트 노드를 방문하는 순서에 따라 정해지는 것.

루트노드를 먼저 방문하면 전위(pre) -> 루트-왼쪽-오른쪽
루트노드를 중간에 방문하면 중위(inorder) -> 왼쪽-루트-오른쪽
루트노드를 나중에 방문하면 후위(post) -> 왼쪽-오른쪽-루트

이렇게 이해하고 있으니 기억이 안나도 조금만 생각하고 나면 구현할 수 있었다.

구현을 할 때는 기본적으로 깊이 우선 탐색을 이용하여 하면쉽고,
개인적으로 서브트리에도 같은 방식(?)의 순회를 해줘야하기 때문에
재귀를 이용하여 풀면 직관적이고 좋다. 물론 스택을 이용해도 된다.

...
...

Level Traversal

전위, 중위, 후위 순회랑 다르게 살짝 외톨이 같은 녀석이라 따로 정리한다.

말 그대로 루트 노드부터 레벨 단위로 한 층씩 내려오면서 순회하는 방식이다.
자연스럽게 너비 우선 탐색 방식이 되겠고 큐를 이용하여 구현하면 간단하다.

어려울 것 없다.
끗