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