트리 순회
모든 노드를 한 번씩 도는 방법. 앞서 학습한 이진 탐색 트리 뿐 아니라, 모든 트리 구조에서 사용가능한 순회 알고리즘이다. 다른 섹션들보다 재귀를 더 많이 사용할 예정.
너비 우선 탐색 (BFS)
요소들을 거쳐가는 일반적인 순서를 기준으로 탐색 방식을 구분하였다. CSS Flexbox의 direction을 row로 주거나, column으로 주는 것도 이와 유사하다고 볼 수 있을 듯 하다.
너비 우선 탐색법(BFS)은 최상단 노드(Root)부터 가로 횡을 기준으로 수평으로 한 줄씩 내려가며 순회하는 방식이다.
구현
선입선출 구조를 갖는 큐 방식을 통해 BFS를 구현한다. 배열이나 리스트에서 Push / Shift 메서드를 사용하면 된다. 큐는 한 줄에 존재하는 노드를 담아놓는 버퍼 역할을 하며, 한줄 씩 읽을 때마다 큐에 존재하는 원소들을 결과 리스트로 이동시킨다.
과정을 좀 더 정확히 설명하자면 특정 노드와 같은 줄에 있는 노드 값을 큐에 넣은 후, 특정 노드의 좌/우 자식 노드 여부를 확인하고 이들도 큐에 넣어주는 방식이다.
BFS() {
var queue = [];
var node = this.root;
var result = [];
// 1. 루트 노드를 큐에 넣는다.
queue.push(node);
// 2. queue에 무언가가 들어있다면, 루프를 반복한다.
while (queue.length) {
node = queue.shift();
result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return result;
}
깊이 우선 탐색 (DFS)
전위 순회(PreOrder)
DFS를 구현하기 위해 필요한 추가적인 헬퍼 메서드가 존재한다. 인수를 입력받지 않는, 노드의 값을 변수에 넣어 저장하는 역할을 한다. 이를 활용하여 CurrentNode를 갱신해가며 Result List에 노드 값을 넣어준다. 해당 알고리즘은 재귀를 사용하고, 구현보다 이해의 난도가 좀 더 높은 듯 하다. 호출 스택 등의 디버깅을 통해 과정을 이해하는 것을 추천
DFSPreOrder() {
var current = this.root;
var result = [];
function traverse(node) {
result.push(node.val);
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
}
traverse(current);
return result;
}
후위 순회(PostOrder)
후위 순회에서는 어떤 노드이든지 모든 자식을 먼저 방문한 후 해당 노드를 방문하게 된다. 따라서 루트 노드가 순회하는 가장 마지막 노드가 된다. 전위 탐색에서 구현한 코드에서 단순히 Result List에 노드 값을 Push하는 순서만 바꿔주면 된다. 그러나 결과에는 큰 변화가 발생한다.
DFSPostOrder() {
var current = this.root;
var result = [];
function traverse(node) {
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
result.push(node.val);
}
traverse(current);
return result;
}
정리
먼저 두 방법론을 비교해보자. 두 방법론에서의 시간 복잡도는 모든 트리 노드를 순회하는 것이기 때문에 동일하다. 따라서 큐에 들어가는 용량의 공간 복잡도를 들여다 봐야 한다.
깊이가 얕고 넓은 형태의 트리 구조라면, 적은 재귀 메서드 사용으로 트리를 순회할 수 있는 DFS가 유리할 것이고, 반대로 깊고 긴 트리에서는 BFS를 통한 연산이 효율적일 것이다.
