[자료구조] 전위 , 중위, 후위 순회란?

순회란, 여기 저기로 돌아다닌다는 뜻을 가지고 있습니다.

 

우리가 노드를 지나가는 것 역시 순회라고 합니다.

 

그리고 그 노드를 지나가는 순서에 따라 

 

전위 순회, 중위 순회, 후위 순회로 나뉘는 것입니다.

 

 

다음과 같이 단순한 트리가 하나 있다고 가정해봅시다.

 

 

 

모든 노드를 지나가는 횟수는 아래와 같이 총 6회이지만, 

 

(왼->루트->오 / 왼->오->루트 / 루트->왼->오/ 루트->오->왼 / 오->루트->왼 / 오->왼->루트)

 

왼쪽과 오른쪽이 고정되어있다고 치면, 

 

 

 

이렇게 3가지 경우로 나뉠 수 있고, 이게 각각 전위, 중위, 후위 순회입니다.

 

루트노드 -> 왼쪽 자식 -> 오른쪽 자식 순으로 노드를 읽는 것이 전위 순회,

 

왼쪽 자식 -> 루트노드 -> 오른쪽 자식 순으로 노드를 읽는 것이 중위 순회,

 

왼쪽 자식 -> 오른쪽 자식 -> 루트노드 순으로 노드를 읽는 것이 후위 순회입니다.

 

 

루트노드를 제일 먼저 읽는다면 루트노드가 맨 앞에 오기 때문에 전(前:앞 전) 위

루트노드가 왼쪽 노드와 오른쪽 노드의 중간에 있다면 중(中: 가운데 중) 위

루트노드를 왼쪽 노드, 오른쪽 노드보다 나중에 읽는다면 맨 뒤에 읽게 되는 것이므로 후(後: 뒤 후)위 순회가 되는 것입니다.

 

 

즉 루트노드의 위치에 따라 전위, 중위, 후위 순회로 나뉘는 것이죠.

 

 

이제 뭐가 뭐인지 헷갈릴 일은 없을 겁니다.

 

그럼 지금부터는 실제 트리를 가져와서 읽는 순서를 알려드리도록 하겠습니다.

 

 

이런 트리가 있을 때 전위 순회, 중위 순회, 후위 순회를 하게 되면 어떻게 될까요?

 

바로 알려드리겠습니다.

 

전위 순회는 루트노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 읽으면 된다고 했으므로

 

 

이렇게 됩니다. 

 

순서대로 살펴보겠습니다.

 

우선, 루트-> 왼 -> 오 순서로 가야하므로 트리의 루트노드인 g를 맨 처음 읽습니다.

 

그 다음은 루트노드 기준 왼쪽에 있는 노드를 읽어야 합니다. 위 그림에서는 e가 되겠네요

 

이제 다음으로 넘어갈 때, e는 e,a,b로 이루어진 서브 트리의 루트노드가 됩니다. 

 

따라서 e,a,b로 이루어진 서브트리를 기준으로 전위 순회 해주면 e -> a -> b가 됩니다. 

 

왼쪽에는 더 이상 노드가 존재하지 않네요.

 

그러면 g가 노드인 전체 트리 기준으로 루트 -> 왼  까지는 완료된 것입니다.

 

이제 마지막으로 오른쪽에 있는 것들만 정리를 해주면 됩니다. 

 

루트노드 g를 기준으로 오른쪽에는  f,c,d 서브트리가 존재합니다.

 

여기서도 루트 -> 왼 -> 오 의 순서대로 가주면 되므로, f-> c -> d 가 됩니다.

 

따라서 전위순회한 결과는 g -> e -> a -> b -> f -> c -> d 입니다.

 

 

중위 순회는 왼쪽 노드 -> 루트 노드 -> 오른쪽 노드 입니다.

 

어떻게 생각하면 가장 단순한 순회입니다.

 

트리의 가장 왼쪽에 있는 노드로 시작해서 가장 오른쪽에 있는 노드로 끝나거든요.

 

 

 

트리의 가장 왼쪽에 있는 a 로 시작해서 a가 있는 a,e,b 서브트리에서  왼 -> 루트 -> 오 순으로 순회합니다.

 

이제 전체 트리를 기준으로 왼쪽에 있는 노드는 순회를 마쳤으므로 루트노드 g로 가준 뒤, 

 

오른쪽 서브트리 역시 c -> f -> d 순으로 순회해주면 됩니다.

 

중위 순회 결과는 a -> e -> b -> g -> c -> f -> d 가 됩니다.

 

 

마지막으로 후위 순회입니다. 

 

후위 순회는 가장 왼쪽에 있는 노드에서 시작하고 루트노드로 끝납니다. 

 

 

 

 

가장 왼쪽에 있는 a로 시작하여, a,e,b 서브트리에서 왼 -> 오 -> 루트 순으로 순회해주면 a -> b -> e 이고

 

전체 트리를 기준으로 왼쪽에서의 순회가 끝났으므로 오른쪽 서브트리로 가서 오른쪽 서브트리 c,f,d 에서

 

후위순회 해주면 c -> d -> f 이고 루트로 끝내주면 후위 순회가 끝납니다.

 

전체 후위 순회 결과는 a -> b -> e -> c -> d ->f -> g 가 됩니다.

 

 

여기까지 잘 따라오셨나요?

 

직접 순회를 해야할 때는 꼭 서브트리를 고려해주어야 편합니다. 

 

아마 제가 예시를 든 트리보다 복잡한 트리를 순회해야 할 때가 있을 수도 있는데,

 

 

이런 경우에도 왼쪽 서브트리 , 오른쪽 서브트리 , 루트 노드 이렇게 잘 나눠서 해주시면 됩니다.

 

정답만 남겨놓을테니 직접 해보시고, 궁금한 점 있으면 댓글 달아주세요.

 

전위 순회 : g - e - a - 1 - b - f - c - d - 2 - 4 - 5 - 3

중위 순회 : a - 1 - e - b - g - c - f - 4 - 2 - 5 - d - 3

후위 순회 : 1 - a - b - e - c - 4 - 5 - 2 - 3 - d - f - g