[알고리즘] [11] 트리 탐색

1. Breadth First Search

• 너비 우선 탐색은 인접 노드를 차례로 방문한 후 방문한 노드를 기준으로 하여 다시 해당 노드의 인접 노드를 차례로 방문하는 방식이다.
• 인접 노드를 탐색 후 다시 너비 우선 탐색을 진행하므로 선입선출 자료구조인 큐를 활용한다.

2. Depth First Search

• 깊이 우선 탐색은 루트 노드에서 출발하여 한 방향으로 경로가 있는 곳까지 탐색한 후 더 이상 갈 곳이 없을 때 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와 다른 방향의 노드 탐색을 반복하는 순회 방법이다.
• 재귀적으로 구현하거나 후입선출 자료구조인 스택을 활용한다.

---

3. 이진트리 순회 (traversal)

• 전위 순회 (preorder traversal) : 부모 노드 방문 후 자식 노드를 좌, 우 순서로 방문한다.
• 중위 순회 (inorder traversal) : 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순서로 방문한다.
• 후위 순회 (postorder traversal) : 자식 노드를 좌, 우 순서로 방문 후 부모 노드를 방문한다.

4. 힙 (heap)

• 완전 이진 트리의 노드 중 키 값이 가장 큰 노드 또는 가장 작은 노드를 찾는 자료구조
• 최대 힙과 최소 힙이 있다.
• 힙에 삽입 시 완전 이진 트리를 유지하도록 삽입하며, 우선 순위를 만족할 때까지 부모 노드와 자식 노드의 위치를 바꾼다.
• 힙은 루트 노드의 원소만을 삭제할 수 있다.
  >> 루트 노드의 원소값을 반환하고 마지막 노드를 루트 노드에 올린다.
  >> 우선 순위를 만족하도록 부모 노드와 자식 노드의 위치를 바꾼다.