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

minho·2021년 10월 15일

트리용어 정리

출처:https://coderkoo.tistory.com/9

문제

여기 이진트리가 있다.
순회방법은 3가지가 있다.
1. 전위순회
2. 중위순회
3. 후위순회

편의상 왼쪽 단말노드를 ln, 오른쪽 단말노드를 rn, 이 두개의 부모를 node라고 하겠다.

전위순회

node를 먼저 출력하고 ln부터 출력하는 시스템이다.
ln끝까지 출력하고 난 뒤 rn을 출력한다.
즉, 여기서는 1 - 2 - 4 - 5 - 3 - 6 - 7 의 순서이다.
결과적으로 node -> ln -> rn 의 순서이다.

전위순회 코드

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));

중위 순회

맨 밑의 왼쪽단말노드를 먼저 출력하고 부모노드를 출력한뒤 오른쪽 단말노드를 출력하는 시스템이다.
여기서는 4 - 2 - 5 - 1 - 6 - 3 - 7이다.
순서: ln -> node -> rn

중위 순회 코드

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));