[자료구조] 이진트리(binary tree)의 기본 개념

 

binary tree: leaf 노드를 제외한 모든 노드의 자식의 수가 최대 2개인 트리

 

특징: i번째 level의 최대 노드 개수는 2^(i-1)이다.

       height가 h인 트리가 가질 수 있는 노드의 최대 개수는 (2^h) - 1이다. 

 

struct node
{  
	int data;
    struct node *left_child;
    struct node *right_child;
};

 

full binary tree: leaf node와 root를 제외한 모든 노드의 child가 2개인 트리

 

 

complete binary tree: 가장 오른쪽 interior 노드의 right child만 없고, leaf node와 root를 제외한 모든 노드의 child가 2개인 트리