[자료구조 ] Tree(트리) 필수 개념, 트리 순회

트리란?

트리는 Node 로 이루어진 자료구조 이다.

하지만 Node로 이루어져있다고 다 트리라고 부를 수 있을까?

아니다. 트리는 그래프와 구별되며 다음과 같은 특징을 가지고 있다.

1. 트리는 최소 연결 트리라고 불린다. 두 Node 사이에 반드시 1가지의 경로만을 가진다. (ex, A에서 F로 가는 경로는 한가지이다.)
2. 트리는 오직 한개의 Root Node를 가진다.
3. 트리에는 loop, circuit, self-loop가 존재하지 않는다. (사이클이 없는 방향 그래프(DAG))
4. 트리의 순회는 Pre-Order, Inorder, Post-order로 이루어진다.
5. Edge는 항상 Node의 개수 - 1 의 개수이다.

 

---

 

이진트리(Binary Tree)에 대해서

우리가 보통 BT 라고 부르는 Binary Tree(이진 트리)는 모든 Internal Node들이 2개 이하의 자식 (0 ~ 2개의 자식)을 가지는 트리를 이야기 한다.

완전 이진 트리 (Complete Binary Tree)란?

가장 마지막 Level을 제외한 모든 Node들이 2개의 자식을 가지는 BT

위 BT가 CBT가 되기 위해서는 G라는 노드가 F의 Siblings로 들어와야 한다.

 

 

---

 

이진 트리 순회 (Tree Traverse)

트리 순회는 예시의 순서를 눈으로 따라가면서 이해하는 것이 가장 빠르다.

트리를 순회할 때, 중요한 것은 node의 Level과 노드가 parent의 left에 위치해 있는지 right에 위치해 있는지이다.

 

 

1. 전위 순회 (Pre-Order Traversal)

: Root Node부터 시작

Parent Node → Left Child Node → Right Child Node

0 -> 1 -> 3 -> 7 -> 8 -> 4 -> 2 -> 5 -> 9 -> 10 -> 6

 

2. 중위 순회 (In-Order Traversal)

: 맨 왼쪽 Leaf Node 부터 시작

Left Child Node → Parent Node → Right Child Node

7 -> 3 -> 8 -> 1 -> 4 -> 0 -> 10 -> 9 -> 5 -> 2 -> 6

 

3. 후위 순회 (Post-Order Traversal)

: 맨 왼쪽 Leaf Node 부터 시작

Left Child Node → Right Child Node → Parent Node

7 -> 8 -> 3 -> 4 -> 1 -> 10 -> 9 -> 5 -> 6 -> 2 -> 0

 

4. 층별 순회 (Level-Order Traversal)

: Root Node 부터 시작

Hight → Low, Left → Right

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10