[Java] 트리 순회 알고리즘
트리의 순회 방법에는 3가지가 있다.
- 전위 순회
- 중위 순회
- 후위 순회
한 가지씩 자세히 알아보자.
1. 전위 순회( preorder )
전위 순회란 루트 노드를 가장 먼저 방문하고, 왼쪽과 오른쪽 서브트리를 방문하는 순회 방법이다.
다음과 같은 예제에서 전위 순회 방법을 사용한다면 방문 순서가 어떻게 될까?
루트노드를 가장 먼저 방문해야 하므로 처음엔 0번을 방문할 것이고, 그 다음엔 왼쪽과 오른쪽의 서브트리가 남는다.
왼쪽을 먼저 방문하면, 왼쪽 서브트리에는 또 루트노드인 1이 있다. 따라서 루트노드인 1을 방문하고, 왼쪽 노드와 오른쪽 자식노드인 3, 4를 방문한다.
그렇게 하면 방문 순서는 다음과 같다.
2. 중위 순회( Inorder )
중위 순회는 루트 노드를 중간에 방문하기에 중위 순회라고 생각하면 쉽다. 왼쪽 서브트리를 먼저 방문하고, 다음으로 루트 노드, 마지막으로 오른쪽 서브 트리를 방문하는 순회 방법이다.
이 예제에서 중위 순회를 해 보자. 가장 처음으로 왼쪽을 방문하므로, 왼쪽 서브트리를 따로 보자. 왼쪽 서브트리를 따로 보면 루트노드인 1이 있고 그 아래에 왼쪽 자식노드인 3과 오른쪽 자식노드인 4가 있다. 왼쪽 우선 방문이므로 3을 먼저 방문하고, 다음으로 루트노드인 1을, 마지막으로 오른쪽인 4를 방문한다. 이렇게 하면 왼쪽 서브트리의 방문이 끝났다.
왼쪽이 끝났으면 루트노드인 0을 이어서 방문하고, 남은 오른쪽 서브트리를 방문한다.
오른쪽 서브트리에는 왼쪽노드는 없으므로 루트노드인 2를 방문하고, 5를 방문한다.
이렇게 하면 방문 순서는 아래와 같다.
3. 후위 순회( postorder )
후위 순회란 루트 노드를 가장 마지막에 방문하는 순회 방법이다. 왼쪽을 먼저 방문하고 나서 오른쪽을 방문하고, 루트를 방문하면 된다.
같은 예제에서 후위 순회는 어떻게 적용될까? 우선 왼쪽 서브트리를 방문한다. 그 다음 왼쪽 서브트리 내에서 방문을 진행하는데, 왼쪽 - 오른쪽 - 루트 순서이니 방문 순서는 3 - 4 - 1 이 된다.
최종적으로 후위 순회의 방문 순서는 다음과 같다.
