[자료구조/java] 트리 (Tree)

* 트리 (Tree)

"비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조(Hierarchical Data Structure)이다."

- 트리를 구성하는 원소(자료)를 노드라고 하고 노드를 연결하는 선을 간선(edge)이라 한다.

- 트리의 시작 노드를 루트 노드(Root)라 하고 레벨(level) 0이 된다.

- 각 노드는 자식노드 수만큼의 서브트리(subtree)를 갖는다.

- 한 노드가 가지는 서브 트리의 수, 즉 자식노드의 수를 그 노드의 차수(degree)라 한다.

- 노드의 차수 중에서 가장 큰 차수는 트리의 차수가 된다. 트리 A의 전체 차수는 3이된다.

- 자식이 없는 노드를 리프 노드(Leaf Node) 또는 단말 노드라고 한다.

- 조상은 자기와 연결된 선을 따라 위로 올라가면서 만나는 사람들이다.

- 자손은 자기와 연결된 선을 따라 아래로 내려가면서 만나는 사람들이다.

- 높이는 루트에서 그 노드에 이르는 경로에 있는 간선의 수가되고, 최대 레벨이 그 트리의 전체 높이가 된다.

- 나무가 모이면 숲이 되듯이 여러 트리의 집합을 포리스트(forest)라고 한다.