Binary Tree

컴퓨터 과학에서 사용되는 데이터 구조의 하나로, 뿌리가 있는 나무 구조(트리, tree)에서 어떤 노드의 자식의 수가 최대 2개를 넘지 않는 트리를 말한다.

typedef struct Node {

int data;

struct Node *left;

struct Node *right;

} Node;

Node* root;

이진 트리의 종류로는 포화 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 높이 균형 트리(Height Balanced Tree), 완전 높이 균형 트리(Completely Height Balanced Tree) 등이 있으며, 각각의 특징은 다음과 같다.

- 포화 이진 트리 : 모든 레벨의 노드가 꽉 차있으며, 단말 노드를 제외한 모든 노드의 차수가 2인 이진 트리.
- 완전 이진 트리 : 단말 노드들이 트리 왼쪽부터 채워진 형태의 이진 트리.
- 높이 균형 트리 : 모든 단말 노드의 깊이 차이가 많아야 1인 이진 트리.
- 완전 높이 균형 이진 트리 : 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리.

* 출처 : https://www.tutorialspoint.com/data_structures_algorithms/