그래프의 한종류로써 서로 다른 두 노드를 잇는 길이 하나뿐인 자료구조이다
계층적 관계를 표현하는 비선형 자료구조이다
하나의 root 노드를 가지며 루트 노드는 0개 이상의 자식 노드를 갖고 있다
그 자식 노드들도 0개 이상의 자식 노드를 갖고 있고 이는 반복적으로 정의된다
트리에는 사이클이 존재할 수 없다, 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다
각 노드는 어떤 자료형으로도 표현 가능하다
- root node: 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
- leaf node: 자식이 없는 노드
- internal node: leaf node가 아닌 노드
- edge: 노드를 연결하는 선 (link, branch 라고도 부름)
- siblings: 같은 부모를 가지는 노드
- size: 자신을 포함한 모든 자손 노드의 갯수
- depth: 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 edge의 수
- level: 트리의 특정 깊이를 가지는 노드의 집합
- height: root node에서 가장 깊숙히 있는 노드의 깊이
- 노드가 N개인 트리는 항상 N-1개의 edge을 가진다
- root node에서 어떤 노드로 가는 경로는 하나뿐이다
- 한 개의 root node만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다
완전 이진 트리는 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리를 말한다 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
전 이진 트리는 자식이 하나만 있는 노드가 존재 하지않는 이진 트리를 말한다
포화 이진 틀리는 전 이진 트리이면서 완전 이진 트리인 경우를 말한다 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드가 꽉 차 있어야 한다
포화 이진 트리는 노드의 개수가 정확히 nᵏ⁻¹(k는 틀리의 높이)개여야 한다
중위 순회는 왼쪽 가지, 현재 노드, 오른쪽 가지 순서로 노드를 방문하고 출력하는 방법을 말한다.
이진 검색 트리(BST)에서 중위 순회를 하면 O(n)의 시간으로 sort할 수 있다.
function inOrderTraversal(node) {
if (node !== null) {
inOrderTraversal(node.left)
visit(node)
inOrderTraversal(node.right)
}
}
전위 순회는 현재 노드, 왼쪽 가지, 오른쪽 가지 순서로 노드를 방문하고 출력하는 방법을 말한다
function preOrderTraversal(node) {
if (node !== null) {
visit(node)
preOrderTraversal(node.left)
preOrderTraversal(node.right)
}
}
후위 순회는 왼쪽 가지, 오른쪽 가지, 현재 노드 순서로 노드를 방문하고 출력하는 방법을 말한다
function postOrderTraversal(node) {
if (node !== null) {
postOrderTraversal(node.left)
postOrderTraversal(node.right)
visit(node)
}
}
3가지 방법중 가장 빈번하게 사용되는 순회 방식은 중위 순회이다.