[자료구조] 트리 간략 정리

이진트리와 이진탐색트리

• 이진트리 : 각 노드 최대 두개의 자식을 갖음
• 이진탐색트리 : 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들 / 이러한 특징을 갖음

완전이진트리와 전이진트리, 포화이진트리

• 완전이진트리 : 트리의 모든 높이에서 노드가 꽉 차야함. 마지막 레벨은 제외, 허나 왼쪽에서 오른쪽으로 채워야함
• 전이진트리 : 모든 노드 자식이 없거나 정확히 두 개 있는 경우
• 포화이진트리 : 전이진트리 + 완전이진트리 / 2^k-1 (K는 트리의 높이)

이진트리순회

• 중위순회 : 왼쪽 -> 현재 -> 오른쪽
• 전위순회 : 현재-> 왼쪽 -> 오른쪽
• 후위순회 : 왼쪽 -> 오른쪽 -> 현재