[자료구조] 이진 트리의 순회(Traversal) (1)

[자료구조] 이진 트리의 순회 (Traversal) (1)

앞서 이진 트리를 만드는 도구에 대해 알아보고,

간단하게 이진 트리를 만들어보기까지 했다.

그렇다면 만들어진 이진 트리의 정보를

가져오기 위해 어떠한 방법을 써야할까?

이진 트리의 순회를 이용하여 트리의

루트부터 단말노드까지 모든 데이터를

순회하며 정보를 가져올 수 있다.

이진 트리의 순회를 하기 위해서는 재귀의 개념이 필요하다.

들어가기에 앞서 순회의 세가지 방법에 대해 알아보도록 하자.

위 그림 처럼 노드가 세개밖에 없는 경우는 매우 간단하다.

하지만 트리의 깊이가 깊은 경우에는 상당히 복잡할 수도 있다.

만약 중위순회 방법으로 순회를 구현했다면

트리의 깊이가 얼마가 되었든간에 순차적으로

중위 순회를 하며 모든 데이터를 가져올 수 있어야 한다.

ex) 중위 순회의 구현

여기서 재귀의 개념이 사용되는데,

처음 루트노드의 주소값이 전달이되고

함수가 시작이 되면

1. 종료 조건을 체크한다.

현재의 노드가 아무런 데이터를 가지고 있지 않으면 리턴하여 함수를 종료한다.

2. 데이터를 가진 노드라면 (공집합 노드가 아니라면)

자신의 왼쪽 트리를 함수의 인자로 전달하여 순회 함수를 또 한번 호출한다. (재귀의 개념)

3. 자신의 왼쪽 트리의 순회가 끝나고 (2에서 실행했던 함수가 끝나면)

자신이 가진 데이터를 출력한다.

3. 데이터를 출력한 후 (중위 순회이기 때문에 왼쪽에서 오른쪽)

자신의 오른쪽 트리를 함수의 인자로 전달하여 순회 함수를 또 한번 호출한다. (재귀의 개념)

4. 함수 종료

ex) 중위 순회

이진 트리의 중위 순회 결과

위의 중위 순회 동작 순서

오늘은 이진 트리의 순회에 대해 알아보았다.

재귀의 개념이 들어가다 보니까 살짝 어렵게 느껴지기도 한다.

다음에는 함수포인터를 이용하여 이진 트리의 순회를

좀 더 세련되게 표현해보도록 하겠다.