[Algorythm][JS] DFS - 노드 순회(개념)

문제

오늘은 알고리즘 문제라기 보다는, 기본 원리를 이해하고 넘어가자.
DFS 알고리즘 문제를 풀 때 각 트리 구조의 노드를 이동하는 부분이 어려웠기 때문에, 이 부분에 대한 내용을 정리하고 넘어가려고 한다.

전위 순회

전위 순회는 맨 위부터 왼쪽에서 오른쪽으로 차례대로 순회하는 것으로,
1 2 4 5 3 6 7 순으로 노드를 순회하는 것이다.

후위 순회

후위 순회는 맨 아래부터 오른쪽에서 왼쪽으로 차례대로 순회하는 것으로,
4 5 2 6 7 3 1 순으로 노드를 순회하는 것이다.

DFS는 재귀적으로 호출해 구현하는데, 이 재귀함수에 전달하는 인자와 그 인자를 사용해 알고리즘을 짜는 위치의 차이로 이 순회방식이 달라진다.

일단, 각 노드를 어떻게 이동할 수 있는지 부터 짚고 넘어가자.

노드 이동

노드n이 아래 왼쪽의 노드로 이동하려면 어떻게 해야 할까?
노드 1에서 노드 2로 이동하려면 12 = 2를 해야 하듯, n 2를 해주어야 한다.

여기서 다시 아래왼쪽의 노드로 한번 더 이동하려면 이 상태에서 동일하게 재귀호출을 해주면 된다.
그렇다면 아래 오른쪽의 노드로 이동하려면 어떻게 해야할까?
노드 1에서 노드 3으로 이동하려면 12+1 = 3을 해야 하듯, n 2 +1을 해주어야 한다.

알고리즘으로 보기

function solution(n) {
  let answer = '';
  function DFS(n) {
      if(n > 7) return;
      else {
        //console.log(n)//전위순회
        DFS(n * 2);
        // console.log(n)//중위순회
        DFS(n * 2 + 1);
        // console.log(n)//후위순회
      }
  }
  DFS(n);
  return answer;
}

solution(1)