이진트리란
모든 노드가 최대 2개의 자식만을 가질 수 있는 트리
이진 트리를 사용한 기술
•
수식 이진 트리 (Expression Binary Tree)
•
이진 탐색 트리 (Binary Search Tree) - 매우 빠른 데이터 검색이 가능함
이진트리의 형태
이진 트리를 이용한 검색에서 높은 성능을 위해서는 트리의 노드들을 가능한 완전한 모습으로 배치해야한다.
포화 이진 트리 (Full Binary Tree)
이진트리의 모든 Node 가 자식을 두개씩 가지고 있는 트리의 형태
완전 이진 트리 (Complete Binary Tree)
이진 트리의 Leaf Node가 왼쪽 자식부터 차곡 차곡 채워진 형태
이진트리의 균형
트리의 형태와는 상관없이 오직 균형만으로 판단
높이 균형 트리 (Height Balanced Tree)
루트 Node 를 기준으로 왼쪽 하위 트리 (Sub Tree)와 오른쪽 하위 트리의 높이 (Height)가 1이상 차이나지 않는 이진 트리
완전 높이 균형 트리 (Completely Height Balanced Tree)
루트 Node 를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진트리
이진트리의 순회
순회 (Traversal) 는 트리 내의 노드들 사이를 돌아다니는 것
전위 순회 (Preorder Traversal)
1.
루트 노드부터 순회를 시작한다.
2.
왼쪽 하위 트리를 방문하고, 왼쪽 하위 트리의 방문이 끝나면
3.
오른쪽 하위 트리를 방문한다.
중위 순회 (Inorder Traversal)
1.
왼쪽 하위 트리부터 시작해서
2.
루트를 거쳐서
3.
오른쪽 하위 트리를 방문한다.
후위 순회 (Postorder Traversal)
1.
왼쪽 하위 트리를 방문한다.
2.
오른쪽 하위 트리를 방문한다.
3.
루트를 방문한다.
