이진 트리

이진트리 (Binary Tree)

특징

• 일반적인 트리는 한 개의 노드가 여러 개의 자식 노드를 가질 수 있다.
• 이진 트리는 노드 1개 당 최대 2개의 자식 노드를 가질 수 있다.

종류

포화 이진트리 (Full Binary Tree)

• 리프 노드(최하단 노드)를 제외한 모든 노드가 2개의 자식 노드를 가진 구조.

완전 이진트리 (Complete Binary Tree)

• 왼쪽 노드부터 점진적으로 채워진 구조

높이 균형 트리 (Height Balanced Tree)

• 왼쪽, 오른쪽 트리의 높이의 차이가 1이하인 트리

구현

순회

• 전, 중, 후를 root의 순서로 보면 이해하기 쉽다.

전위순회 (Preorder)

• 순서 : root -> 왼쪽 노드-> 오른쪽 노드

중위순회 (Inorder)

• 순서 : 왼쪽 노드 -> root -> 오른쪽 노드

후위순회 (Postorder)

• 순서 : 왼쪽 노드 -> 오른쪽 노드 -> root