[정보처리기사] [1과목 - 데이터베이스] 5. 자료 구조의 기본 -이진 트리

이진 트리의 정의

　- 이진 트리 : 차수(Degree)가 2 이하인 노드들로 구성된 트리, 즉 자식이 둘 이하인 노드들로만 구성된 트리

이진 트리의 특성

　- 이진 트리의 레벨 i에서 최대 노드의 수는  이다

　- 이진 트리에서 Terminal Node(단말 노드, 잎 노드) 수가 , 차수가 2이 노드 수가 라 할 때 이 된다

이진 트리의 종류

　- 정이진 트리(Full Binary Tree)

　　＊ 정어진 트리는 깊이(Depth)가 k일 때 전체 노드의 수가 1개의 노드이고, 레벨 i마다 개의 노드들로 꽉 찬 트리를 말함

　- 전이진 트리(Complete Binary Tree)

　　＊ 노드의 수가 n개일 때, 정이진 트리의 각 노드에 붙인 1 ~ n의 일련번호와 1:1 대응되는 트리

　　＊ 중간에 빈 부분이 있으면 전이진 트리가 될 수 없음

　- 사향 이진 트리(Skewed Binary Tree)

　　＊ 사향 이진 트리는 루트 노드로부터 왼쪽 또는 오르쪽으로만 기울어진 트리, 즉 왼쪽 또는 오른쪽 자식이 없는 노드들로만 구성된 트리를 말함

　　＊ 왼쪽 사향 이진 트리 : 오른쪽 자식이 없는 노드들로만 구성된 트리

　　＊ 오른쪽 사향 이진 트리 : 왼쪽 자식이 없는 노드들로만 구성된 트리