[정보처리기사 필기] 데이터 입출력 구현 - 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+