[자료구조] 이진 트리의 순회

트리를 통해 자료를 계층적인 구조로 저장하고 사용하기 위해서는 트리에 있는
모든 노드를 방문하는 방법이 필요하다. 이진 트리에있는 모든 노드를 한번씩

모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것을 순회 라고 한다. 리

스트나 스택, 큐와 같은 선형 자료구조는 순회하는 방법이 한 가지 였지만, 트

리는 계층구조를 가지고 있기 때문에 여러가지 순회 방법이 있을 수 있다. 현재
노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눌 수 있다.
1. 전위 순회

(1) 현재 노드 n을 방문한다. ( 그 위치의 자료를 가져오거나 확인한다. )

(2) 현재 노드 n의 왼쪽 서브 트리로 이동한다.

(3) 현재 노드 n의 오른쪽 서브 트리로 이동한다.

이렇게 만 놓고 보면 왼쪽으로 갔다가 다시 바로 오른쪽으로 갈 것 같지만, 실

제 구현된 기능은 왼쪽으로 쭉 타고 내려간다. 그리고 더이상 왼쪽으로 갈 수

없다면 오른쪽, 오른쪽이 없다면 다시 부모 노드로, 그리고 다시 오른쪽을 확인
혹시 오른쪽에 노드가 있다면 거기로 갔다가 다시 왼쪽을 확인.. 이런식의 반복

이다..

코드로 구현하자면, 재귀호출을 이용하여 구현하면 간단하다.

2. 중위 순회

(1) 현재 노드 n의 왼쪽 서브 트리로 이동한다.

(2) 현재 노드 n을 방문한다.

(3) 현재 노드 n의 오른쪽 서브 트리로 이동한다.

중위 순회는 현재 노드를 방문하는 작업을 L과 R 노드 작업 중간에 수행하는 것

이다. 이 것은 일단 왼쪽 노드를 쭉 찾아내려간다.. 그리고 최종적인 왼쪽 노드

로 가면, 값을 읽고, 부모 노드로 돌아와서 값을 읽는다. 그 후에 다시 오른쪽노

드로 가서.. 또 왼쪽 노드부터 값을 읽는다.. 이 것의 반복인 것이다.

3. 후위 순회

(1) 현재 노드 n의 왼쪽 서브 트리로 이동한다.

(2) 현재 노드 n의 오른쪽 서브 트리로 이동한다.

(3) 현재 노드 n을 방문한다.

후위 순회도 일단 위의 순회들과 마찬가지로 왼쪽으로 쭉 노드를 찾아내려간

다. 그 후에 다시 부모로 돌아왔다가 오른쪽 노드를 확인을 하고, 그 오른쪽에

값이 있다면 또 왼쪽으로 가다가 최종적으로 돌아와서 자기의 값을 확인하고

또 돌아가고를 반복한다.

이렇게 글로만 보면 헷갈릴 수 있는데, 실제로 이진 트리를 하나 그려놓고, 전

위, 중위, 후위의 순서로 데이터를 읽어보고 방법이 맞는지 다시 검토해 보면

쉽게 이해가 될 것이라 생각된다.