preorder/ inorder/ postorder 구현

어디 나와있는 건 아니고 

어제 우리집 시니어랑 preorder랑 inorder랑 postorder 코드로 구현해보기했다.

헿 맴에드는 그림이 없어서 직접그림

노드안에 저렇게 값이 할당 되어 있을 때,

저 순서대로 순회 하는거다.

function solution(tree) {
  const answer = [];
  function pre(index) {
    answer.push(tree[index]);
    const leftIndex = 2 * index;
    const rightIndex = 2 * index + 1;
    if (leftIndex < tree.length) pre(leftIndex);
    if (rightIndex < tree.length) pre(rightIndex);
  }
  pre(1);
  return answer;
}

tree = [null, 1, 2, 3, 4, 5, 6, 7]
console.log(solution(tree)) // [1, 2, 4, 5, 3, 6, 7]

우선 preorder를 구현 해봤다.

tree 배열은 편의를 위해 그냥 null하나 채우고 시작했다.

그리고 출력하면 [1, 2, 4, 5, 3, 6, 7] 위의 그림속 preorder랑 일치한다.

 

function solution2(tree) {
  const answer = [];
  function inOrder(index) {
    const leftIndex = index * 2;
    const rightIndex = index * 2 + 1;
    if (leftIndex < tree.length) {
      inOrder(leftIndex);
    }
    answer.push(tree[index]);
    if (rightIndex < tree.length) {
      inOrder(rightIndex);
    }
  }

  inOrder(1);
  return answer;
}

console.log(solution2(tree)) // [4, 2, 5, 1, 6, 3, 7]

이건 inorder.

 

function solution3(tree) {
  const answer = [];
  function postOrder(index) {
    const leftIndex = index * 2;
    const rightIndex = index * 2 + 1;
    if (leftIndex < tree.length) {
      postOrder(leftIndex);
    }
    if (rightIndex < tree.length) {
      postOrder(rightIndex);
    }
    answer.push(tree[index]);
  }
  postOrder(1);
  return answer;
}

console.log(solution3(tree))   // [4, 5, 2, 6, 7, 3, 1]

이건 postorder

나름 머리를 쓴다고 쓴거다.. ㅎㅎ

근데 보면 순서만 다르다.

잘한 건가 싶어서 요새 듣고 있는 자료구조/알고리즘 강의에서

관련 내용을 찾아봤다.

//preorder//

function solution(tree) {
  const answer = [];
  function pre(index) {
    if (index > tree.length - 1) return;
    else {
      answer.push(tree[index]);
      pre(index * 2);
      pre(index * 2 + 1);
    }
  }
  pre(1);
  return answer;
}


//inorder//

function solution(tree) {
  const answer = [];
  function in(index) {
    if (index > tree.length - 1) return;
    else {
      in(index * 2);
      answer.push(tree[index]);
      in(index * 2 + 1);
    }
  }
  in(1);
  return answer;
}



//postorder//

function solution(tree) {
  const answer = [];
  function post(index) {
    if (index > tree.length - 1) return;
    else {
      post(index * 2);
      post(index * 2 + 1);
      answer.push(tree[index]);
    }
  }
  post(1);
  return answer;
}

에이...센세.. 이렇게 쉽게 하시면 

제가 뭐가 되나요..

우리센세가 명강의 해주셨다

이거 처음 하는 사람이면

무지성으로 if/else 부터 적으라고...

if에 탈출조건 채워 넣고

else에다가 코드 돌리면 된다.

근데  preorder는 순회 방법이 부모노드-왼쪽노드-오른쪽노드 순으로 순회하고

inorder는 왼-부-오

postorder는 왼-오-부

이다.

else 코드 순서다

 

push 가 부모노드

index * 2 가 왼쪽 노드

index*2+1 이 오른쪽 노드.

ㄴㅇㄱ

이렇게 쉬운 거였다니.

 

혼자 끙끙 앓으면서 고민하던 한시간이 무색해지는 순간이었다.

하지만 그 고민이 없었다면 

이렇게 와닿지도 않았을 거고,

또 금새 까먹었을지도 모른다.

그 고민의 시간덕에

이건 뒤져도 안까먹을듯.