이진 트리(Binary Tree)

이진 트리(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. 루트 노드를 방문한다.

 

트리 소멸 할 때

트리를 구축할 때는 노드들이 어떤 순서대로 생성되든 문제가 되지 않지만,,,

트리를 없앨 때는 반드시 잎 노드부터 자유 저장소에서 제거해야한다.

따라서 잎 노드부터 방문해서 루트 노드까지 거슬러 올라가며 방문하는 후위 순회를

이용하면 이진 트리 전체를 문제없이 소멸시킬 수 있다.