Tree
- Queue, Stack은 Linear하지만 Tree는 X (계층적)
Terminology
- Root Node : 트리 구조에서 최상위에 존재하는 노드
- Node : 트리의 구성요소
- Edge : 노드와 노드를 연결하는 선
- Leaf Node : 자식 노드가 없는 최하위 Level의 노드
- Sub-Tree : 큰 트리에 속하는 작은 트리
- Level : 트리의 각 층별로 숫자를 매김
- Height : 트리의 최고 Level
Kind
- Binary Tree : "이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의서브트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진트리이어야 한다.”
- Full Binary Tree : 모든 레벨이 꽉 찬 트리
- Complete Binary Tree : 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리
Implementation
- Array, LinkedList 모두 구현 가능
- Heap 이라는 자료구조와 연관 (밑에 자료 정리)
Traversal