1.너비우선탐색 BFS

BFS() {
let node = this.root;
let data = [];
let queue = [];
queue.push(node);
//queue에 노드가 있는 동안 루프를 돈다.
while (queue.length) {
node = queue.shift();
//dequeue된 노드 값을 data에 추가
data.push(node.val);
//왼쪽있으면 왼쪽도 넣고 오른쪽있으면 오른쪽도 넣고
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return data;
}
2. 깊이우선탐색 DFS
왼쪽으로 트리 수직방향으로 쭉 내려가서 탐색하는 방법
깊이우선탐색에는 세 가지 방법이 있다. 모두 재귀를 사용하며, 이 세 가지 방법의 각각의 코드들은 재귀의 헬퍼함수 내에서 data.push(node.value); 한 줄의 위치만 다르고 나머지는 동일한다.
PreOrder(전위순회)

DFSPreOrder() {
let date = [];
// let current = this.root;
function traverse(node) {
data.push(node.value);
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
InOrder(중위순회)

DFSInOrder() {
let data = [];
function traverse(node) {
if (node.left) traverse(node.left);
data.push(node.val);
if (node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
PostOrder(후위순회)

DFSPostOrder() {
let data = [];
function traverse(node) {
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
data.push(node.val);
}
traverse(this.root);
return data;
}
DFS와 BFS 시간복잡도는 같다. 하지만 공간복잡도 때문에 골라야한다.
가로로 넓은 트리일 경우 DFS
세로로 아주 깊은 트리일 경우 BFS
'자료구조' 카테고리의 다른 글
[JS] 해시테이블 (1) | 2022.12.22 |
---|---|
[JS] 이진 힙 (0) | 2022.12.21 |
[JS] 트리와 이진 탐색 트리 (0) | 2022.12.17 |
[JS] 스택(stack)과 큐(Queue) (0) | 2022.12.17 |
[JS]이중연결리스트 Doubly Linked Lists (0) | 2022.12.16 |