Study/정보처리기사
037 트리 - 1장 데이터 입출력 - 2과목 소프트웨어 개발
삼공비
2022. 1. 21. 15:28
- 트리의 개요
- 정점(node)과 선분(branch)을 이용하여 사이클을 이루지 않도록 구성한 그래프
- 노드 →하나의 기억 공간
- 링크 → 노드와 노드를 연결하는 선
- 가족 계보, 조직도 등에 적합
- 근 노드(root node) → 맨 위에 있는 노드
- 디그리 → 각 노드에서 뻗어 나온 가지의 수
- 단만 노드(Terminal Node) = 잎 노드(Leaf Node) → 자식이 하나도 없는 노드 = 디그리 0
- 자식 노드 → 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드 → 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드 → 동일한 부모를 갖는 노드들
- 트리의 디그리 → 디그리 중 가장 많은 수
- 트리의 운행법
- 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다
- 세가지 운행법
- 운행법 이름은 root의 위치가 어디 있느냐에 따라 정해진다
- Preorder : Root → Left → Right
- Inorder : Left → Root → Right
- Postorder : Left → Right → Root
- 수식의 표기법
- 산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용한다
- 인오더, 프리오더, 포스트오더로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 된다
- 전위 표기법 : 연산자 → left → right, +AB
- 중위 표기법 : left → 연산자 → right, A+B
- 후위 표기법 : left → right → 연산자, AB+
- infix → postfix or prefix로 바꾸기
- postfix or prefix는 스택을 이용하여 처리하므로 infix는 postfix나 prefix로 바꾸어 처리
- 예) X = A / B * (C + D) + E
- prefix
- 연산 우선순위에 따라 괄호로 묶는다. ( X = (((A / B) * (C + D)) + E))
- 연산자를 해당 괄호의 앞(왼쪽)으로 옮긴다. = (X +(*(/(AB)+(CD))E))
- 필요없는 괄호를 제거한다 prefix 표기 : = X + * / AB + CDE
- porstfix 1.연산 우선순위에 따라 괄호로 묶는다. ( X=((A / B) * (C + D)) + E ))
- 3.필요없는 괄호를 제거한다 Postfix 표기 : X A B / C D + * E + =
- 예) X = A / B * (C + D) + E
- postfix → infix
- 예) A B C - / D E F + * +
- postfix는 연산자를 해당 피연산자 두 개의 뒤로 이동한 것이르모 연산자를 다시 가운데로 옮긴다.
- 먼저 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶는다. ( ( A / ( B - C ) ) + ( D * ( E + F ) ) )
- 3.필요 없는 괄호를 제거한다. A / ( B - C ) + D * ( E + F )
- prefix → infix
- 예) + / A - B C * D + E F
- prefix는 연산자를 해당 피연산자 두 개의 앞으로 이동한것이므로 연산자를 다시 해당 가운데로 옮긴다.
- 먼저 인접한 피연산자 두 개와 왼쪽의 연산자를 괄호로 묶는다. ( + ( / A ( - B C ) ) ( * D ( + E F ) ) )
- 3.필요 없는 괄호를 제거한다. A / ( B - C ) + D * ( E + F )
- postfix or prefix는 스택을 이용하여 처리하므로 infix는 postfix나 prefix로 바꾸어 처리