[백준] 1991번 : 트리 순회 with JS

 

링크 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회

문제 풀이

 

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

 

 

아직 트리에 대한 이해도가 많이 부족한 거 같다.

굳이 class를 만들어서 풀 필요가 없었다.  

또한 순회에 대한 재귀가 아직 이해가 되지 않아 아래의 링크를 참고했다. (이것을 본 순간 순회의 규칙을 찾고 이해하기 쉬웠다!!)

https://bum-developer.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] 재귀 함수를 이용한 트리 순회 알고리즘

 

tree를 객체에 저장하고 root Node를 기준으로 left, right를 설정해준다. (자동으로 연결됨)

const fs = require("fs");
//const n = fs.readFileSync("예제.txt").toString().trim().split("\n").map(Number);
//const [n, ...arr] = fs.readFileSync("예제.txt").toString();

///dev/stdin

const [n, ...arr] = fs.readFileSync("예제.txt").toString().trim().split("\n");

const tree = {};
let result = "";
for (let i = 0; i < arr.length; i++) {
  let [node, left, right] = arr[i].split(" ");
  tree[node] = [left, right];

  //   console.log(tree[node]);
}

function preorder(node) {
  if (node === ".") return;
  const [left, right] = tree[node];
  result += node;
  preorder(left);
  preorder(right);
}

function inorder(node) {
  if (node === ".") return;
  const [left, right] = tree[node];
  inorder(left);
  result += node;
  inorder(right);
}

function postorder(node) {
  if (node === ".") return;
  const [left, right] = tree[node];
  postorder(left);
  postorder(right);
  result += node;
}
preorder("A");
result += "\n";
inorder("A");
result += "\n";
postorder("A");

console.log(result);