---

트리(Tree)

---

1. 트리

• Node와 Edge로 이루어진 자료구조

• 값을 가진 Node와 간선(Edge)로 이루어져 있다.

• 1은 루트(Root)노드이다.

• 모든 노드들은 0개 이상의 자식(Child)노드를 갖고 있으며 보통 부모-자식 관계로 부른다.

• 트리에는 사이클이 존재할 수 없다.(사이클이 존재 : 그래프)

• 모든 노드는 자료형으로 표현이 가능하다.

• 루트에서 한 노드로 가는 경로는 유일하다.

• 노드의 개수가 N개이면 간선은 N-1개를 가진다.

2. 트리 순회 방식

1. 전위 순회(pre-order)

• 각 루트(Root)를 순차적으로 먼저 방문하는 방식이다.
• Root -> 왼쪽 -> 오른쪽

2. 중위 순회(in-order)

• 왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식이다.
• 왼쪽 -> Root -> 오른쪽

3. 후위 순회(post-order)

• 왼쪽 하위 트리부터 모두 방문 후 루트(Root)를 방문하는 방식이다.
• 왼쪽 -> 오른쪽 -> Root

4. 레벨 순회(level-order)

• 루트(Root)부터 계층 별로 방문하는 방식이다.
• 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14