데이터 입출력 구현 4

자료 구조

03. 비선형 구조

1) 트리(Tree)

1. 트리의 구조

• 그래프의 특수한 형태로 노드(Node)와 선분(Branch)으로 되어 있고, 정점 사이에 사이클(Cycle)이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조
• 트리 구조는 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합
• 트리는 프로그램의 에러를 찾아내는 구문 분석에서 필요한 기본 이론을 제공
• 이진트리 : 데이터를 검색하거나 자료를 정렬하는 알고리즘에서 사용
• 최소 비용 신장 트리 : 데이터 간의 관계를 유지하면서 최소의 비용이 드는 관계를 유지하는 방법

2. 트리의 용어

용어	설명
노드(Node)	원
간선(Edge), 링크(Link)	노드와 연결된 선
루트(Root Node) 노드	뿌리가 되는 노드
단(말)노드(Terminal)	자식이 없는 노드
간노드(Nonterminal	자식이 있는 노드
노드의 차수(Degree)	자식 노드의 개수
트리의 차수(Degree)	노드의 차수가 가장 큰 값
노드의 레벨(Level)	특정 깊이를 가지는 노드 집합
노드의 크기(Size)	자신을 포함한 자식 노드의 수
노드의 깊이(Depth)	루트에서 거쳐 간 간선의 수
노드의 높이(Height)	루트에서 가장 높은 노드
부노드(Parent)	부모 노드
자노드(Children)	자식 노드
제노드(Sibling)	형제 노드
숲(Forest)	루트를 제외한 나머지 부분
서브 트리(Sub Tree)	부분 집합 트리

2) 그래프(Graph)

1. 그래프 구조

• 데이터와 데이터 사이의 관계를 표현하는 비선형 구조
• 데이터의 검색, 데이터의 복잡도, 전자회로 분석 등 다양한 응용 분야에 적용

2. 그래프틔 용어

용어	설명
표시 방법	G = (V, E) V : 정점, E l 간선
정점(Vertex)	표현할 자료, 원으로 표시
간선(Edge)	자료 관계, 선이나 화살표로 표시
무방향성 그래프	화살표가 없는 간선
방향성 그래프	화살표가 있는 간선
완전 그래프	모든 정점에 간선이 연결된 경우
부분 그래프	그래프의 일부분, 자기 자신도 부분 그래프
경로(Path)	정점과 정점으로 연결된 경로
경로의 길이	경로에 존재하는 간선의 개수
단순 경로	시작 정점에서 종료 정점까지 중복이 없는 경로
사이클(Cycle)	시작, 종료 정점이 같고 경로의 길이가 2이상
해밀톤 사이클	모든 정점을 한 번씩 거쳐 가는 사이클
오일러 사이클	임의 경로에서 모든 간선을 한 번씩 사용한 사이클
차수(Degree)	정점에 연결된 간선의 수
진입차수	정점으로 들어오는 차수
진출차수	정점에서 나가는 차수
인접(Adjacent)	무방향 그래프에서 하나의 간선으로 연결된 정점
부속(Incident)	무방향 그래프에서 인접 관계에 있는 간선

3. 그래프의 특징

• 그래프는 네트워크 모델
• 트리와 같이 루트 노드, 부모-자식 등의 관계가 없음
• 2개 이상의 경로가 가능함
• 자기 자신을 향하는 간선은 없음
• 중복된 간선을 허용하지 않음

---

04. 이진 트리 순회

1) 이진 트리 순회의 개념

• 프로그램의 에러를 찾아내는 구문 분석에서 필요한 기본 이론을 제공
• 이진 트리 순회는 자료를 검색하거나 정렬하는 알고리즘에서 사용

2) 이진 트리 순회 3가지 방법

1. 중위(In-order) 순회 방법

• 좌측 -> 근노드 -> 우측
• 7 -> 3 -> 8 -> 1 -> 9 -> 4 -> 10 -> 0 -> 11 -> 5 -> 2 -> 6

