2022년 중등부 KOI(한국정보올림피아드) 1차 1교시

1번 문제

문제풀이

  전위 순회로 나타낼 수 있는 결과가 3,1,2,4일 경우 나열할 수 있는 이진트리는 아래와 같다. 

 

필요 숙지 개념

 

1. 트리(Tree) 개념 이해

https://mymajoriscs.tistory.com/1

자료구조 트리(Tree) 이해하기

이전 자료구조 트리 개념을 설명해놓은 자료를 보면 이해가 쉽다.

트리는 싸이클이 존재하지 않는 방향 그래프(DAG, Directed Acyclic Graph)라고 할수 있다.

문제에선 이진트리를 다루고 있지만, 트리의 종류는 아래와 같이 다양하다.

• 편향 트리(Skew tree)
• 이진 트리(Binary Tree)
• 이진 탐색 트리(Binary Search Tree, BST)
• m원 탐색 트리(m-way search tree)
• 균형 트리(Balanced Tree, B-Tree)
• 레드-블랙 트리(Red-Black Tree, RB tree)

위 해설그림 제일왼쪽의 형태가 모든 노드들이 자식을 1개만 갖고 있는 편향 트리(skew tree)이다.

각 노드의 자식노드가 0~2개인 트리를 이진트리라고 정의한다.

 

2. 이진트리 전위순회(Binary Tree Preorder Traversal)

https://mymajoriscs.tistory.com/2

이진트리 전위순회(preorder traversal) 이해하기

전위순회는 "현재 노드 → 왼쪽 → 오른쪽" 순으로 방문하면서 순회하는 것을 나타낸다.

아래 절차와 같이 Subtree관점에서 현재노드 방문→왼쪽 Subtree → 오른쪽 Subtree 순서로 이해해서 분할해서 처리하다보면 위와 같이 A-B-D-H-E-I-J-C-F-G-K 경로를 얻게 된다.