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

자료구조

by ~지우~ 2022. 4. 11. 11:13

728x90

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개인 트리

728x90

[자료구조] 이진탐색트리(binary search tree) (0)	2022.04.11
[자료구조] 트리(tree) 용어 정리하기 (0)	2022.04.11
[자료구조] 이진탐색트리(binary search tree) - AVL tree (0)	2022.03.28
[자료구조] 트리 탐색(tree traversal) 방법- inorder traverse, postorder traverse, preorder traverse, level order traversal (0)	2022.03.18
[자료구조] linked list로 큐(queue) 구현하기 (0)	2022.03.13