1. 자료구조 트리(Tree)
- 트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용해 사이클(순환)을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태이다.
- 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 한다.
2. 트리 관련 용어
- 노드(Node): 트리의 기본 요소, 데이터와 다른 데이터에 대한 가지(Branch)를 합친 것
- ex) A, B, C, D, E, F, G, H, I
- 근 노드(Root Node): 트리의 맨 위에 있는 노드, 트리 - 나무, 나무의 뿌리(Root)에서 처음 시작하는 부분의 노드
- ex) F
- 디그리(Degree, 차수): 각 노드에서 뻗어나온 가지(Branch)의 수, 트리의 디그리는 노드들 중 가장 많은 디그리를 말한다.
- ex) F = 2, B = 2, G = 1, D = 2, 트리의 디그리 = 2
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 디그리(차수)가 0인 노드
- ex) A, C, E, H
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- ex) F의 자식노드 = B, G
- 부모노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- ex) D의 부모노드 = B, H의 부모노드 = I
- 형제노드(Brother Node, Sibling Node), 동일한 부모를 갖는 노드들
- ex) A의 형제노드 = D
- 레벨(Level) = 깊이(Depth): 근 노드부터 level 1로 시작해 층 별로 level이 1씩 증가한다.
- ex) F의 레벨 = 1, B의 레벨 = 2, D의 레벨 = 3, C의 레벨 = 4
3. 트리 순회 방법 - 전위, 중위, 후위, 레벨 순서 순회
- 트리를 순회하는 방법은 각 시작 노드와 중간에 탐색할 노드, 마지막으로 탐색할 노드의 순서를 다르게 하여 순회하는 여러가지의 방법이 존재한다. 이런 트리 순회 과정은 재귀로 설명할 수 있다.
3.1. 전위 순회(Preorder) = 깊이 우선 순회(DFT; Depth First Traversal)
- 노드 방문
- 왼쪽 서브 트리를 전위 순회
- 오른쪽 서브 트리를 전위 순회
3.2. 중위 순회(Inorder) = 대칭 순회(Symmetric)
- 왼쪽 서브 트리를 중위 순회
- 노드 방문
- 오른쪽 서브 트리를 중위 순회
3.3. 후위 순회(Postorder)
- 왼쪽 서브 트리를 후위 순회
- 오른쪽 서브 트리를 후위 순회
- 노드 방문
3.4. 레벨 순서 순회(Levelorder) = 너비 우선 순회(BFT; Breadth First Traversal)
- 모든 노드를 낮은 레벨부터 순회(같은 레벨의 경우 왼쪽 노드 먼저)
위 그림의 이진 탐색 트리에서 각 순회는 아래와 같은 순서로 순회된다.
- 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
- 중위 순회: A, B, C, D, E, F, G ,H, I (left, root, right)
- 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)
- 레벨 순서 순회: F, B, G, A, D, I, C, E, H
정보처리기사 필기 기출문제
| 22. 다음 트리의 차수(degree)와 단말 노드(terminal node)의 수는? ② [정답률: 72%] 정보처리기사(2020년 이후) 필기 (2020년 1회·2회 통합 기출문제) |
|
 |
|
| ① 차수:4, 단말 노드: 4 | |
| ② 차수:2, 단말 노드: 4 | 차수는 2, 단말노드는 D, G, H, F 총 4 |
| ③ 차수:4, 단말 노드: 8 | |
| ④ 차수:2, 단말 노드: 8 | |
| 34. 다음 트리를 전위 순회(preorder traversal)한 결과는? ④ [정답률: 76%] 정보처리기사(2020년 이후) 필기 (2020년 1회·2회 통합 기출문제) |
|
 |
|
| ① ＋ * A B / * C D E | |
| ② A B / C * D * E ＋ | 후위 순회(postorder) - left, right, root 순서로 순회 |
| ③ A / B * C * D ＋ E | 중위 순회(inorder) - left, root, right 순서로 순회 |
| ④ ＋ * * / A B C D E | 전위 순회(preorder) - root, left, right 순서로 순회 |
| 29. 다음 트리를 Preorder 운행법으로 운행할 경우 가장 먼저 탐색되는 것은? ① [정답률: 81%] 정보처리기사(2020년 이후) 필기 (2020년 3회 기출문제) |
|
 |
|
| ① A | 중위순회(preorder) - root, left, right - 즉 A가 가장먼저 탐색 |
| ② B | |
| ③ D | |
| ④ G | |
| 40. 다음 트리의 차수(degree)는? ② [정답률: 73%] 정보처리기사(2020년 이후) 필기 (2020년 3회 기출문제) |
|
 |
|
| ① 2 | |
| ② 3 | 차수는 노드들 중에 가장 큰 값 B의 차수 = 3 |
| ③ 4 | |
| ④ 5 | |
| 32. 다음 트리에 대한 INORDER 운행 결과는? ① [정답률: 68%] 정보처리기사(2020년 이후) 필기 (2020년 4회 기출문제) |
|
 |
|
| ① D B A E C F | 중위 순회(Inorder) - left, root, right |
| ② A B D C E F | 전위 순회(Preorder) - root, left, right |
| ③ D B E C F A | |
| ④ A B C D E F | |
