다시 돌아온 DFS..첫 개념부터 잡고 갑니다

📍 이진트리(binary tree)

이진 트리란 모든 노드의 자식 노드가 최대 2개의 노드를 가지는 트리를 의미합니다.

📍 이진트리순회

이진트리를 순회하는 방법은 대표적으로 3가지가 있습니다. 3가지 순회 순서에 따라 나눠지게 되는데, 부모 노드를 중심으로 생각하면 쉽습니다.

1️⃣ 전위순회
부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드

2️⃣ 중위순회
왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드

3️⃣ 후위순회
왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드

그래서 방법은?

재귀함수를 사용하여 순회 방식을 간단하게 짜보게 되면,

// 이진트리순회

const solution = (v) => {
  let answer;

  const DFS = (L) => {
    if (L > 7) return;
    else {
      console.log("전위순회 >>>", L); // 1, 2, 4, 5, 3, 6, 7 -> 전위순회
      
      DFS(L * 2); // 왼쪽 자식으로 이동
      
      console.log("중위순회 >>>", L); // 4, 2, 5, 1, 6, 3, 7 -> 중위순회
      
      DFS(L * 2 + 1); // 오른쪽 자식으로 이동
      
      console.log("후위순회 >>>", L); // 4, 5, 2, 6, 7, 3, 1 -> 후위순회
    }
  };
  DFS(v);
  return answer;
};

solution(1);

위 코드와 같이 DFS함수의 호출 순서를 중점으로 중간 연산자의 위치에 따라 순회를 달리 산출하게 됩니다.