Tree

트리

---

• 계층적 자료구조 (상하관계를 가지고 있음)
• 상위계층의 자료를 하위계층의 parent라고 함
• 반대로는 상위계층의 children이라고 함
• parent는 다수의 children을 가질 수 있지만 children은 하나의 parent를 가질 수 있음

종류

---

• 이진 트리(Binary Tree)
  • 노드가 최대 2개의 자식을 갖는 Tree
• 완전 이진 트리(Complete Binary Tree)
  • 마지막 오른쪽 노드를 제외한 모든 노드는 무조건 채워져 있어야 한다.
• 정 이진트리(Full Binary Tree)
  • 모든 노드가 0개 or 2개의 자식 노드를 갖는 이진 Tree
• 이진 탐색 트리(Binary Search Tree)
  • 중복된 값이 없으면서 왼쪽 자식 노드 값 < root 노드 < 오른쪽 자식 노드 값을 만족하는 이진 Tree

순회 방법

---

     24
    /   \
   15    28
  /  \   / \
 2   19 27  30

• Pre order (전위 순회) : Root 부터 왼쪽 모든 노드 탐색 후 오른쪽

24 -> 15 -> 2 -> 19 -> 28 -> 27 -> 30

• In order (중위 순회) : 맨 왼쪽 아래 Node부터 Root, 오른쪽

2 -> 15 -> 19 -> 24 -> 27 -> 28 -> 30

• Post order (후위 순회) : 맨 왼쪽 아래 Node부터 오른쪽 탐색 후 Root

2 -> 19 -> 15 -> 27 -> 30 -> 28 -> 24