[자료구조] 이진 트리..

[자료구조] 이진 트리..[자료구조] 이진 트리..[자료구조] 이진 트리..
이진 트리란...


트리의 노드 구조를 일정하게 정의하면 트리의 연산이 쉬워진다. 그래서 모든

노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 것이
이진 트리다.

이진 트리는 구별된 2개의 왼쪽, 오른쪽 자식 노드만을 가질 수 있으며, 공백 노

드도 이진 트리의 노드로 취급한다.

이진 트리에 있는 모든 노드는 왼쪽 자식 노드를 루트로 하는 왼쪽 서브 트리와
오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리를 갖는다. 그리고 이진 트리

의 서브 트리들 역시 모두 이진 트리여야 한다.



이진 트리의 특징...



1. n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가진다.

2. 높이가 n인 이진 트리가 가질 수 있는 노드의 최소 개수는 (n+1)개가 되며,

최대 개수는 (2ⁿ+¹ - 1)  개 이다.


이진 트리의 분류....


포화 이진 트리 : 포화 이진 트리는 모든 레벨에 노드가 꽉 차서 포화 상태인 이

진 트리를 의미한다. 즉 포화 이진 트리는 최대 노드수를 갖는 이진 트리다.


완전 이진 트리: 완전 이진 트리는 높이가 h 노드의 갯수가 n 이라면, 높이가 h

인 포화 이진트리의 노드 순서와 n 개 까지가 동일한 이진 트리이다. 

쉽게 얘기하면, n 개 까지의 순서는 포화 이진 트리와 똑 같지만 그 이후의 나머

지 노드는 공백 노드인 이진 트리가 완전 이진 트리이다.  


편향 이진 트리 : 이진 트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오

른쪽 서브 트리만 가지고 있는 트리를 편향 이진 트리라고 한다.

[자료구조] 이진 트리..[자료구조] 이진 트리..[자료구조] 이진 트리..