[백준] 1991번 트리 순회 Javascript(NodeJs)

문제링크

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

알고리즘: 트리

풀이

이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제
여기서 이진 트리란 각각의 노드가 최대 두개의 자식 노드를 갖는 트리 자료 구조를 말한다.
입력에서 주어진 이진 트리를 객체로 저장한다. ex) tree[부모] = [왼쪽 자식, 오른쪽 자식]
그리고 각각 순회마다 기록 시점을 다르게 하면 전위 순회, 중위 순회, 후위 순회가 올바르게 출력되는 것을 볼 수 있다.

소스코드

const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let tree = {};
for(let i=1; i<inputData.length; i++) {
    let input = inputData[i].trim().split(' ');
    tree[input[0]] = [input[1],input[2]]; //부모 노드를 key 값으로 자식 노드를 value 값으로 저장.
}
let answel = '';

preOrder('A'); //항상 A는 루트 노드가 됨.
answel += '\n';

inOrder('A');
answel += '\n';

postOrder('A');

function preOrder(pn) {
    //전위 순회
    if(pn === '.') { 
        //재귀의 종료 조건
        return;
    }
    let [lcn, rcn] = tree[pn]; //왼쪽 자식 노드, 오른쪽 자식 노드
    answel += pn;
    preOrder(lcn);
    preOrder(rcn);
}

function inOrder(pn) {
    //중위 순회
    if(pn === '.') {
        //재귀의 종료 조건
        return;
    }
    let [lcn, rcn] = tree[pn]; //왼쪽 자식 노드, 오른쪽 자식 노드
    inOrder(lcn);
    answel += pn;
    inOrder(rcn);
}

function postOrder(pn) {
    //후위 순회
    if(pn === '.') {
        //재귀의 종료 조건
        return;
    }
    let [lcn, rcn] = tree[pn]; //왼쪽 자식 노드, 오른쪽 자식 노드
    postOrder(lcn);
    postOrder(rcn);
    answel += pn;
}

console.log(answel);