자료구조/알고리즘 - Tree traversal, BFS/DFS

1-6.트리 순회(Tree traversal)
 -특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
 -트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 있음

 (1)전위 순회(Preorder traverse)
 (2)중위 순회(inorder traverse)
 (3)후위 순회(postorder traverse)

 +균형 이진 탐색 트리 : 이진 탐색 트리의 문제점을 보완하고자 나온 트리

  *왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 것이 특징으로, 이러한 높이 차이를 균형인수(Balance Factor)라고 함.

1-7.BFS / DFS
 -그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적
 -하지만 그래프의 데이터는 배열처럼 정렬되어 있지 않기 때문에, 원하는 데이터를 찾으려면 하나씩 모두 방문해야함

 (1)너비 우선 탐색(Breadth-First Search : BFS)
  -가까운 정점부터 탐색하고, 더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문하는 방식
  -주로 두 정점 사이의 최단 경로를 찾을 때 사용
  -경로를 하나씩 전부 방문하기에, 최악의 경우 모든 경로를 다 살펴보아야 함

 (2)깊이 우선 탐색(Depth-First Search : DFS)
  -하나의 경로를 끝까지 탐색한 후, 찾고자 하는 정점이 아니라면 다음 경로로 넘어가 탐색하는 방식
  -한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용
  -BFS보다 탐색시간이 상대적으로 오래 걸림, 모든 노드를 완전히 탐색할 수 있음