[2021 정보처리기사 필기] 바이너리 트리(Tree)의 운행법

목차

 

 

 

 

[정보처리기사 2과목 필기 예상 키워드] 목록으로 돌아가기
과목: 2. 소프트웨어 개발 챕터: 1장 데이터 입출력 구현 키워드: 바이너리 트리(Tree)의 운행법(Traversal)	#트리의 개요 #Preorder, Inorder, Postorder 운행법

 

 

트리의 개요

트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태이다.
하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 한다.

 

근 노드(Root Node): 트리의 맨 위에 있는 노드, A
자식노드(Son Node, Child Node): 어떤 노드에 연결된 하위 레벨의 노드들, A 이하 모두
부모노드(Parent Node): 어떤 노드에 연결된 상위 레벨의 노드들, EFGHI 이상 모두
형제노드(Sibling Node): 동일한 부모를 갖는 노드들, BCD, EF와 HI

차수(Degree): 각 노드에서 뻗어나온 가지의 수, A=3, B=2...
트리의 차수(Degree): 노드들의 디그리 중에서 가장 많은 수를 의미한다.

 

 

 

 

 

 

 

 

 

*트리의 운행법(Traversal)*

트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
처음 접하는 개념이라면 다소 어렵게 느껴질 수 있지만, 이해하고 나면 문제를 보면서 손쉽게 운행순서를 찾을 수 있다.

이진 트리(Binary Tree)를 운행하는 방법은 산술식의 표기법과 연관성을 가지며
운행법은 Preorder 운행, Inorder 운행, Postorder 운행의 세 가지가 있다.

쉽게 기억하려면 Root의 위치가 어디에 있느냐에 따라 Pre, In, Post로 나누어 생각하면 된다.

 

 

 

 

 

예제를 통해 개념 익히기

위와 같은 예제를 통해 하나의 트리를 각각 Preorder, Inorder, Postorer 방법으로 운행해보며 쉽게 숙지할 수 있다.

나는 시나공에 나와있는 다이어그램 형식의 운행법이 잘 이해가 되지않아
그냥 운행방법에 따른 순서에 맞게 눈으로 그려보는 방식으로 미로찾기를 하듯이 숙지했다. (이게 훨씬 쉬움)

그림을 모니터에 띄워놓고, 손가락을 짚으며 아래의 순서대로 따라가다보면 매우 쉽게 이해된다.
운행 방법에 따라 Root의 위치가 바뀌고, 이후로는 L > R 의 순서로 운행된다는 점을 기억하면 된다. 

 

 

예제1. Preorder 운행법 : 노드 방문순서 구하기

위 사진은 포스팅하는 김에 노가다로 한 개 만들어 본 애니매이션... 이거 하나로 나머지 운행법도 모두 정복가능!ㅠㅠ
부디 이 움짤로 도움받는 분이 계시기를...

 

예제1. Preorder ( Root > L > R ) 운행법으로 각 노드를 방문한 순서를 구할 것

1) A에서 출발한다. Root > L > R 순서에 따라, A는 곧 Root 노드이므로 첫 번째 방문순서는 A
2) 다음은 Root > L > R 의 순서에 따라 B로 간다. B에서 다시 Root>L>R, B=Root 노드이므로 두 번째 방문순서는 B
3) 다음은 Root > L > R의 순서에 따라 D로 간다. D에서 다시 Root>L>R, D=Root 노드이므로 세 번째 방문순서는 D
4) 다음도 마찬가지로 Root > L > R의 순서에 따라 H로 간다. H는 하위노드가 없으므로 네 번째 방문순서는 H
5) 다시 D로 돌아온다. Root>L>R의 순서에 따라 D(Root)와 H(L)는 이미 방문했으므로 R로 이동, 즉 다섯번째 방문순서는 I
6) 다시 D로 돌아온다. 그런데 이미 D는 이미 방문했으므로 B로, B 역시 방문했으므로 R로 이동, 여섯번째순서는 E
7) 이미 방문한 B, A를 거치면 L을 모두 운행했으므로 Root > L > R의 순서에 의거해 C로 간다
8) C에서 다시 Root>L>R, C=Root 노드이므로 일곱번째 방문순서는 C
9) 다음은 Root > L > R의 순서에 따라 F로 간다. F는 하위노드가 없으므로 여덟번째 방문순서는 F
10) 다시 C로 돌아온다. Root>L>R의 순서에 따라 C(Root)와 F(L)는 이미 방문했으므로 R로 이동, 즉 아홉번째 방문순서는 G



= 따라서 Preorder 운행법에 따른 방문 순서는 ABDHIECFG 이다.

 

 

 

 

예제2. Inorder  운행법 : 노드 방문순서 구하기

예제2. Inorder ( L > Root > R ) 운행법으로 각 노드를 방문한 순서를 구할 것

1) A에서 출발해서 L > Root > R 순서에 따라,  하위의 Left 노드가 없을때까지 진행하여 첫번째 방문 순서는 H
2) 다음은 L > Root > R 순서에 따라 Root로 이동, 두번째 방문 순서는 D
3) 다음은 L > Root > R 순서에 따라 R로 이동, 세번째 방문 순서는 I
4) 이미 방문한 D를 거쳐 B로 이동, Root > R 순서에 따라 R로 이동, 네번째 방문순서는 B
5) 다음은 Root>R 순서에 따라 다섯번째 방문순서는 E
6) 이미 방문한 B를 거쳐 A로 이동, Root > R 순서에 따라 여섯번째 방문순서는 A
7) 다음은 L > Root > R 순서에 따라 C로 이동 후 좌측 하위 노드가 있으므로 F로 이동, 일곱번째 방문순서는 F
8) F는 더이상 하위 노드가 없으므로 Root로 이동, Root> R 순서에 따라 여덟번째 방문순서는 C
9) 다음은 Root>R 순서에 따라 아홉번째 방문순서는 G



= 따라서 Inorder 운행법에 따른 방문 순서는 HDIBEAFCG 이다.

 

 

 

 

예제3. Postorder 운행법: 노드 방문 순서 구하기

예제2. Postorder (L > R > Root) 운행법으로 각 노드를 방문한 순서를 구할 것


1) A에서 출발해서 L > R > Root 순서에 따라, 하위의 Left 노드가 없을때까지 진행하여 첫번째 방문 순서는 H
2) H는 더이상 하위 노드가 없으므로 다시 D(Root)로 돌아온 뒤 L > R 의 순서에 따라 R로 이동, 두 번째 방문 순서는 I
3) 다음은 L > R > Root 순서에 따라 세 번째 방문 순서는 D
4) B로 이동 후 R > Root 순서에 따라 네 번째 방문 순서는 E
5) 다음은 R > Root의 순서에 따라 다섯번째 방문 순서는 B
6) 다시 A로 돌아와 L > R > Root 순서에 따라 C를 거쳐 F로 이동, 여섯번째 방문 순서는 F
7) 다음은 L > R > Root 순서에 따라 일곱번째 방문 순서는 G
8) 다음은 R > Root의 순서에 따라 여덟번째 방문 순서는 C
9) 마지막으로 아홉번째 방문 순서는 A




= 따라서 Postorder 운행법에 따른 방문 순서는 HIDEBFGCA 이다.

 

 

 

 

 

 

 

[2021 정보처리기사 키워드 정리] 2. 소프트웨어 개발 (상시업데이트)

참고: 시나공 정보처리기사 필기 (저자: 강윤석, 김용갑, 김우경, 김정준 | 출판사: 길벗), 유튜브 주간컴공TV