트리의 순회 - 전위 순회, 중위 순회, 후위 순회

1. 트리의 순회 (Tree traversal)

트리 순회란 트리의 모든 노드를 방문하는 것을 말합니다.

방문 순서에 따라 다음 3가지 방법이 있습니다.

처음에는 헷갈리지만 몇 번만 연습해보면 매우 간단하다는 것을 깨닫게 되실 겁니다.

 

2. 전위 순회(preorder) - VLR

전위 순회는 먼저 자기 자신을 방문한 뒤, 왼쪽 자식-오른쪽 자식 순으로 방문합니다. 만약 자식에게 또 자식이 있다면 자식 노드를 방문하기 전에 자식의 왼쪽 자식 노드를 방문합니다. 즉, 자기 자신을 방문한 다음(V) 왼쪽 자식으로 이동하여 자식이 있는 지 확인하고, 있다면 자식이 없는 리프 노드(leaf node)를 만날 때까지 계속 왼쪽으로 이동합니다. 왼쪽 서브트리에 대한 방문을 모두 마친 뒤에야 (L), 오른쪽 자식에 대해서 똑같이 방문을 시작합니다(R).

코드를 보면 이해가 쉽습니다. 

public void VLR(TreeNode root) {
    System.out.print(root.getData() + " "); // V
    if(root.getLeftChild() != null) VLR(root.getLeftChild()); // L
    if(root.getRightChild() != null) VLR(root.getRightChild()); // R
}

먼저 자기 자신을 출력한 다음 재귀적으로 왼쪽 자식과 오른쪽 자식에 대해서 순회를 시작합니다.

 

3. 중위 순회(inorder) - LVR

중위 순회는 먼저 왼쪽 자식을 방문한 다음 자기 자신 그리고 오른쪽 자식을 방문합니다.

public void LVR(TreeNode root) {
    if(root.getLeftChild() != null) LVR(root.getLeftChild());
    System.out.print(root.getData() + " ");
    if(root.getRightChild() != null) LVR(root.getRightChild());
}

구현 방법은 전위 순회와 크게 다르지 않습니다. L R V의 순서만 바꿔주면 됩니다.

 

4. 후위 순회(postorder) - LRV

후위 순회는 왼쪽, 오른쪽 자식을 모두 방문한 뒤에 자기 자신을 방문합니다.

public void LRV(TreeNode root) {
    if(root.getLeftChild() != null) LRV(root.getLeftChild());
    if(root.getRightChild() != null) LRV(root.getRightChild());
    System.out.print(root.getData() + " ");
}

 

5. 예제

 

1) 전위 순회 : 1 2 4 5 3 6

2) 중위 순회 : 4 2 5 1 6 3

3) 후위 순회 : 4 5 2 6 3 1