[정보처리산업기사] 트리(Tree)

 

 

 

1. 정의

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

 

 

 

 

2. 용어

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

 

 

 

 

3. 트리의 운행법(Traversal)

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

 

 

 

 

4. 수식의 표기법

• 산술식을 계산하기 위해 기억시키는 방법
• 이진 트리를 많이 사용
• 이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Prostfix) 표기법이 됨
• 전위 표기법(PreFix) : 연산자 → Left → Right, +AB
• 중위 표기법(InFix) : Left → 연산자 → Right, A+B
• 후위 표기법(PostFix) : Left → Right → 연산자, AB+