본문 바로가기
정보처리기사 필기/[2과목] 소프트웨어 개발

[정보처리기사] 자료구조 트리, 이진트리 순회 (preorder, inorder, postorder)

by Devinus 2021. 3. 3.

1. 자료구조 트리(Tree)

- 트리는 정점(Node, 노드)선분(Branch, 가지)을 이용해 사이클(순환)을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태이다.

- 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 한다.

 

2. 트리 관련 용어

이진 탐색 트리 - By Miles - 자작, 퍼블릭 도메인, https://commons.wikimedia.org/w/index.php?curid=1535668

  • 노드(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)

  1. 노드 방문
  2. 왼쪽 서브 트리를 전위 순회
  3. 오른쪽 서브 트리를 전위 순회

3.2. 중위 순회(Inorder) = 대칭 순회(Symmetric)

  1. 왼쪽 서브 트리를 중위 순회
  2. 노드 방문
  3. 오른쪽 서브 트리를 중위 순회

3.3. 후위 순회(Postorder)

  1. 왼쪽 서브 트리를 후위 순회
  2. 오른쪽 서브 트리를 후위 순회
  3. 노드 방문

3.4. 레벨 순서 순회(Levelorder) = 너비 우선 순회(BFT; Breadth First Traversal)

  1. 모든 노드를 낮은 레벨부터 순회(같은 레벨의 경우 왼쪽 노드 먼저)

이진 탐색 트리 - By Miles - 자작, 퍼블릭 도메인, https://commons.wikimedia.org/w/index.php?curid=1535668

위 그림의 이진 탐색 트리에서 각 순회는 아래와 같은 순서로 순회된다.

  • 전위 순회: 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