[자료구조] 비선형 자료구조 - 트리

트리의 정의

- 정점(Node, 노드),과 선분(Branch, 가지)을 이용하여 나타냄

- 사이클을 이루지 않도록 구성된 그래프의 한 형태

- 노드(Node) : 하나의 기억 공간

- 링크(Link) : 노드와 노드를 연결하는 선

- 가족의 족보, 조직도 등의 표현에 적합

 

트리 관련 용어

- 노드(Node) : 트리의 기본 요소로서 자료 항목과 자른 항목에 대한 가지를 합친 것

- 근 노드(Root Node) : 트리의 맨 위에 있는 노드

- 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수

- 단말 노드(Terminal Node) : 자식이 하나도 없는 노드 ( = 차수가 0인 노드)

- 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들

- 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들

- 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들

- 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

 

트리 운행법

: 트리를 구성하는 각 노드들을 찾아가는 방법

: 이진 트리의 운행법은 산술식의 표기법과 연관성을 가짐

- Preorder 운행 : Root - Left - Right 순으로 운행

- Inorder 운행 : Left - Root- Right 순으로 운행

- Outorder 운행 : Left - Right - Root 순으로 운행

 

수식 표기법

: 산술식의 계산을 위해 기억 공간에 기억시키는 방법

: 이진 트리로 만들어진 수식을 각 운행 방법에 따라 운행하면 전위, 중위, 후위 표기법이 됨

- 전위 표기법(PreFix) : 연산자 - Left - Right

- 중위 표기법(InFix) : Left - 연산자 - Right

- 후위 표기법(PostFix) : Left - Right - 연산자