- 계층적 자료구조 (상하관계를 가지고 있음)
- 상위계층의 자료를 하위계층의
parent라고 함
- 반대로는 상위계층의
children이라고 함
parent는 다수의 children을 가질 수 있지만 children은 하나의 parent를 가질 수 있음
- 이진 트리(Binary Tree)
- 완전 이진 트리(Complete Binary Tree)
- 마지막 오른쪽 노드를 제외한 모든 노드는 무조건 채워져 있어야 한다.
- 정 이진트리(Full Binary Tree)
- 모든 노드가 0개 or 2개의 자식 노드를 갖는 이진 Tree
- 이진 탐색 트리(Binary Search Tree)
- 중복된 값이 없으면서 왼쪽 자식 노드 값 < root 노드 < 오른쪽 자식 노드 값을 만족하는 이진 Tree
24
/ \
15 28
/ \ / \
2 19 27 30
- Pre order (전위 순회) : Root 부터 왼쪽 모든 노드 탐색 후 오른쪽
24 -> 15 -> 2 -> 19 -> 28 -> 27 -> 30
- In order (중위 순회) : 맨 왼쪽 아래 Node부터 Root, 오른쪽
2 -> 15 -> 19 -> 24 -> 27 -> 28 -> 30
- Post order (후위 순회) : 맨 왼쪽 아래 Node부터 오른쪽 탐색 후 Root
2 -> 19 -> 15 -> 27 -> 30 -> 28 -> 24