이진 트리(Binary Tree)
자료구조 2015. 8. 17. 21:40이진 트리(Binary Tree)
모든 노드가 최대 2개의 자식을 가질 수 있는 트리이다.
이 이진 트리는 일반 트리처럼 데이터를 담는 용도로는 사용하기 곤란하지만,
예를 들어 수식 이진 트리, 아주 빠른 데이터 검색이 가능한 이진 탐색 트리가 있다.
이진트리와 일반트리의 차이점
일반 트리는 한 노드가 N개의 자식을 가질 수 있는 트리구조이지만 이진 트리는
모든 노드가 최대 2개의 자식을 가질 수 밖에 없는 트리구조를 가지고 있다.
또한 일반 트리는 데이터를 담을 수 있지만 이진 트리는 수식을 계산하거나 아주 빠른 데이터 탐색을 할 수 있다는 점에서 차이가 있다.
이진 트리의 종류
포화 이진 트리(Full Binary Tree)
- 모든 레벨의 노드들이 꽉 차있는 이진 트리 형태
- 잎 노드들이 모두 같은 깊이에 존재한다..
완전 이진 트리(Complete Binary Tree)
- 포화 이진 트리를 이루기 전의 단계
- 잎 노드들이 트리의 왼쪽부터 차례대로 채워진다.( 채워져 있지 않으면 안됨)
높이 균형 트리(Height Balanced Tree)
- 루트 노드(부모노드)를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지
않는 이진 트리를 일컫는다.
완전 높이 균형 트리(Completely Height Tree)
- 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리를 말한다.
트리 순회법
순회(Traversal)란???
- 트리 내의 노드들 사이를 돌아다니는 것을 말한다.
- 순회는 몇 가지 규칙에 근거해서 내부를 돌아다니게 된다.
- 효율적인 방법으로 원하는 데이터에 접근할 수 있는 방법을 제공하게된다.
전위 순회(Preorder Traversal)
1. 루트 노드부터 시작해서 아래로 내려온다.
2. 왼쪽 하위 트리를 방문한다. 방문이 끝나면
3. 오른쪽 하위 트리를 방문하는 방식이다.
중위 순회(Inorder Traversal)
- 중위 순회는 하위 트리부터 방문한다. 왜그럴까????????
- 트리는 하위 트리의 집합이라고 할 수 있고, 하위 트리 역시 또 다른 하위 트리의 집합이라고
할 수 있다.
- 그리고 중위 순회가 응용되는 것은 대표적인 예로 수식 트리가 있다.
1. 왼쪽 하위 트리부터 시작한다.
2. 루트를 거친다.
3, 오른쪽 하위 트리를 방문한다.
후위 순회(Postorder Traversal)
- 후위 순회는 전위 순회와 정반대의 방법으로 진행하면된다.
1. 왼쪽 하위 트리부터 시작
2. 오른쪽 형제 노드를 방문하고
3. 루트 노드를 방문한다.
트리 소멸 할 때
트리를 구축할 때는 노드들이 어떤 순서대로 생성되든 문제가 되지 않지만,,,
트리를 없앨 때는 반드시 잎 노드부터 자유 저장소에서 제거해야한다.
따라서 잎 노드부터 방문해서 루트 노드까지 거슬러 올라가며 방문하는 후위 순회를
이용하면 이진 트리 전체를 문제없이 소멸시킬 수 있다.
'자료구조' 카테고리의 다른 글
AVL 트리 (0) | 2015.08.24 |
---|---|
Red Black Tree (0) | 2015.08.19 |
트리 (0) | 2015.08.17 |
순차탐색 (0) | 2015.08.17 |
순환 큐 (Circle Queue) (0) | 2015.07.29 |