깊이 우선 탐색(DFS)

깊이 우선 검색(DFS)은 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기 위한 알고리즘입니다. 하나는 루트에서 시작하여(그래프의 경우 임의의 노드를 루트로 선택) 역추적하기 전에 각 분기를 따라 가능한 한 멀리 탐색합니다.

/**
 * @typedef {Object} TraversalCallbacks
 *
 * @property {function(node: BinaryTreeNode, child: BinaryTreeNode): boolean} allowTraversal
 * - Determines whether DFS should traverse from the node to its child.
 *
 * @property {function(node: BinaryTreeNode)} enterNode - Called when DFS enters the node.
 *
 * @property {function(node: BinaryTreeNode)} leaveNode - Called when DFS leaves the node.
 */

/**
 * Extend missing traversal callbacks with default callbacks.
 *
 * @param {TraversalCallbacks} [callbacks] - The object that contains traversal callbacks.
 * @returns {TraversalCallbacks} - Traversal callbacks extended with defaults callbacks.
 */
function initCallbacks(callbacks = {}) {
  // Init empty callbacks object.
  const initiatedCallbacks = {};

  // Empty callback that we will use in case if user didn't provide real callback function.
  const stubCallback = () => {};
  // By default we will allow traversal of every node
  // in case if user didn't provide a callback for that.
  const defaultAllowTraversalCallback = () => true;

  // Copy original callbacks to our initiatedCallbacks object or use default callbacks instead.
  initiatedCallbacks.allowTraversal = callbacks.allowTraversal || defaultAllowTraversalCallback;
  initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback;
  initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback;

  // Returned processed list of callbacks.
  return initiatedCallbacks;
}

/**
 * Recursive depth-first-search traversal for binary.
 *
 * @param {BinaryTreeNode} node - binary tree node that we will start traversal from.
 * @param {TraversalCallbacks} callbacks - the object that contains traversal callbacks.
 */
export function depthFirstSearchRecursive(node, callbacks) {
  // Call the "enterNode" callback to notify that the node is going to be entered.
  callbacks.enterNode(node);

  // Traverse left branch only if case if traversal of the left node is allowed.
  if (node.left && callbacks.allowTraversal(node, node.left)) {
    depthFirstSearchRecursive(node.left, callbacks);
  }

  // Traverse right branch only if case if traversal of the right node is allowed.
  if (node.right && callbacks.allowTraversal(node, node.right)) {
    depthFirstSearchRecursive(node.right, callbacks);
  }

  // Call the "leaveNode" callback to notify that traversal
  // of the current node and its children is finished.
  callbacks.leaveNode(node);
}

/**
 * Perform depth-first-search traversal of the rootNode.
 * For every traversal step call "allowTraversal", "enterNode" and "leaveNode" callbacks.
 * See TraversalCallbacks type definition for more details about the shape of callbacks object.
 *
 * @param {BinaryTreeNode} rootNode - The node from which we start traversing.
 * @param {TraversalCallbacks} [callbacks] - Traversal callbacks.
 */
export default function depthFirstSearch(rootNode, callbacks) {
  // In case if user didn't provide some callback we need to replace them with default ones.
  const processedCallbacks = initCallbacks(callbacks);

  // Now, when we have all necessary callbacks we may proceed to recursive traversal.
  depthFirstSearchRecursive(rootNode, processedCallbacks);
}

너비 우선 탐색(BFS)

BFS(Breadth-First Search)는 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기 위한 알고리즘입니다. 트리 루트(또는 '검색 키'라고도 하는 그래프의 임의 노드)에서 시작하여 다음 레벨 이웃으로 이동하기 전에 먼저 이웃 노드를 탐색합니다.

import Queue from '../../../data-structures/queue/Queue';

/**
 * @typedef {Object} Callbacks
 * @property {function(node: BinaryTreeNode, child: BinaryTreeNode): boolean} allowTraversal -
 *   Determines whether DFS should traverse from the node to its child.
 * @property {function(node: BinaryTreeNode)} enterNode - Called when DFS enters the node.
 * @property {function(node: BinaryTreeNode)} leaveNode - Called when DFS leaves the node.
 */

/**
 * @param {Callbacks} [callbacks]
 * @returns {Callbacks}
 */
function initCallbacks(callbacks = {}) {
  const initiatedCallback = callbacks;

  const stubCallback = () => {};
  const defaultAllowTraversal = () => true;

  initiatedCallback.allowTraversal = callbacks.allowTraversal || defaultAllowTraversal;
  initiatedCallback.enterNode = callbacks.enterNode || stubCallback;
  initiatedCallback.leaveNode = callbacks.leaveNode || stubCallback;

  return initiatedCallback;
}

/**
 * @param {BinaryTreeNode} rootNode
 * @param {Callbacks} [originalCallbacks]
 */
export default function breadthFirstSearch(rootNode, originalCallbacks) {
  const callbacks = initCallbacks(originalCallbacks);
  const nodeQueue = new Queue();

  // Do initial queue setup.
  nodeQueue.enqueue(rootNode);

  while (!nodeQueue.isEmpty()) {
    const currentNode = nodeQueue.dequeue();

    callbacks.enterNode(currentNode);

    // Add all children to the queue for future traversals.

    // Traverse left branch.
    if (currentNode.left && callbacks.allowTraversal(currentNode, currentNode.left)) {
      nodeQueue.enqueue(currentNode.left);
    }

    // Traverse right branch.
    if (currentNode.right && callbacks.allowTraversal(currentNode, currentNode.right)) {
      nodeQueue.enqueue(currentNode.right);
    }

    callbacks.leaveNode(currentNode);
  }
}

참조:

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search