트리 알고리즘 (3 - 트리의 순회방법 (개념편))

 

 

○이어지는 글

 

https://kuck-su-labor.tistory.com/52

 

 

○들어가는 글

 

원래 이어지는 글이라면 이번시간에는 greedy알고리즘을 설명하는 시간 이였습니다. 하지만 그 전에 지금이 아니면 순회방법의 대해서 다룰 타이밍이 따로 없을 것 같아서 잠시 순회의 대해서 먼저 설명하려고합니다.

저번 글에서는 트리의 마지막 부분에서 값을 얻음으로써 값을 얻는 완전탐색의 대해서 알아보았습니다. 하지만 우리는 각 노드의 값을 구해야 하는 경우도 있습니다. 이러한 경우에는 단순히 각 노드를 담당하는 함수 자체에서 값을 얻는 (출력문을 넣는다거나) 것으로 해결 할 수 있을 것입니다. 하지만 우리가 더 알아야 하는 것은 노드를 참조할 때 순서가 있는 경우입니다.

 

○트리의 순회

트리는 크게 ‘전위 순회’ , ‘중위 순회’ , ‘후위 순회’로 나누어집니다. 한번 각각이 어떠한 차이점이 있는지 알아봅시다.

 

>전위순회 [root -> Left -> right]

전위순회는 root를 먼저 참조하고, 그 다음에 왼쪽 자식, 오른쪽 자식을 순회하는 순회법입니다.

>전위순회 [Left -> Root -> Right]

중위 순회는 왼쪽 자식 노드부터 시작해서 root로, 그리고 마지막 남은 오른쪽 자식노드로 순회합니다.

>후위순회 [Left -> Right -> Root]

후위 순회는 아예 자식노드를 먼저 순회하고 Root를 마지막으로 순회하는 방법입니다.

 

 

○트리의 순회 고려사항

이렇게 본다면 쉬워보이지만, 우리가 알아야 하는 것은 트리는 재귀 구조이기 때문에 순회 과정에서 root가 아닌 자식 노드라도, 자식이 있다면 재귀되어 root 노릇을 한다는 점입니다.

위 그림을 보면 첫 root에서 나온 왼쪽 자식노드는 또 다시 root 노드가 되어 전위순회를 시작합니다. 이렇게 자식노드가 없을 때 까지 이러한 절차를 반복하지요. 결과적으로 말하자면 트리는 재귀적이기 때문에 이러한 순회방법을 우리는 재귀적으로 접근할 필요가 있습니다.

 

○간단한 실습

우선 간단하게 순회방법을 연습해 봅시다. 다음과 같은 트리가 있을 때 각 순회를 고려한다면 다음과 같은 순서 방법이 나올 것입니다.

 

 

 

 

>전위순회

 

>중위순회

 

>후위순회

 

○ 더 나아가서

사실 이 글은 실제 순회방법을 비교하면서 구현할 예정 이였기에 분량이 더 길었어야 했습니다. 하지만 이 포스트의 콘셉트인 (5+1)은 무리되지 않게 간단히 쓸 수 있는 그림의 분량(5+1)장 정도로 쓰는 것을 목표로 하고 있기 때문에 글을 2개로 나누어 이번 글에서는 순회의 개념만을 다루려고 합니다.

다음에는 이러한 순회방법을 구현하는 방법과 비교하는 글을 쓸 생각입니다. 빨리 이것을 끝내고 greedy 알고리즘으로 넘어가도록 하겠습니다. 읽어주셔서 감사합니다.