트리 (Tree)

1. 트리[Tree] 란?

- computer science에서 계층구조(hierarchical structure)를 가진 추상자료형

- 트리는 노드로 구성되어 있는데, 노드들은 부모-자식 (parent-child)관계를 가진다.

- 직장에서 부장-과장(1,2,3)-(대리1,2,3,4,5,6) 이 업무연관성에 따라 그려진 조직도를 떠올려보면 좋다.

- File System, Programming enviroment 등에서 사용된다.

 

 

2. 용어(Terminology)

- Root (node) : parent가 없는 노드

- Internal node : 적어도(at least) 자식을 하나이상 가지는 노드

- External node : 자식이 없는 노드

- Ancestors of a node(a) : node(a)의 parent,grand parent, grand-grandparent........etc

- Depth of a node(a) : number of ancestors (조상노드의 수)

- Height of a tree(a) : maximum depth of any node (가장 큰 깊이를 가진 노드의 깊이가 트리의 높이)

- Descendant of a node : child, grandchild, ..... etc

 

 

3. Method

-기본적인 methods 

-(1) Generic methods

     - int size()

     - bool empty()

-(2) Accessor methods

     - position root()

     - listh<position> positions()

-(3) Position-based methods

     - position parent()

     - list<position> children

-(4) Query methods

     - bool isRoot()

     - bool isExternal()

 

 

4. 탐색(순회)

- 트리 자료구조를 탐색하는 방법은 많지만 여기서는 기본적인 2개만 다루겠다.

-(1) 전위순회

     - descendants들을 방문하기 전에 자신의 노드부터 방문처리 하는 것이다.

-(2) 후위순회

     - descendants를 먼저 방문하고 자신을 마지막에 방문처리하는 것이다.