이진 트리란

자료구조를 공부한지 꽤 지났다. 책을 다시 펴보니 선형 리스트(리스트, 스택, 큐)는 잘 이해하고 있는데 항상 비선형 리스트(트리, 그래프)는 뭔가 새롭다.

트리에 대해 공부해보자.

Q. 트리란?

- 계층적 관계를 표현하는 자료구조이다.

Q. 이진 트리란?

- 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

- 나뉘어진 두 서브 트리 모두 이진 트리여야 한다.

위 그림은 이진 트리를 보여주는데, 트리에서 사용되는 용어들을 살펴보자

1. 노드 : 트리의 구성요소에 해당하는 A~E까지의 각 요소

2. 간선 : 노드와 노드를 연결하는 연결선

3. 루트 노드 : 트리 구조 최상단에 있는 A 노드

4. 단말노드 : 아래에 다른 노드가 없는 H, E, F, G 노드
5. 차수 : 한 노드에 연결된 서브 노드의 개수, 이진 트리의 차수는 2 이하.

6. 레벨 : 트리에서 각 층별로 숫자를 매김, A는 0레벨, B,C는 1레벨

7. 높이 : 트리의 최고 레벨을 의미한다. H는 레벨3에 속하므로 위 트리의 높이는 3이다.

8. 포화 이진 트리 : 트리의 모든 레벨이 꽉 차 있는 트리 (아래 그림 참조)

9. 완전 이진트리 : 포화 이진 트리는 아니지만 빈틈 없이 노드가 채워진 이진트리 (아래 그림참조)

트리에 저장된 모든 데이터를 출력해야 한다고 가정하자. 우선, 트리의 모든 노드를 방문해야 하는데, 이를 순회라고 한다.

트리를 순회하는 방법에는 아래와 같이 4가지가 있다.

전위 순회 : 루트노드를 먼저 방문한다.

중위 순회 : 루트노드를 중간에 방문한다.

후위 순회 : 루트노드를 마지막에 방문한다.
단계 순회 : 루트노드부터 왼쪽 노드와 오른쪽 노드를 차례대로 방문한다.

핵심은 루트 노드의 방문 순서이다. 글보다는 그림이 이해가 편하다.

전위 순회 방법 ( A-> B-> C)
- 루트노트를 먼저 방문하고 왼쪽부터 오른쪽 순으로 순회한다.

중위 순회 방법 (B-> A-> C)
- 왼쪽 노드를 먼저 방문 후, 루트노드를 방문한뒤 오른쪽으로 순회한다.

후위 순회 방법 (B-> C-> A)
- 왼쪽부터 오른쪽으로, 루트노드를 가장 마지막에 방문한다.

단계 순회 방법 (A-> B-> C)

- 루트노드부터 왼쪽과 오른쪽으로 단계적으로 순회하는 방법

전위 순회와 단계 순회의 결과가 같아보이지만, 트리의 레벨을 한 단계 높인 순회 예시를 들면 이해할 것이라 믿는다.

전위 순회 방법 : A-> B-> D-> E-> C-> F-> G

단계 순회 방법 : A-> B-> C-> D-> E-> F-> G