[정보처리기사 필기] 데이터 입출력 구현 - 029. 트리 Tree

1. 트리의 개요

• 정점(노드)과 선분(가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
  • 노드 Node : 하나의 기억 공간
  • 링크 Link : 노드와 노드를 연결하는 선
• 가족의 계보(족보), 조직도 등을 표현하기에 적합
• 트리와 관련된 용어

- 노드 Node : 트리의 기본 요소, 자료 항목과 다른 항목에 대한 가지를 합친 것 - 근 노드 Root Node : 트리의 맨 위에 있는 노드 - 디그리 Degree : 차수, 각 노드에서 뻗어나온 가지의 수 - 단말 노드 Terminal Node, 잎 노트 Leaf Node : 자식이 하나도 없는 노드, 디그리가 0인 노드 - 자식 노드 Son Node : 어떤 노드에 연결된 다음 레벨의 노드들 - 부모 노드 Parent Node : 어떤 노드에 연결된 이전 레벨의 노드들 - 형제 노드 Brother Node, Sibling : 동일한 부모를 갖는 노드들 - 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

2. 트리의 운행법

• 트리를 구성하는 각 노드들을 찾아가는 방법
• 이진 트리 운행법 : 산술식의 표기법과 연관성
  • Preorder 운행 : Root -> Left -> Right
  • Inorder 운행 : Left -> Root -> Right
  • Postorder 운행 : Left -> Right -> Root

3. 수식의 표기법 

• 이진 트리 표기법
  • 전위 표기법 (PreFix) : 연산자 -> Left -> Right, +AB
  • 중위 표기법 (InFix) : Left -> 연산자 -> Right, A+B
  • 후위 표기법 (PostFix) : Left -> Right -> 연산자, AB+