📖

BFS・DFSの実装

2024/03/27に公開

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の講座を参考にしています。
https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/

Discussion