자료구조 - Chapter 08
트리(Tree)
트리
계층적인 관계(Hierarchical Relationship)을 표현하는 자료구조
- 노드(Node) : 트리의 구성 요서에 해당하는 A, B, C, D...같은 요소
- 간선(Edge) : 노드와 노드를 연결하는 연결선
- 루트 노드(root Node) : 트리 구조에서 최 상위에 존재하는 A와 같은 노드
- 단말 노드(terminal Node) : 아래로 다른 노드가 연결 되어 있지 않은 H, I, J, E, F, G 노드
- 내부 노드(internal Node) : 단말 노드를 제외한 모든 노드
이진트리(Binary tree)와 서브 트리(Sub tree)
서브 트리
큰 트리에 속한 작은 트리를 지칭한다.
이진 트리
루트 노드를 중심으로 두 개의 서브 트리로 나누어진다.
나뉘어진 두 서브 트리도 모두 이진 트리여야 한다.
위 조건 2개를 만족하면 이진트리가 된다. 이진 트리의 존재 자체가 재귀적이기 때문에 이렇게 정의한다.
포화 이진 트리(Full Binary tree)와 완전 이진 트리(Complete Binary Tree)
- 레벨 (level) : 트리의 각 층
- 높이(height) : 트리의 최고 레벨
포화 이진 트리
모든 레벨이 꽉 찬 이진트리를 지칭한다.
완전 이진트리
포화 이진 트리 처럼 모든 레벨이 꽉 찬 상태는 아니지만 빈 틈없이 노드가 채워진 이진트리
이진 트리의 구현
이진트리와 관련된 일부 연산은 재귀 호출의 형태를 보인다.
또한 아진 트리 역시 배열 기반, 연결 리스트 기반으로 구현이 가능하다.
예제 : 연결 리스트로 이진 트리 구현
예제 : 이진트리 순회
순회 방법
- 전위 순회(Preorder Traversal) : 루트 노드 먼저
- 중위 순회(Inorder Traversal) : 루트 노드 중간
- 후위 순회(Postorder Traversal) : 루트 노드 마지막
예제 : 트리로 수식 계산
