Binary Tree & 순회

*목차

전위, 중위, 후위순회 차이
Binary Tree
Binary Search Tree
unbalanced
Complete Binary Tree
Full Binary Tree
Perfect Binary Tree

 

Binary Tree

 

전위(Preorder)	중위(Inorder)	후위(Postorder)
Root, Left , Right	Left, Root, Right	Left, Right, Root
1 -> 2 -> 4 -> 5 -> 3	4 -> 2 -> 5 -> 1 -> 3	4 -> 5 -> 2 -> 3 -> 1

 

*Binary Tree

노드가 최대 2개의 자식노드를 가진다.

 

*Binary Search Tree

Root 노드를 기준으로 왼쪽자식 노드는 작은 값, 오른쪽 노드는 큰 값을 가진다.

Binary Search Tree

*unbalanced

왼쪽 자식노드와 오른쪽 자식 노드가 불균형이다.

balanced(redblack tree, AVL tree)

 

unbalanced

 

*Complete Binary Tree

모든 노드들이 같은 높이의 레벨에서 왼쪽부터 채워진다.

Complete Binary Tree

*Full Binary Tree

노드들의 child가 하나도 없거나 2개인 경우만 존재한다.

Full Binary Tree

*Perfect Binary Tree

마지막 레벨에서 빈공간 없이 모든 노드들이 2개의 자식노드를 가진다.

Perfect Binary Tree