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

- 전위순회 출력 : 부모-> 왼 -> 오

- 중위순회 출력 : 왼 -> 부모 -> 오

- 후외순회 출력 : 왼 -> 오-> 부모

function solution(v) {
  let answer;
  function DFS(v) {
    if (v > 7) return;
    else {
      console.log(v); //전위순회 , 6번줄
      DFS(v * 2); //lt  , 7번줄
      // console.log(v); //중위순회   , 8번줄
      DFS(v * 2 + 1); //rt  ,  9번줄
      // console.log(v); //후위순회 ,  10번줄 
    }
  }
  DFS(v);
}

console.log(solution(1));

 

예를 들어서  전위 순회 출력만 해보기

stack=[]

 

1. D(1)이 들어감 console.log(1)   stack.push(D(1) - 7번줄 대기) answer=1

2.D(2)이 들어감 console.log(2)  stack.push(D(2)-7번줄 대기)   answer=1,2

3.D(4)이 들어감 console.log(4) stack.push(D(4)-7번줄 대기)  answer=1,2,4

4.D(8)이 들어감 , return

5. 가장 위에 있는 stack 실시

6.D(4)이 들어감 stack.push(D(4)-9번줄 대기) 

7. D(9)이 들어감 , return

8.stack.pop (D(4)없어짐)

9. 가장위에있는 stack실시

10.D(2)이 들어감 stack.push(D(2)-9번줄 대기)

11.D(5)이 들어감 console.log(5) stack.push(D(5)-7번줄 대기) answer=1,2,4,5..

.

.

.

.

answer = 1,2,4,5,3,6,7

이런방법으로 하면 위에서봤던 트리모양 대로 전위순회가 출력한다는 것을 볼 수 있다.

기초가 가장 중요하니 중위,후위도 직접 한번 그려보면서 해보면 좋을 듯 하다.