CS[DataStructure].push('Traversal')

codeFug·2024년 3월 5일

datastructure

DataStructure

목록 보기

6/7

Traversal

Traversal (순회) 는 Tree와 연관이 깊습니다.

이번 학습에서는 order (pre,in,post) 와 함께 DFS, BFS를 탐구해보겠습니다.

BFS

BFS(너비 우선 탐색)은 말 그대로 breadth를 기준으로 전개해나가는 탐색 방법입니다.

같은 breadth를 모두 탐색완료해야 depth으로 진행됩니다.

Queue를 활용하여 진행된다는 특징이 있습니다.

DFS

DFS(깊이 우선 탐색)은 말 그대로 depth를 기준으로 전개해나가는 탐색 방법입니다.

depth를 먼저 진행한 후 다음에는 같은 breadth 그 다음에 처음으로 돌아가서 다시 depth 진행 하는 식으로 전개됩니다.

Stack를 활용하여 진행된다는 특징이 있습니다.

Order

Order란 세가지 종류가 있다.
각각 간단하게 말하자면 다음과 같다.

Pre : 자신 탐색 > 왼쪽 자식 > 오른쪽 자식
In : 왼쪽 자식 > 자신 탐색 > 오른쪽 자식
Post : 왼쪽 자식 > 오른쪽 자식 > 자신 탐색

구현

JS로 이 모든 것들을 구현해보자.
여기서 주목했던 부분

traversal 함수 하나로 pre, in, post 모든 type을 처리할 수 있도록 하는 것

그리고 이전에 사용했던 Stack과 Queue를 활용해보는 것이다. (이전 포스트와 다르게 length 부분을 추가하여 사용하였습니다.)

import { BinarySearchTree } from "../Tree/BinarySearchTree.js";
import { Stack } from "../Stack/Stack.js";
import { Queue } from "../Queue/Queue.js";

/**
 * type으로 pre, in, post를 받아서 각각의 순회 경로를
 * 받는 함수
 * @param {string} type
 * @param {class} tree
 * @returns {string}
 */
function traversal(type, tree) {
  let result = "";
  if (tree === null){
    return "";
  }
  if (type === "pre") {
    result = dfs(tree);
  } else if (type === "in") {
    // left > value > right
    result += `${traversal("in", tree.left)}`;
    result += `${tree.value} `;
    result += `${traversal("in", tree.right)}`;
  } else if (type === "post") {
    // left > right > value
    result += `${traversal("post", tree.left)}`;
    result += `${traversal("post", tree.right)}`;
    result += `${tree.value} `;
  }
  return result;
}

function bfs(tree) {
  let result = "";
  const queue = new Queue();
  queue.enqueue(tree.root);
  while (queue.length > 0) {
    const node = queue.dequeue();
    result += `${node.value} `;
    if (node.left) {
      queue.enqueue(node.left);
    }
    if (node.right) {
      queue.enqueue(node.right);
    }
  }
  return result;
}

function dfs(tree) {
  let result = "";
  const stack = new Stack();
  stack.push(tree.root);
  while (stack.length > 0) {
    const node = stack.pop();
    result += `${node.value} `;
    if (node.right) {
      stack.push(node.right);
    }
    if (node.left) {
      stack.push(node.left);
    }
  }
  return result;
}

const bst = new BinarySearchTree();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.insert(4);
bst.insert(6);
bst.insert(8);
console.log(bfs(bst));
console.log(dfs(bst));
console.log(traversal("pre", bst));
console.log(traversal("in", bst.root));
console.log(traversal("post", bst.root));