[정보처리기사] 2024 2차 실기 대비 - 트리 자료구조(전위/중위/후위 운행법)

1️⃣ 트리(TREE) 자료 구조

트리는 노드(Node)와 선분(Branch/가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
※ 그래프와 트리의 차이
 1. 트리는 무조건 방향이 존재하지만, 그래프는 선택이 가능
 2. 트리는 비순환 방식이지만, 그래프는 순환/비순환 중 선택이 가능
 3. 트리는 계층 모델이지만, 그래프는 네트워크 모델임 
아래에 첨부한 사진이 흔히 우리가 볼 수 있는 트리 자료 구조 중 하나인 이진 트리

 

2️⃣ 트리 관련 용어

ㆍ노드(Node) : 트리를 구성하는 기본 요소로, 데이터를 저장하는 단위
ㆍ루트(Root) : 트리의 최상위에 있는 노드로, 부모가 없는 유일한 노드(위 이미지에서는 A에 해당)
ㆍ디그리(Degree) : 한 노드가 가지고 있는 자식 노드의 수(eg. B : 2개, E : 1개, D : 2개...)
ㆍ부모 노드(Parent Node) : 특정 노드 상위에 연결된 노드(eg. D는 H와 I의 부모 노드)
ㆍ자식 노드(Child Node) : 특정 노드 하위에 연결된 노드(eg. H와 I는 D의 자식 노드)
ㆍ깊이(Depth) : 루트 노드부터 특정 노드까지의 경로 길이
ㆍ터미널 노드(Terminal Node) : 자식 노드가 없는 말단 노드(위 이미지에서는 H, I, J, F, G에 해당)

 

3️⃣ 전위/중위/후위 운행법

개념은 간단하기 때문에, 암기보다는 다양한 트리 구조에서 계산해 봐야 실수를 하지 않는 영역이다.

전위(Preorder) 운행
이진 트리를 Root > Left > Right 순으로 운행하며 노드들을 찾아가는 방법이다.
위 이미지를 예로 들면, A > B > D > H > I > E > J > C > F > G의 순서가 나온다.

중위(Inorder) 운행
이진 트리를 Left > Root > Right 순으로 운행하며 노드들을 찾아가는 방법이다.
위 이미지를 예로 들면, H > D > I > B > E > J > A > F > C > G

후위(Postorder) 운행
이진 트리를 Left > Right > Root 순으로 운행하며 노드들을 찾아가는 방법이다.
위 이미지를 예로 들면, H > I > D > J > E > B > F > G > C > A

---

📝 Reference

👉 길벗 2023 시나공 퀵이지 정보처리기사실기 교재 참조

👉 Claude 3.5 Sonnect, GPT 4o 답변 참조