이진트리 순회(깊이우선탐색) DFS , 전위순회 , 중위순회 , 후위순회

 

 

이진트리란 

이진트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리입니다.

 

깊이 들어가서 왼쪽부터~오른쪽까지 전부 훑는 방식입니다 (그림잘못그림..)

 

모든 순회는 왼쪽 , 오른쪽을 기준으로 설명됩니다.

전위 순회 

부모 >> 왼쪽 >> 오른쪽 출력을 의미합니다.

 

전위순회

 

중위 순회

왼쪽 >> 부모 >> 오른쪽 출력을 의미합니다.

 

중위순회

 

후위 순회

왼쪽 >> 오른쪽 >> 부모 출력을 의미합니다.

 

후위순회

 

 

예시 문제 

이진트리 순회(깊이 우선 탐색) 아래 그림과 같은 이진트리를 전위 순회와 후위 순회를 연습해보세요.

 

풀이

function solution(n) {
  let answer = "";
  function DFS(V) {
    if (V > 7) {
      return;
    } else {
      answer += V;
      DFS(V * 2);
      DFS(V * 2 + 1);
      console.log(V);
    }
  }
  DFS(n);
  return answer;
}

console.log(solution(1));

 

 

이전에 배운 재귀 함수와 스택에 대한 지식을 이용해 DFS에 관해 공부해보았습니다.