[알고리즘] 재귀함수 이진트리 순회 (깊이 우선 탐색 DFS)

 

 

 

 

 

스택프레임을 이용한 재귀함수를 통해 이진트리 깊이 우선탐색 DFS의 순회의 종류와 그 순서를 알아보자.

 

DFS(v)의 v는 정점(vertex)라는 의미를 가지고 있다.

 

이진트리의 기본 진행 순서는 부모노드 -> 왼쪽 -> 오른쪽이다. 

 

해당 문제의 왼쪽 값은 v*2 오른쪽 값은 v*2+1이다.

 

 

 

전위 순회 출력

 

 

      function solution(n) {
        let answer = "";
        function DFS(v) {
          if (v > 7) return;
          else {
            answer += v + " "; //전위순회
            DFS(v * 2);
            DFS(v * 2 + 1);
          }
        }
        DFS(n);
        return answer;
      }

      console.log(solution(1));

 

 

 

전위순회의 경우 부모 -> 왼쪽 -> 오른쪽 순으로 순회한다.

 

 

  1 -> (2 -> 4 -> 5) -> (3 -> 6 -> 7)

부모          왼쪽                 오른쪽

         부     좌    우      부   좌    우

 

 

즉 1 2 4 5 3 6 7 의 순으로 진행된다.

 

 

 

 

 

 

중위 순회 출력

 

 

      function solution(n) {
        let answer = "";
        function DFS(v) {
          if (v > 7) return;
          else {
            DFS(v * 2);
            answer += v + " "; //중위순회
            DFS(v * 2 + 1);
          }
        }
        DFS(n);
        return answer;
      }

      console.log(solution(1));

 

 

 

 

중위순회의 경우 왼쪽 -> 부모 -> 오른쪽 순으로 순회한다.

 

 

 (4 -> 2 -> 5) -> 1 -> (6 -> 3 -> 7)

       왼쪽         부모      오른쪽

  좌    부    우             좌    부   우

 

 

즉 4 2 5 1 6 3 7 의 순으로 진행된다.

 

 

 

 

 

 

 

후위 순회 출력

 

 

      function solution(n) {
        let answer = "";
        function DFS(v) {
          if (v > 7) return;
          else {
            DFS(v * 2);
            DFS(v * 2 + 1);
            answer += v + " "; //후위순회
          }
        }
        DFS(n);
        return answer;
      }

      console.log(solution(1));

 

 

 

 

후위순회의 경우 왼쪽 -> 오른쪽 -> 부모 순으로 순회한다.

 

 

 (4 -> 5 -> 2) -> (6 -> 7 -> 3) -> 1

       왼쪽               오른쪽        부모

  좌    우    부      좌    우    부

 

 

즉 4 5 2 6 7 3 1 의 순으로 진행된다.

 

 

 

 

---

 

 

해당자료는 알고리즘의 보충자료로서 만들어졌습니다.

 

GitHub - Higher77/Algorithm