2. 전위(Pre-order) 순회 방법

• 근노드 -> 좌측 -> 우측
• 0 -> 1 -> 3 -> 7 -> 8 -> 4 -> 9 -> 10 -> 2 -> 5 -> 11 -> 6

3. 후위(Post-order) 순회 방법

• 좌측 -> 우측 -> 근노드
• 7 -> 8 -> 3 -> 9 -> 10 -> 4 -> 1 -> 11 -> 5 -> 6 -> 2 -> 0

---

05. 폴리쉬 표기법

1) 폴리쉬 표기법의 개념

• 수학식처럼 연산자가 중간에 있는 중위식(Inorder), 연산자가 앞에 있는 전위식(Preorder), 연산자가 뒤에 있는 후위식(Postorder)으로 변형하는 표기법
• 전위식은 CPU 명령어 형식, 후위식은 프로그램의 문법 에러를 확인하는데 주로 사용
• 폴리쉬 표기법은 근노드가 연산자가 된다는 것 외에는 이진 트리 운행과 차이가 거의 없음

2) 폴리쉬 표기법의 종류

폴리쉬 표기법	배치 순서	예
중위식(Infix)	대상, 연산자, 대상	A+B
전위식(Prefix)	연산자, 대상, 대상	+AB
후위식(Postfix)	대상, 대상, 연산자	AB+

3) 중위식을 전위식으로 변경하는 예

• 연산 순위가 빠른 연산부터 전위식으로 변경한 후, 괄호로 구분하여 하나의 대상으로 생각하면 됨
• 같은 방법으로 진행하다가 마지막에는 괄호를 제거함

중위식	A = (B - C) * D + E

연산 순위	연산	전위식 변경 과정
1	(B - C)	- B C
2	(B - C) * D	* (- B C) D
3	(B - C) * D + E	+ (* - B C D) E
4	A = (B - C) * D + E	= A (+ * - B C D E)

전위식	= A + * - B C D E

4) 중위식을 후위식으로 변경하는 예

• 연산 순위가 빠른 연산부터 후위식으로 변경한 후, 괄호로 구분하여 하나의 대상으로 생각하면 됨
• 같은 방법으로 진행하다가 마지막에는 괄호를 제거함

중위식	A = (B - C) * D + E

연산 순위	연산	후위식 변경 과정
1	(B - C)	B C -
2	(B - C) * D	(B C -) D *
3	(B - C) * D + E	(B C - D *) E +
4	A = (B - C) * D + E	A (B C - D * E +) =

후위식	A B C - D * E + =

5) 전위식을 중위식으로 변경하는 예

• 연산자, 대상, 대상 형태로 되어 있는 곳을 찾아 중위식으로 변경한 후, 괄호로 구분하여 하나의 대상으로 생각하면 됨
• • B C가 연산자, 대상, 대상으로 된 첫 번째 전위식

전위식	= A + * - B C D E

연산 순위	연산	후위식 변경 과정
1	- B C	B - C
2	* (- B C) D	(B - C) * D
3	+ (* - B C D) E	(B - C) * D + E +
4	= A (+ * - B C D E)	A = (B - C) * D + E

중위식	A = (B - C) * D + E

6) 후위식을 중위식으로 변경하는 예

• 대상, 대상, 연산자 형태로 되어 있는 곳을 찾아 중위식으로 변경한 후, 괄호로 구분하여 하나의 대상으로 생각하면 됨
• B C -가 대상, 대상, 연산자로 된 첫 번째 후위식

후위식	A B C - D * E + =

연산 순위	연산	중위식 변경 과정
1	B C -	B - C
2	(B C -) D *	(B - C) * D
3	(B C - D *) E +	(B - C) * D + E +
4	A(B C - D * E +) =	A = (B - C) * D + E

중위식	A = (B - C) * D + E