Tree란
그래프 중 하나이다. 다른 점은 루트 노드가 있고 루트 노드에서 아래로 방향성을 띤다. 루트 노드는 자식 노드를 가지고 있다.
Tree 종류
Binary Tree : child node가 최대 2개까지 있는 트리를 binary tree라고 한다.
Binary Search Tree : 현재 노드를 기준으로 왼쪽 노드들의 값들은 현재 노드의 값보다 작아야되고 오른쪽은 큰 값으로 되어있는 트리를 binary search tree라고 한다.
Complete Binary Tree
- 이진 트리에서 child node가 왼쪽부터 채워져 있는 트리를 Complete Binary Tree라고 한다.
Full Binary Tree - 이진 트리에서 child node가 2개로 완전히 같거나 1개도 가지지 않는 트리를 Full Binary Tree라고 한다.
Perfect Binary Tree - 노드 개수가 2n - 1개를 가진다.
트리 순회 방법
- pre-order: A -> B -> C로 순회하는 방법
- in-order: B -> A -> C로 순회하는 방법
- post-order: B -> C -> A로 순회하는 방법
