Tree Traversal
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
Breadth-First Searh (BFS)
-
Breadth-First Search : 인접한 노드를 모두 탐색한 후, 다음 깊이의 노드를 탐색함
-
BFS 수행 방법 (Iteratively)
- 방문했던 노드의 값을 저장하기 위해 queue와 data 배열을 생성함
- queue에 root 노드를 넣음
- queue에 아무것도 없을 때까지 아래 과정을 반복해서 수행함
3-1. queue에서 한 노드를 꺼내와서, 노드의 값을 data에 저장함
3-2. 노드가 left 프로퍼티를 가지고 있다면, 노드의 left를 queue에 넣음
3-3. 노드가 right 프로퍼티를 가지고 있다면, 노드의 right를 queue에 넣음 - 값들이 저장된 data를 반환함
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current = this.root;
while(true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
BFS() {
let node = this.root,
data = [],
queue = [];
queue.push(node);
while(queue.length) {
node = queue.shift();
data.push(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return data;
}
}
// 10
// 5 13
// 2 7 11 16
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(13);
tree.insert(11);
tree.insert(2);
tree.insert(16);
tree.insert(7);
tree.BFS(); // [10, 5, 13, 2, 7, 11, 16]Depth-First Search (DFS)
- Depth-First Search (DFS)
- Depth-First Search PreOrder : node -> left -> right 순으로 탐색
- Depth-First Search PostOrder : left -> right -> node 순으로 탐색
- Depth-First Search InOrder : left -> node -> right 순으로 탐색
Depth-First Search - PreOrder
- DFS PreOrder 수행 방법 (Recursively)
- 방문한 노드의 값을 저장하기 위한 배열을 생성함
- current 변수에 root를 저장함
- 노드를 인수로 받은 helper function을 작성함
3-1. 노드의 값을 생성한 배열에 넣음
3-2. 노드가 left 프로퍼티를 가지고 있다면, 노드의 left를 인수로 받은 helper function을 호출함
3-3. 노드가 right 프로퍼티를 가지고 있다면, 노드의 right를 인수로 받은 helper function을 호출함 - current 변수를 인수로 받은 helper function을 호출함
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current = this.root;
while(true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
DFSPreOrder() {
let data = [];
function traverse(node) {
data.push(node.value);
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
}
// 10
// 5 13
// 2 7 11 16
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(13);
tree.insert(11);
tree.insert(2);
tree.insert(16);
tree.insert(7);
tree.DFSPreOrder(); // [10, 5, 2, 7, 13, 11, 16]Depth-First Search - PostOrder
- DFS PostOrder 수행 방법 (Recursively)
- 방문한 노드의 값을 저장하기 위한 배열을 생성함
- current 변수에 root를 저장함
- 노드를 인수로 받은 helper function을 작성함
3-1. 노드가 left 프로퍼티를 가지고 있다면, 노드의 left를 인수로 받은 helper function을 호출함
3-2. 노드가 right 프로퍼티를 가지고 있다면, 노드의 right를 인수로 받은 helper function을 호출함
3-3. 노드의 값을 생성한 배열에 넣음 - current 변수를 인수로 받은 helper function을 호출함
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current = this.root;
while(true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
DFSPostOrder() {
let data = [];
function traverse(node) {
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
data.push(node.value);
}
traverse(this.root);
return data;
}
}
// 10
// 5 13
// 2 7 11 16
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(13);
tree.insert(11);
tree.insert(2);
tree.insert(16);
tree.insert(7);
tree.DFSPostOrder(); // [2, 7, 5, 11, 16, 13, 10]Depth-First Search - InOrder
- DFS InOrder 수행 방법 (Recursively)
- 방문한 노드의 값을 저장하기 위한 배열을 생성함
- current 변수에 root를 저장함
- 노드를 인수로 받은 helper function을 작성함
3-1. 노드가 left 프로퍼티를 가지고 있다면, 노드의 left를 인수로 받은 helper function을 호출함
3-2. 노드의 값을 생성한 배열에 넣음
3-3. 노드가 right 프로퍼티를 가지고 있다면, 노드의 right를 인수로 받은 helper function을 호출함 - current 변수를 인수로 받은 helper function을 호출함
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current = this.root;
while(true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
DFSInOrder() {
let data = [];
function traverse(node) {
if (node.left) traverse(node.left);
data.push(node.value);
if (node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
}
// 10
// 5 13
// 2 7 11 16
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(13);
tree.insert(11);
tree.insert(2);
tree.insert(16);
tree.insert(7);
tree.DFSInOrder(); // [2, 5, 7, 10, 11, 13, 16]When to use BFS, DFS
- BFS와 DFS 둘 다 모든 노드를 탐색하므로 시간 복잡도가 같음
- 공간 복잡도는 탐색하고자 하는 트리의 구조에 따라 다름
- 폭이 큰 트리를 탐색하는 경우, BFS보다 DFS가 공간 복잡도를 작음
- DFS의 사용 예
- DFS - InOrder :
- 반환한 배열의 노드들의 값이 오름차순으로 정렬되어 있음
- 정렬된 노드 값 배열이 필요할 때 유용함
- DFS - PreOrder :
- 트리를 복사하거나 저장하고자 할 때 유용함
- 트리를 평탄화(flatten)해서 저장할 때 사용함
- DFS - InOrder :
