트리는 기본적으로 비선형 구조이다
BFS (너비 우선 탐색)
기본적으로 선입선출(FIFO) 방식으로 구현 가능
이진트리의 경우 최상위 루트부터 시작하여 좌,우 child 여부를 확인하여 queue에 push 해주고 반복문 안에서 shift를 통해서 탐색한다.
무조건 이진트리일 필요는 없다.
DFS (깊이 우선 탐색)
기본적으로 stack 을 사용해서 구현한다
DFS에는 크게 3가지 방법이 있다
- 전위 순회 - 루트부터 시작해서 왼쪽을 순회한 뒤 오른쪽을 순회하는 방법
현재 루트를 기준으로 재귀 함수를 실행하여 좌, 우에 값이 있는지 확인한다. - 후위 순회 - 제일 마지막에 루트를 방문하고 최하단 노드를 모두 확인한 뒤 상위 노드를 방문하는 방법
- 정위 순회 - 루트를 기준으로 왼쪽만을 확인한 뒤 상위 노드를 방문하고 오른쪽을 확인하는 방법
