이진트리 순회(깊이우선탐색-DFS)

 

 

문제

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보시오.

 

전위순회(부모->왼->오) 출력 : 1 2 4 5 3 6 7  

중위순회(왼->부모->오) 출력 : 4 2 5 1 6 3 7

후위순회(왼->오->부모) 출력 : 4 5 2 6 7 3 1

---

순회에 따른 탐색

전위순회 | 탐색방향 : 부모 -> 왼쪽 -> 오른쪽

 

중위순회 | 탐색방향 : 왼쪽 -> 부모 -> 오른쪽

 

후위순회 | 탐색방향: 왼쪽 -> 오른쪽 -> 부모

 

코드

<script>
  function solution(n) {
    let answer = "";
    function DFS(v) { //v 는 vertex(꼭짓점)의 약자
      if (v > 7) return
      else {
      	①
        DFS(v * 2)
        ②
        DFS(v * 2 + 1)
        ③
      }
    }
    DFS(n);
    return answer;
  }
  solution(1);
</script>

<!--console.log(v) 이 1번에 들어가면 전위순회-->
<!-- 1 2 4 5 3 6 7 -->

<!--console.log(v) 이 2번에 들어가면 중위순회-->
<!-- 4 2 5 1 6 3 7 -->

<!--console.log(v) 이 3번에 들어가면 후위순회-->
<!-- 4 5 2 6 7 3 1 -->

 

전위순회일 때 스택프레임

 

중위순회일 때 스택프레임

 

후위순회일 때 스택프레임

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의