자바스크립트 알고리즘 이진 트리 순회 정리

부모 노드가 1, 자식 노드와 2 와 3,

부모 노드가 2와 3 그에 따른 자식 노드가 4, 5와 6, 7 이라고 한다면

각 왼쪽 자식 노드는 부모 노드에 x2 값을 한것이고, 오른쪽 자식 노드는 x2 +1 한 값이다.

- 전위 순회 출력

let N = 1;

function solution(N) {
  let answer = [];

  function binary(n) {
    if (n > 7) {
      return;
    }
    answer.push(n);
    binary(n * 2);
    binary(n * 2 + 1);
  }

  binary(N);

  return answer;
}

console.log(solution(N)); // [1, 2, 4, 5, 3, 6, 7];

- 설명

1. 처음에 binary(1)이 실행되고, answer에 1이 push된다.
2. 그 후에 밑에 줄인 binary(n x 2)인 binary(2)가 실행되어서 answer에 2가 push 된다.
3. 그 후에 밑에 줄인 binary(n x 2)인 binary(4)가 실행되어서 answer에 4가 push 된다.
4. 그 후에 밑에 줄인 binary(n x 2)인 binary(8)가 실행되지만 7보다 크기때문에 return 된다.
5. 또한 n이 현재 4일때 binary(n x 2 +1)인 binary(9) 또한 7보다 크기때문에 return 된다.
6. n이 2일때 binary(n x 2 + 1)이 아직 실행 되지 않았기 때문에 binary(5)가 실행되어서 answer에 5가 push 된다.
7. 하지만 n이 5일때 binary(10)과 binary(11)은 조건에 충족되지 않기때문에 리턴된다.
8. 맨 처음 n이 1일때 binary(n x 2 +1)이 실행되지 않았기 때문에 binary(3)이 실행되어서 answer에 3이 push 된다.
9. binary(3)일때 binary(nx2)가 실행되어서 binary(6)이 실행되어서 answer에 6이 push 된다.
10. binary(6)에서 binary(12)와 binary(13)은 조건에 충족되지 않으므로 return 된다.
11. 9번줄에 binary(3)일때 binary(n x 2 + 1)이 아직 실행되지 않았으므로 binary(7)이 실행되어 answer에 7이 push 된다.
12. binary(14)와 binary(15)는 조건에 충족되지 않으므로 리턴된다.

- 중위 순회 출력

let N = 1;

function solution(N) {
  let answer = [];

  function binary(n) {
    if (n > 7) {
      return;
    }
    binary(n * 2);
    answer.push(n);
    binary(n * 2 + 1);
  }

  binary(N);

  return answer;
}

console.log(solution(N)); // [4, 2, 5, 1, 6, 3, 7]

- 설명

1. 처음에 binary(1)이 실행되어서 binary(2), binary(4), binary(8)까지 쌓였다가 리턴되어서 answer에 4가 push 된다.
2. binary(n x 2 +1) 인 binary(9)가 실행되지만 n이 7보다 크므로 리턴된다.
3. 밑 스택인 binary(2)로 돌아와서 answer에 2가 push 되고 binary(n x 2 +1)인 binary(5)가 실행된다.
4. binary(n x 2)인 binary(10)은 조건에 성립되지 않으므로 return 되고 answer에 5가 push 되고, binary(11)도 조건에 충족되지 않으므로 리턴된다.
5. 맨 밑 스택이었던 binary(1)이 실행되어서 answer에 1이 push가 되고 binary(n x 2 +1)인 binary(3)이 실행된다.
6. binary(3)에서 binary(n x 2)인 binary(6)이 실행된 후 binary(12)까지 실행되지만, 조건에 충족되지 않으므로 리턴되고 answer에 6이 push 된다.
7. 그 후 binary(n x 2 +1)인 binary(13) 조건에 충족되지 않으므로 리턴된다.
   8.6번줄에 binary(3)이었을때 binary(n x 2 +1)이 실행되지 않았으므로 binary(7)이 실행된다.
8. binary(14)와 binary(15)는 조건에 충족되지 않으므로 리턴되고 answer에는 7이 push되며 끝난다.

- 후위 순위 출력

let N = 1;

function solution(N) {
  let answer = [];

  function binary(n) {
    if (n > 7) {
      return;
    }
    binary(n * 2);
    binary(n * 2 + 1);
    answer.push(n);
  }

  binary(N);

  return answer;
}

console.log(solution(N));

- 풀이

1. binary(1)이 실행된다
2. binary(2), binary(4), binary(8)과 binary(9)까지 되었다가 리턴된다.
3. binary(4) 에서 binary 함수 실행이 다 끝나고 answer에 4가 push 된다.
4. binary(n x 2 +1)인 binary(5)가 실행된다;
5. binary(5)에서 나머지 식인 binary(10)과 binary(11)은 조건에 충족되지 않으므로 리턴된다.
6. binary(5)에서 마지막줄인 answer에 5가 push 된다.
7. 기존 라인이었던 binary(2)에서 answer에 2가 push 된다.
8. 처음에 binary(2)부분이 끝나고 binary(3)부분이 다시 실행된다.
9. binary(3), binary(6)까지 실행된후 binary(12)와 binary(13)은 조건에 충족 되지 않으므로 리턴된다.
10. binary(6)에서 answer에 6이 push 된다.
11. 8번 줄에서 binary(n x 2 + 1)인 binary(7)이 실행되어서 binary(7)이 실행된다.
12. answer에 7이 push 되고 나머지 binary(1)에서 answer에 1이 push 된다.