📖
BFS・DFSの実装
BFS・DFSの実装
Binary Search Tree での BFS・DFSの実装
BFS
class BinarySearchTree {
constructor() {
this.root = null;
}
// BFS・DFSと関係がないため省略
insert(value) {
}
lookup(value) {
}
remove(value) {
}
// Iterative BFS
BFS() {
let currentNode = this.root:
let list = [];
let queue = [];
queue.push(currentNode);
while(queue) {
currentNode = queue.shift();
list.push(currentNode.value);
if (currentNode.left) {
queue.push(currentNode.left);
}
if (currentNode.right) {
queue.push(currentNode.right);
}
}
return list;
}
// Recursive BFS
BFSR(queue, list) {
if (!queue) {
return list;
}
let currentNode = queue.shift();
list.push(currentNode.value);
if (currentNode.left) {
queue.push(currentNodeleft);
}
if (currentNode.right) {
queue.push(currentNode.right);
}
return this.BFS(queue, list);
}
}
DFS
class BinarySearchTree {
constructor() {
this.root = null;
}
// BFS・DFSと関係がないため省略
insert(value) {
}
lookup(value) {
}
remove(value) {
}
DFSInorder() {
return traverseInOrder(this.root, []);
}
DFSPreOrder() {
return traversePreOrder(this.root, []);
}
DFSPostorder() {
return traversePostOrder(this.root, []);
}
}
// InorderのDFS
function traverseInOrder(node, list) {
if (node.left) {
traverseInOrder(node.left, list);
}
list.push(node.value);
if (node.right) {
traverseInOrder(node.left, list);
}
return list;
}
// PreorderのDFS
function traversePreOrder(node, list) {
list.push(node.value);
if (node.left) {
traverseInPreder(node.left, list);
}
if (node.right) {
traverseInPreder(node.left, list);
}
return list;
}
// PostorderのDFS
function traversePostOrder(node, list) {
if (node.left) {
traversePostOrder(node.left, list);
}
if (node.right) {
traversePostOrder(node.left, list);
}
list.push(node.value);
return list;
}
留意点
BFSはqueueを使用しており、木構造がかなり横に広い構造になっていた場合、メモリがかなり必要になる場合がある。
参考webサイト
このUdemyの講座を参考にしています。
Discussion