트리

트리는 무방향이면서 사이클이 없는 그래프이다.

트리는 아래와 같은 특징을 가지고 있다

• N개의 정점과 N-1개의 간선을 가진다
• 두 개의 정점을 연결하는 simple path(재방문 하지 않는 경로)가 하나뿐이다
• 임의의 간선을 추가하면 사이클이 생긴다
• 임의의 간선을 제거하면 연결 그래프가 아니게 된다

이진 트리

이진트리는 정점의 자식이 최대 2개인 트리이다.

이진 트리의 순회 방식

레벨 순회 (Level-order Traversal)

트리의 높이 순서대로 방문하는 방식

전위 순회 (Preorder Traversal)

1. 현재 정점을 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

루트 -> 왼쪽 -> 오른쪽

위의 트리를 전위 순회하면 방문 순서는 아래와 같다.
1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 11 -> 3 -> 6 -> 13 -> 7 -> 14

중위 순회 (Inorder Traversal)

1. 왼쪽 서브 트리를 중위 순회한다.
2. 현재 정점을 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

왼쪽 -> 루트 -> 오른쪽

위의 트리를 중위 순회하면 방문 순서는 아래와 같다.
8 -> 4 -> 9 -> 2 -> 10 -> 5 -> 11 -> 1 -> 6 -> 13 -> 3 -> 14 -> 7

후위 순회

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 현재 정점을 방문한다.

왼쪽 -> 오른쪽 -> 루트

위의 트리를 후위 순회하면 방문 순서는 아래와 같다.
8 -> 9 -> 4 -> 10 -> 11 -> 5 -> 2 -> 13 -> 6 -> 14 -> 7 -> 3 -> 1