자료구조 - 이진 트리 순회

이진트리 순회란?

이진트리 순회를 알려면 일단 트리를 알아야 한다.

다행스럽게도(?) 이전에 트리에 대해서 간략하게 설명한 부분을 참고하면 좋을 것 같다.

 

https://beetr.tistory.com/97

자료구조 - 비선형구조 : 트리, 그래프

 

추가적으로 이진 트리는 트리구조를 따라가는데, 자식 노드가 0 ~ 2개 사이인 트리를 의미한다.

 

이진 트리에는 다음과 같은 종류가 있다.

• 편향트리 : 좌 또는 우 한쪽 서브트리만 가지는 트리.
• 포화이진트리 : 모든 레벨에서 노드들이 모두 채워진 트리.
• 완전 이진트리 : 마지막 레벨을 제외하고 ( 다 채워져 있어도 됨) 모든 노드가 채워진 트리

그렇다면 왜 이진 트리를 사용할까??

이진트리는 선형 구조와 달리 검색, 삽입에서 연산 횟수를 대폭 줄일 수 있다.

 

선형구조(배열, Linked List, 스택, 큐, 덱(데크))는 일자로 되어있기 때문에 하나의 데이터 뒤에는 또 하나의 데이터가 있다.

때문에, 선형구조에서는 정렬이 되어있지 않을 때 최악 시간 복잡도는 O(n)이 된다.

 

하지만, 이진 트리는 탐색하는데 드는 최적의 시간복잡도는 O(log n)이 된다.

이진트리 예시

위 그림을 예로 들어서 대답해 보자. 위는 9개의 데이터가 있다.

"9"를 찾기 위해서 몇 번을 검색해야 할까? 

1. 우선 11보다 작기 때문에 왼쪽으로 간다.
2. 그 다음 5보다 크기 때문에 오른쪽으로 간다.
3. 9보다 크기 때문에 오른쪽으로 간다.
4. 10이다! 

•  트리의 레벨이 3이라면 (데이터의 갯수가 2의 3승 - 1) 세번,
• 트리의 레벨이 4라면(데이터의 갯수가 2의 4승 - 1) 네번만 가면 찾을 수 있다.

쭉쭉 가서 데이터가 2의 n승 -1개라면 n 번을 가면 찾을 수 있기 때문에 시간 복잡도는 log n 번이다.

 

이진 트리 순회

다시 돌아와서, 이진 트리의 순회에 대해서 알아보자.

개념

이진트리 순회는 자료를 검색하거나, 정렬하는 알고리즘에서 사용된다.

종류

1) 중위 순회 (In-Order)

좌측 노드 → 중간 노드 → 우측 노드 순으로 순회한다.

2) 전위 순회 (Pre-Order)

루트(근) 노드 → 좌측 노드 → 우측 노드 순으로 순회한다.

3) 후위 순회 (Post-Order)

좌측 노드 → 우측 노드 → 루트(근) 노드 순으로 순회한다.