1. 그래프

• 정점(Vertex)과 간선(Edge)의 두 집합으로 이루어지는 자료 구조
• 사이클이 있음
• 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분됨

방향 그래프

• 최대 간선수

  n(n-1)

무방향 그래프

• 최대 간선 수

  n(n-1)/2

2. 트리

• 정점(Node, 노드)와 선분(Branch, 가지)를 이용
• 사이클이 없는 그래프의 특수한 형태
• 하나의 기억 공간을 노드(Node)라 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 함

용어

1. 노드(Node): 자료 항목과 다른 항목에 대한 가지를 합친 것
2. 근노드(Root Node): 트리의 맨 위에 있는 노드
3. 차수(Degree): 각 노드에서 뻗어나온 가지의 수
4. 단말 노드(Terminal Node): 자식이 하나도 없는 노드
5. 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드
6. 조상 노드(Ancestors Node): 임의이 노드에서 근 노드에 이르는 경로상에 있는 노드들
7. 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
8. 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
9. 형제 노드(Broter Node, Sibling): 동일한 부모를 갖는 노드들
10. Level: 근 노드의 레벨을 1로 시작하여 층 별로 1씩 추가
11. 깊이(Depth): 트리에서 가질수 있는 최대의 레벨
12. 숲(Forest): 여러 개의 트리가 모여 있는 것
13. 트리의 디그리: 노드들의 차수중 가장 많은 수

3. 이진 트리

• 차수가 2 이하인 노드들로 구성된 트리
• 이진 트리의 레벨 i에서 최대 노드의 수는 2^(i-1)

  

4. 트리의 운행법

• 각 노드들을 찾아가는 방법
• 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖음

Preorder

• 이진 트리를 Root -> Left -> Right 순으로 운행

Inorder

• 이진 트리를 Left -> Root -> Right 순으로 운행

PostOrder

• 이진트리를 Left -> Right -> Root 순으로 운행

  

5. 수식의 표기법

• 이진 트리로 만들어진 수식을 운행하면 각 중위, 전위, 후위 표기법이 됨
• 전위 표기법(PreFix): 연산자 -> Left-> Right EX)+AB
• 중위 표기법(InFix): Left -> 연산자 -> Right, A+B
• 후위 표기법(PostFix): Left -> Right -> 연산자, AB+

표기법 변환 예시

1. 중위 표기법을 전위 표기법으로 변환

식: A*(B+C)

1. 연산 우선 순위에 따라 ()를 친다
   (A*(B+C))
2. 기호들을 괄호 안에서 가장 앞쪽으로 이동한다
   (*A(+BC))
3. 괄호를 제거한다
   *A+BC

2. 중위 표기법을 후위 표기법으로 변환

식 A*(B+C)

1. 연산 우선 순위에 따라 ()를 친다
   (A*(B+C))
2. 기호들을 괄호의 뒤로 옮긴다
   (A(BC+)*)
3. ()를 제거한다
   ABC+*

3. 전위 표기법을 중위 표기법으로 변환

식: *A+BC

1. 인접한 피연산자 두개와 왼쪽의 연산자를 () 친다
   (*A(+BC))
2. 연산자를 해당 피연산자 두 개의 가운데로 옮긴다
   (A*(B+C))
3. 필요 없는 ()를 지운다
   A*(B+C)

4. 후위 표기법을 중위 표기법으로 변환

식: ABC+*

1. 먼저 인접한 피연산자 두 개와 오른쪽의 연산자를 ()로 묶는다
   (A(BC+)*)
2. 연산자를 해당 피연산자 두 개의 가운데로 옮긴다
   (A*(B+C))
3. 필요 없는 ()를 지운다
   A*(B+C)

연습 문제

1. 다음 Prefix 연산식에 대한 연산 결과를 쓰시오.

*+53-72

정답
40