트리의 정의
# 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다.
# 트리란 정점(vertex)과 정점과 정점 사이를 연결시켜주는 간선(edge)으로 이루어진 순환 구조가 없는 특별한 형태의 연결 그래프(Graph)의 일종이다.
# 즉, 트리는 이 다음에 다룰 그래프의 특수한 형태이다. 이 정의는 그래프를 공부하고 나면 더 잘 이해가 될 것이다.
# 트리는 다음 조건들을 만족하는 하나 이상의 노드로 구성된 유한 집합이다.
1) 모든 노드가 시작되는 특정한 뿌리 노드(root node)가 존재한다.
2) 노드와 노드 사이의 간선이 하나만 존재한다.
3) 각 노드들 사이에 순환이 존재하지 않는다.
4) 뿌리 노드를 제외한 다른 노드들도 자신을 뿌리 노드로 하는 트리여야 한다.
# 트리는 정의 자체가 재귀적이기 때문에 이미지로 이해하는 것이 편하다. 즉, 아래와 같은 형태면 트리이다.
# 순환이 없다는 말을 이미지로 표현하면 원과 원을 연결하는 선이 닫힌 도형을 이루지 않는다는 뜻이다.
트리 관련 용어
# 노드(node) : 트리의 구성요소. 데이터가 직접 저장되는 공간이다. 위의 그림의 원에 해당한다. (그래프에서는 정점이라고 한다.)
# 부모 노드(parent node) : 임의의 노드에 연결된 상위 노드.
# 자식 노드(child node) : 임의의 노드에 연결된 하위 노드.
# 조상 노드(Ancestor node) : 임의의 노드의 부모 노드와 그 부모 노드의 부모 노드들.
# 후손 노드(Descendant Node) : 임의의 노드의 자식 노드와 그 자식 노드의 자식 노드들.
# 형제 노드(sibling Node) : 같은 부모 노드를 갖는 자식 노드들.
# 뿌리 노드(root node) : 트리의 최상위 노드. 모든 노드의 조상이 되며, 부모 노드가 없는 노드.
# 단말 노드(teminal node) 혹은 잎 노드(leaf node) : 자식 노드가 없는 노드들.
# 내부 노드(Internal node) 혹은 가지 노드(branch node) 혹은 비단말 노드(nonteminal node) : 단말 노드를 제외한 트리의 모든 노드들.
# 차수(degree) : 임의의 노드의 자식 노드의 수.
# 트리의 차수(degree of tree) : 트리를 구성하는 노드들의 차수 중 가장 큰 값.
# 단계(Level) : 뿌리 노드의 레벨을 0으로 하고, 아래로 내려올수록 1씩 증가하는 값.
# 트리의 높이(height) 또는 깊이(depth) : 트리를 구성하는 노드들의 레벨 중 가장 큰 값.
# 경로(path) : 임의의 노드에서 다른 노드까지의 순서.
ex) 아래 그림에서 F노드에서 D노드까지의 경로는 F->B->A->D
# 부트리(SubTree) : 트리에 속하는 작은 트리. (하나의 트리 내부에서 나누는 개념)
# 트리군(forest) : 여러개로 분리된 트리들의 유한 집합. (서로 독립적인 트리들의 집합)
트리의 종류
자식 노드 수에 따른 분류
# 일반 트리(General Tree) : 각 노드의 차수에 제한이 없는 트리.
# 이진 트리(Binary Tree) : 트리의 차수가 2이하인 트리.
# 사진 트리(QuadTree) : 트리의 차수가 4인 트리.
# 구분하자면 수없이 구분할 수 있겠지만 이 이상의 구분은 무의미한 것 같다. 가장 많이 쓰이는 트리는 이진트리이다.
순서 트리와 비순서 트리
# 순서 트리(Ordered Tree) : 노드들의 좌우 배열 순서가 고정되어 노드의 위치가 중요한 트리.
# 비순서 트리(Oriendted Tree) : 노드간에 레벨 차이는 의미가 있지만 위치는 중요하지 않은 트리.
닮은 트리와 대등한 트리
# 닮은 트리(Similar Tree) : 구조는 동일하지만 노드의 내용이 다른 트리.
# 대등한 트리(Equivalent Tree) : 구조뿐만 아니라 노드의 내용까지 완전히 같은 트리.
이진 트리의 분류
# 엄밀한 이진 트리 : 트리를 구성하는 각 노드의 차수가 0 또는 2인 트리.
# Knuth 이진 트리 : 트리를 구성하는 노드의 차수가 2 이하인 트리. 즉, 모든 이진트리가 knuth 이진 트리이다.
# 포화이진트리 혹은 정이진트리(Full Binary Tree) : 엄밀한 이진 트리면서 높이 h인 트리의 모든 리프노드가 레벨 h에 있는 트리.
# 완전이진트리 혹은 전이진트리(Complete Binary Tree) : 높이 h인 트리의 레벨 h-1까지는 포화 이진 트리이고, 레벨 h에서 왼쪽부터 리프 노드를 채우는 트리.
# 사향이진트리(Skewed Binary Tree) : 트리의 왼쪽 부트리나 오른쪽 부트리가 없는 이진 트리.
균형트리와 완전균형트리
# 균형트리(Height Balanced Tree) : 뿌리 노드를 기준으로 왼쪽 부트리와 오른쪽 부트리의 높이 차이가 1이하인 트리.
# 완전균형트리(Completely Height Balanced Tree) : 뿌리 노드를 기준으로 왼쪽 트리와 오른쪽 부트리의 높이가 같은 트리.
#이 외의 수식트리나 레드블랙트리 등 특별한 용도를 가진 트리나 특별한 기준으로 구성되는 트리등도 있다.