1. 트리의 개요
: 트리는 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태이다.
-
트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 한다.
-
트리는 가족의 계보(족보), 조직도 등을 표현하기에 적합하다.
-
트리 관련 용어
- 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
- 근 노드(Root Node): 트리의 맨 위에 있는 노드
- 디그리(Degree, 차수): 각 노드에서 뻗어 나온 가지의 수
- 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 디그리가 0인 노드
- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들
- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들
- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들
- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수
2. 트리의 운행법
: 트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다.
-
이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다.
-
이진 트리의 운행법은 다음 세 가지가 있다.
- Preorder : Root -> Left -> Right
- Inorder : Left -> Root -> Right
- Postorder : Left -> Right -> Root
3. 수식의 표기법
: 산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용한다. 이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 된다.
- 전위 표기법(PreFix) : 연산자 -> Left -> Right
- 중위 표기법(InFix) : Left -> 연산자 -> Right
- 후위 표기법(PostFix) : Left -> Right -> 연산자
